Math 2.0

statement theorem

Binary trees are counted by Catalan numbers

Statement

Let nn be a natural number. Then the number of binary trees with exactly nn nodes is the Catalan number CnC_n.

Remarks

Here a binary tree is either empty or a root node with an ordered pair of binary trees as its left and right subtrees. For n=3n = 3 there are C3=5C_3 = 5 binary trees. Proof idea: a nonempty tree with n+1n + 1 nodes has a left subtree with ii nodes and a right subtree with n−in - i nodes. This gives the Catalan recurrence.

Explanations

L1 human

Remove the root of a binary tree, and you get a left tree and a right tree. The sizes of the two trees add up to one less than the size of the original tree, and this gives the Catalan recurrence.

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 3 nodes in this order. The foundations come first, and the list ends with this node.

Binary tree, definition, no evidence levelBinary treedefinitionCatalan numbers, definition, no evidence levelCatalan numbersdefinitionBinary trees are counted by Catalan numbers, statement, no evidence levelBinary trees are coun…statement
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. Binary tree definition
  2. Catalan numbers definition
  3. Binary trees are counted by Catalan numbers statement

Sources

  1. Web https://en.wikipedia.org/wiki/Catalan_number, Applications in combinatorics

What links here

No node links to this node yet.