Difference between revisions of "Binary tree"
(MSC 05C05) |
m (link oeis) |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 3: | Line 3: | ||
A (planar) [[rooted tree]] for which every node has a left child, a right child, neither, or both. Three examples are: | A (planar) [[rooted tree]] for which every node has a left child, a right child, neither, or both. Three examples are: | ||
| − | < | + | <gallery> |
| − | + | File:Binary tree 1.svg | |
| − | + | File:Binary tree 2.svg | |
| + | File:Binary tree 3.svg | ||
| + | </gallery> | ||
These three are all different. | These three are all different. | ||
| Line 11: | Line 13: | ||
The number of binary trees with $n$ nodes, $p$ left children, $q$ right children ($p+q=n-1$) is | The number of binary trees with $n$ nodes, $p$ left children, $q$ right children ($p+q=n-1$) is | ||
| − | $$\ | + | $$\frac{1}{n}\binom{n}{p}\binom{n}{p+1} = \frac{1}{n}\binom{n}{p}\binom{n}{q}.$$ |
| − | The numbers $ | + | The numbers $\frac{1}{n}\binom{n}{p}\binom{n}{p+1}$ are called Runyon numbers or Narayana numbers ({{OEIS|A001263}}). |
| − | A complete binary tree is one in which every node has both left and right children or is a leaf (i.e., has no children). E.g., there are two complete binary trees with five nodes: | + | A complete binary tree is one in which every node has both left and right children or is a leaf (''i.e.'', has no children). ''E.g.'', there are two complete binary trees with five nodes: |
| − | < | + | <gallery> |
| + | File:Complete binary tree left.svg | ||
| + | File:Complete binary tree right.svg | ||
| + | </gallery> | ||
| − | + | A complete binary tree has an odd number of nodes, say $2k+1$, and then the number of leaves is $k+1$. Label the $k+1$ leaves from left to right with symbols $x_1,\dotsc,x_{k+1}$. Then the various complete binary trees with their $k+1$ leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word $x_1\cdots x_{k+1}$, each way corresponding to a computation of the product by successive multiplications of precisely two factors each time. The number of ways of doing this, and hence the number of binary trees with $k+1$ nodes, is the Catalan number | |
| − | + | $$\frac{1}{k+1}\binom{2k}{k},k=1,2,\dotsc$$ | |
| − | + | which is {{OEIS|A000108}}. | |
| − | The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 | + | The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 {{Cite|a1}}. |
The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set $X$ and the [[Free magma|free magma]] on $X$. | The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set $X$ and the [[Free magma|free magma]] on $X$. | ||
====References==== | ====References==== | ||
| − | + | * {{Ref|a1}} E. Catalan, "Note sur une équation aux différences finies" ''J. Math. Pures Appl.'' , '''3''' (1838) pp. 508–516 | |
| − | + | * {{Ref|a2}} L. Comtet, "Advanced combinatorics" , Reidel (1974) {{ZBL|0283.05001}} | |
| − | + | * {{Ref|a3}} I.M. Gessel, R.P. Stanley, "Algebraic enumeration" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovacz (ed.) , ''Handbook of Combinatorics'' , '''II''' , Elsevier (1995) pp. 1021–1062 | |
| − | + | * {{Ref|a4}} R.P. Stanley, "Enumerative combinatorics" , Wadsworth and Brooks/Cole (1986) | |
| − | |||
| − | |||
Latest revision as of 08:31, 12 November 2023
2020 Mathematics Subject Classification: Primary: 05C05 [MSN][ZBL]
A (planar) rooted tree for which every node has a left child, a right child, neither, or both. Three examples are:
These three are all different.
The number of binary trees with $n$ nodes, $p$ left children, $q$ right children ($p+q=n-1$) is
$$\frac{1}{n}\binom{n}{p}\binom{n}{p+1} = \frac{1}{n}\binom{n}{p}\binom{n}{q}.$$
The numbers $\frac{1}{n}\binom{n}{p}\binom{n}{p+1}$ are called Runyon numbers or Narayana numbers (OEIS sequence A001263).
A complete binary tree is one in which every node has both left and right children or is a leaf (i.e., has no children). E.g., there are two complete binary trees with five nodes:
A complete binary tree has an odd number of nodes, say $2k+1$, and then the number of leaves is $k+1$. Label the $k+1$ leaves from left to right with symbols $x_1,\dotsc,x_{k+1}$. Then the various complete binary trees with their $k+1$ leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word $x_1\cdots x_{k+1}$, each way corresponding to a computation of the product by successive multiplications of precisely two factors each time. The number of ways of doing this, and hence the number of binary trees with $k+1$ nodes, is the Catalan number
$$\frac{1}{k+1}\binom{2k}{k},k=1,2,\dotsc$$
which is OEIS sequence A000108.
The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 [a1].
The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set $X$ and the free magma on $X$.
References
- [a1] E. Catalan, "Note sur une équation aux différences finies" J. Math. Pures Appl. , 3 (1838) pp. 508–516
- [a2] L. Comtet, "Advanced combinatorics" , Reidel (1974) Zbl 0283.05001
- [a3] I.M. Gessel, R.P. Stanley, "Algebraic enumeration" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovacz (ed.) , Handbook of Combinatorics , II , Elsevier (1995) pp. 1021–1062
- [a4] R.P. Stanley, "Enumerative combinatorics" , Wadsworth and Brooks/Cole (1986)
Binary tree. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Binary_tree&oldid=38558