Return to Answer

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 OEIS 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)$.

The characterization of the numbers for odd $n$ given in OEIS A140735 suggestions an alternative formula for these numbers, which is not too hard to prove combinatorially: Let $S$ be the operator on polynomials in $t$ defined by $S(p(t)) = (t+t^2 + d/dt)(p(t))$. Then the coefficient of $x^m/m!$ in $F(t,x)$ is $S^n(1)$ and the coefficient of $x^m/m!$ in $te^x F(t,x)$ is $S^n(t)$.

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'$. The blocks must be permuted by $\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 OEIS 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)$.

The characterization of the numbers for odd $n$ given in OEIS A140735 suggestions an alternative formula for these numbers, which is not too hard to prove combinatorially: Let $S$ be the operator on polynomials in $t$ defined by $S(p(t)) = (t+t^2 + d/dt)(p(t))$. Then the coefficient of $x^m/m!$ in $F(t,x)$ is $S^n(1)$ and the coefficient of $x^m/m!$ in $te^x F(t,x)$ is $S^n(t)$.

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 OEIS 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)$.

The characterization of the numbers for odd $n$ given in OEIS A140735 suggestions an alternative formula for these numbers, which is not too hard to prove combinatorially: Let $S$ be the operator on polynomials in $t$ defined by $S(p(t)) = (t+t^2 + d/dt)(p(t))$. Then the coefficient of $x^m/m!$ in $F(t,x)$ is $S^n(1)$ and the coefficient of $x^m/m!$ in $te^x F(t,x)$ is $S^n(t)$.

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 OEIS 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)$.

The characterization of the numbers for odd $n$ given in OEIS A140735 suggestions an alternative formula for these numbers, which is not too hard to prove combinatorially: Let $S$ be the operator on polynomials in $t$ defined by $S(p(t)) = (t+t^2 + d/dt)(p(t))$. Then the coefficient of $x^m/m!$ in $F(t,x)$ is $S^n(1)$ and the coefficient of $x^m/m!$ in $te^x F(t,x)$ is $S^n(t)$.

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 OEIS 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)$.

The characterization of the numbers for odd $n$ given in OEIS A140735 suggestions an alternative formula for these numbers, which is not too hard to prove combinatorially: Let $S$ be the operator on polynomials in $t$ defined by $S(p(t)) = (t+t^2 + d/dt)(p(t))$. Then the coefficient of $x^m/m! in $F(t,x)$ is $S^n(1)$ and the coefficient of $x^m/m!$ in $e^x F(t,x)$ is $S^n(t)$.

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 OEIS 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)$.

The characterization of the numbers for odd $n$ given in OEIS A140735 suggestions an alternative formula for these numbers, which is not too hard to prove combinatorially: Let $S$ be the operator on polynomials in $t$ defined by $S(p(t)) = (t+t^2 + d/dt)(p(t))$. Then the coefficient of $x^m/m!$ in $F(t,x)$ is $S^n(1)$ and the coefficient of $x^m/m!$ in $te^x F(t,x)$ is $S^n(t)$.