Skip to main content
2 of 4
added 24 characters in body
Ira Gessel
  • 17k
  • 1
  • 58
  • 80

A chain $$ A_k \subset A_{k-1} \subset\dots\subset A_1 \subset A_0 $$ can be represented by the ordered partition $(B_1, B_2, \dots, B_{k+1})$ of the set $A_0=\{1, 2, \dots, n\}$ where $B_1=A_k$, $B_2=A_{k-1}-A_k$, $\dots,$ $B_{k+1}=A_0-A_1$.

First, a generating function proof. If we wanted to count such chains (or ordered partitions) without signs, the generating function would be $\sum_{j=0}^\infty (e^x-1)^j = 1/(2-e^x)$ (http://oeis.org/A000670). With signs, the generating function is $$\sum_{j=0}^\infty (-1)^{j+1}(e^x-1)^j= -e^{-x} = \sum_{n=0}^\infty (-1)^{n+1} \frac{x^n}{n!}$$

For a combinatorial proof using a sign reversing involution that changes the parity of the number of blocks, write the entries of each block in increasing order, with a bar between blocks, so $\{2,4,6\}\{1,3\}\{5\}$ would be written as $ 2 4 6 | 1 3 | 5 $. Find the first position, if there is one, where a number is followed by a larger number. If there is a bar there, remove it, and if there is no bar there then put one in. So our example would be mapped to $ 2 | 4 6 | 1 3 | 5 $; as another example, $4 | 3 | 1 2|$ would map to $4 | 3| 1 | 2$. The only ordered partitions not paired up are of the form $n | n-1| \cdots |2 | 1$.

Ira Gessel
  • 17k
  • 1
  • 58
  • 80