Editing Binary tree (section)

== Combinatorics ==
{{unreferenced section|date=July 2014}}
In [[combinatorics]], one considers the problem of counting the number of full binary trees of a given size.  Here the trees have no values attached to their nodes (this would just multiply the number of possible trees by an easily determined factor), and trees are distinguished only by their structure; however, the left and right child of any node are distinguished (if they are different trees, then interchanging them will produce a tree distinct from the original one). The size of the tree is taken to be the number ''n'' of internal nodes (those with two children); the other nodes are leaf nodes and there are {{math|''n'' + 1}} of them. The number of such binary trees of size ''n'' is equal to the number of ways of fully parenthesizing a string of {{math|''n'' + 1}} symbols (representing leaves) separated by ''n'' binary operators (representing internal nodes), to determine the argument subexpressions of each operator. For instance for {{math|''n'' {{=}} 3}} one has to parenthesize a string like {{tmath|X*X*X*X}}, which is possible in five ways:
: <math display=block>((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).</math>
The correspondence to binary trees should be obvious, and the addition of redundant parentheses (around an already parenthesized expression or around the full expression) is disallowed (or at least not counted as producing a new possibility).

There is a unique binary tree of size 0 (consisting of a single leaf), and any other binary tree is characterized by the pair of its left and right children; if these have sizes ''i'' and ''j'' respectively, the full tree has size {{math|''i'' + ''j'' + 1}}. Therefore, the number <math>C_n</math> of binary trees of size ''n'' has the following recursive description <math>C_0=1</math>, and <math>\textstyle C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}</math> for any positive integer ''n''. It follows that <math>C_n</math> is the [[Catalan number]] of index ''n''.

The above parenthesized strings should not be confused with the set of words of length 2''n'' in the [[Dyck language]], which consist only of parentheses in such a way that they are properly balanced. The number of such strings satisfies the same recursive description (each Dyck word of length 2''n'' is determined by the Dyck subword enclosed by the initial '(' and its matching ')' together with the Dyck subword remaining after that closing parenthesis, whose lengths 2''i'' and 2''j'' satisfy {{math|''i'' + ''j'' + 1 {{=}} ''n''}}); this number is therefore also the Catalan number <math>C_n</math>. So there are also five Dyck words of length 6:
: {{math|()()(),{{quad}} ()(()),{{quad}} (())(),{{quad}} (()()),{{quad}} ((()))}}

These Dyck words do not correspond to binary trees in the same way. Instead, they are related by the following recursively defined bijection: the Dyck word equal to the empty string corresponds to the binary tree of size 0 with only one leaf. Any other Dyck word can be written as (<math>w_1</math>)<math>w_2</math>, where <math>w_1</math>,<math>w_2</math> are themselves (possibly empty) Dyck words and where the two written parentheses are matched. The bijection is then defined by letting the words <math>w_1</math> and <math>w_2</math> correspond to the binary trees that are the left and right children of the root.

A bijective correspondence can also be defined as follows: enclose the Dyck word in an extra pair of parentheses, so that the result can be interpreted as a [[Lisp (programming language)|Lisp]] list expression (with the empty list () as only occurring atom); then the [[Lisp (programming language)#S-expressions represent lists|dotted-pair]] expression for that proper list is a fully parenthesized expression (with NIL as symbol and '.' as operator) describing the corresponding binary tree (which is, in fact, the internal representation of the proper list).

The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a [[free magma]] on a singleton set.