What is the number of achiral color patterns for a row of n colors containing k different colors?

Question

A color pattern consists of a string of n letters, with each letter standing for a separate color. If we permute the letters, the resultant pattern is equivalent. Thus ABC, ACB, BAC, BCA, CAB, and CBA are equivalent color patterns. The number of nonequivalent color patterns for a string of n colors containing exactly k different colors is the Stirling subset number S2(n,k). For example, if n=3 and k=2, we have AAB, ABA, and ABB. Note that none of these is a permutation of another. A color pattern is achiral if its reverse (or a permutation of the colors thereof) is the same as the original. For example, if n=5 and k=3, there are five achiral color patterns: AABCC, ABACA, ABBBC, ABCAB, and ABCBA. Results for odd n appear in OEIS A140735; for even n in OEIS A293181. I have a recursive method to determine the number of achiral color patterns, but I am wondering if there is a closed-form solution.

Answer 1

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