Skip to main content
2 of 6
deleted 66 characters in body
Ira Gessel
  • 17k
  • 1
  • 58
  • 80

Here's a sketch of the derivation of the exponential generating function. First consider the case $n$ even, $n=2m$. The problem is equivalent to counting partitions with $k$ blocks of the set $\{1,2,\dots, m\}\cup \{1', 2',\dots, m'\}$ that are invariant under the involution $\omega$ that switches each $i$ with $i'$. Each block must be invariant under $\omega$, and since unequal blocks are disjoint, each block is either fixed (and thus contains either both $i$ and $i'$ or neither for each $i$) or disjoint from its image under $\omega$. A fixed block may be identified with the set of its unprimed entries, so the exponential generating function for these blocks is $e^x-1$. For pairs of blocks that are disjoint from their images, we take a nonempty subset $S$ of $\{1,\dots, m\}$ and prime an arbitrary subset of $S$, but since complementary subsets of $S$ give the same pair, we must divide by 2. So the e.g.f for these pairs of blocks is $\tfrac12(e^{2x}-1)$. If we weight each block by $t$ then the e.g.f for fixed blocks and pairs of blocks is $$t(e^x-1) + t^2(e^{2x}-1)/2.$$ So by the properties of exponential generating functions (the ``exponential formula") the number of partitions of $\{1,2,\dots, m\}\cup \{1', 2',\dots, m'\}$ fixed by $\omega$ with $k$ blocks is the coefficient of $t^k x^m/m!$ in $$F(t,x):=\exp\left(t(e^x-1) + t^2(e^{2x}-1)/2\right).$$ Note that setting $t=1$ gives the generating function of A002872.

For $n=2m+1$ we consider partitions of $\{0\}\cup\{1,2,\dots, m\}\cup \{1', 2',\dots, m'\}$, where $\omega$ fixes 0. The block containing 0 must be fixed by $\omega$, so by similar reasoning we find that the number of partitions of $\{0\}\cup\{1,2,\dots, m\}\cup \{1', 2',\dots, m'\}$ fixed by $\omega$ with $k$ blocks is the coefficient of $t^k x^m/m!$ in $te^x F(t,x)$.

Ira Gessel
  • 17k
  • 1
  • 58
  • 80