Math 2.0

statement theorem

Catalan recurrence

Statement

Let nn be a natural number, and let CmC_m be the Catalan numbers. Then Cn+1=∑i=0nCi Cn−i.C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}.

Remarks

With the definition of the node Catalan numbers, the statement holds by definition. Its content is in the combinatorial families that satisfy it. Example: C4=C0C3+C1C2+C2C1+C3C0=5+2+2+5=14C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 5 + 2 + 2 + 5 = 14. For Dyck words, the recurrence splits a word at the first return to level 00.

Explanations

L1 human

A structure of size n+1n + 1 often splits into a left part of size ii and a right part of size n−in - i. Add over all ii the number of ways to build the two parts, and you get the next Catalan number.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 2 nodes in this order. The foundations come first, and the list ends with this node.

Catalan numbers, definition, no evidence levelCatalan numbersdefinitionCatalan recurrence, statement, no evidence levelCatalan recurrencestatement
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Catalan numbers definition
  2. Catalan recurrence statement

Sources

  1. Web https://en.wikipedia.org/wiki/Catalan_number, Properties

What links here

No node links to this node yet.