§ 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