In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a Schröder number describes the number of paths from the southwest corner (0, 0) of an n × n grid to the northeast corner (n, n), using only single steps north, northeast, or east, that do not rise above the SW–NE diagonal.

The first few Schröder numbers are

1, 2, 6, 22, 90, 394, 1806, 8558, .... .

Examples

The following figure shows the 6 Schröder paths through a 2 × 2 grid:

Related constructions

Schröder numbers count the number of paths from (0, 0) to (2n, 0), using only single steps northeast or southeast (steps (1, 1) or (1, –1)) or double steps east (steps (2, 0)), that never fall below the x-axis:



Similarly, the Schröder numbers count the number of ways to divide a rectangle into n + 1 smaller rectangles using n cuts; with the restriction that there are n points inside the rectangle, no two of these points falling on the same line parallel to either the x-axis or y-axis, and each cut intersects one of the points and divides only a single rectangle in two. The following figure shows the 6 rectangulations into 3 rectangles using two cuts:



And here are the 22 rectangulations into 4 rectangles using three cuts:



Schröder numbers also count separable permutation

Separable permutation

In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations can also be characterized as the permutations that contain neither 2413 nor 3142...

s.

See also

• Delannoy number
  Delannoy number
  In mathematics, a Delannoy number D describes the number of paths from the southwest corner of a rectangular grid to the northeast corner , using only single steps north, northeast, or east....
  
  
• Motzkin number
  Motzkin number
  In mathematics, a Motzkin number for a given number n is the number of different ways of drawing non-intersecting chords on a circle between n points. The Motzkin numbers have very diverse applications in geometry, combinatorics and number theory...
  
  
• Narayana number
  Narayana number
  In combinatorics, the Narayana numbers N, n = 1, 2, 3 ..., 1 ≤ k ≤ n, form a triangular array of natural numbers, called Narayana triangle, that occur in various counting problems. They are named for T.V...
  
  
• Schröder–Hipparchus number
  Schröder–Hipparchus number
  In number theory, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by...
  
  

External links

• Stanley, Richard P.
  Richard P. Stanley
  Richard Peter Stanley is the Norman Levinson Professor of Applied Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. He received his Ph.D. at Harvard University in 1971 under the supervision of Gian-Carlo Rota...
  
  : Catalan addendum to Enumerative Combinatorics, Volume 2