Schröder number

Schröder number

In mathematics, 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 OEIS|id=A006318:

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

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

Equivalently, Schröder numbers can be represented as paths from (0, 0) to (2"n", 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:

ee also

*Delannoy number
*Motzkin number
*Narayana number

References

*MathWorld|title=Schröder Number|urlname=SchroederNumber

External links

* Stanley, Richard P.: [http://www-math.mit.edu/~rstan/ec/catadd.pdf Catalan addendum] to "Enumerative Combinatorics, Volume 2"


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Schröder — is a German surname which has been held by many notable people including:* Ernst Schröder, German logician and mathematician. * Christian Mathias Schröder * Gerhard Schröder (CDU) (1910 1989), German politician * Gerhard Schröder (SPD) (b. 1944) …   Wikipedia

  • Schröder, Gerhard — born April 7, 1944, Mossenberg, near Detmold, Ger. Chancellor of Germany. In his youth he joined the Social Democratic Party and the Young Socialists, and, as a law student at Göttingen, he participated in the student protests of 1968. He served… …   Universalium

  • Schroder — Recorded in a bewildering number of spellings, some shown below, this is an ancient German surname. It is occupational and describes a tailor, and is with Smith or Schmit, perhaps the most popular of all occupational surnames. These spelling… …   Surnames reference

  • Delannoy number — In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east. For an n × n grid, the first few Delannoy… …   Wikipedia

  • Motzkin number — In mathematics, a Motzkin number for a given number n (named after Theodore Motzkin) 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,… …   Wikipedia

  • Narayana number — In combinatorics, the Narayana numbers N(n, k), 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. Narayana… …   Wikipedia

  • Gerhard Schröder — Infobox Chancellor name = Gerhard Schröder office = 7th Chancellor of the Federal Republic of Germany term start = 27 October 1998 term end = 22 November 2005 president = Johannes Rau Horst Köhler deputy = Joschka Fischer predecessor = Helmut… …   Wikipedia

  • Ernst Schröder — For the actor, see Ernst Schröder (actor). Ernst Schröder (25 November, 1841 Mannheim, Germany – 16 June, 1902 Karlsruhe Germany) was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of… …   Wikipedia

  • Rietveld Schröder House — Infobox World Heritage Site Name = Rietveld Schröderhuis (Rietveld Schröder House) imagecaption= The exterior of the Rietveld Schröder House State Party = NED Type = Cultural Criteria = I, II ID = 965 Link = http://whc.unesco.org/en/list/965… …   Wikipedia

  • Oliver Schröder — The title of this article contains the character ö. Where it is unavailable or not desired, the name may be represented as Oliver Schroeder. Oliver Schröder Personal information Full name …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”