§ When are the catalan numbers odd
- The catalan numbers count the number of binary trees on 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 , so we pair such a complete binary tree to itself.
- This breaks the set 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 is odd iff , which allows for us to have a complete binary tree, which is not paired by the involution.