Math 2.0

Combinatorics Theorem

Closed formula for Catalan numbers

Builds on Binomial coefficientCentral binomial coefficientCatalan numbers

Statement

Let nn be a natural number, and let CnC_n be the nn-th Catalan number. Then Cn=1n+1(2nn)=(2n)!(n+1)! n!.C_n = \frac{1}{n + 1} \binom{2n}{n} = \frac{(2n)!}{(n + 1)!\, n!}.

Remarks

The fraction is an integer, because Cn=(2nn)−(2nn+1)C_n = \binom{2n}{n} - \binom{2n}{n+1}. The numerator (2nn)\binom{2n}{n} is the central binomial coefficient. Example: C4=15(84)=705=14C_4 = \frac{1}{5} \binom{8}{4} = \frac{70}{5} = 14.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Binomial coefficient, definition, no evidence levelBinomial coefficientdefinitionCatalan numbers, definition, no evidence levelCatalan numbersdefinitionCentral binomial coefficient, definition, no evidence levelCentral binomial coef…definitionClosed formula for Catalan numbers, statement, no evidence levelClosed formula for Ca…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Binomial coefficient definition
  2. Catalan numbers definition
  3. Central binomial coefficient definition
  4. Closed formula for Catalan numbers statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Catalan_number, Proof of the formula
About this page
Tag0NNDQVJ54Q
URIm2://0NNDQVJ54Q
Kindstatement, theorem
WritingW0 stub
MSC05A15
StatusThis copy of the site has no build data. Run m2 status 0NNDQVJ54Q.
UsesBinomial coefficient, Central binomial coefficient, Catalan numbers

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.