## § When are the catalan numbers odd

- The catalan numbers $C_n$ count the number of binary trees on $n$ nodes.
- For every binary tree, label the nodes in some standard ordering (eg. BFS).
- Pick the lex smallest
*unbalanced * node (node with different left and right subtree sizes). - The operation that swaps the left and right subtrees of the lex smallest unbalanced node is an involution.
- This operation only fails when we have a complete binary tree, so the number of nodes is $n = 2^r - 1$, so we pair such a complete binary tree to itself.
- This breaks the set $C_n$ into an even number of trees (pairs of unbalanced trees) and a potential "loner tree" (paired with itself) which is the complete binary tree.
- Thus $C_n$ is odd iff $n = 2^r - 1$, which allows for us to have a complete binary tree, which is not paired by the involution.
- Reference