Combining symbols with symmetry

Question

So this question has probably been answered already, but I can't find a good answer through searching google or this site. Basically, if I have n symbols, how many n-length combinations of the symbols can I make, excluding symmetrical duplicates and duplicates made by switching symbols for each other?

For instance, with the following sets of symbols you can get the following combinations:

{1,2}  
  11, 12
{1,2,3}  
  123, 112, 121, 111

(I'm only mostly sure that those are all the combinations for the set {1,2,3})

If you can point me to a previous question like this, or answer this one, that would be great!

Thanks in advance,
Numeri

Answer 1

The problem boils down to finding the number of partitions of the set $\{1,2,\dots,n\}$ up to symmetry (i.e. $1\mapsto n$, $2\mapsto n-1$, ...), let's call this number $K_n$. First of all, the number of all partitions is the $n$-th Bell number $B_n$. From there we should be able to count the partitions up to symmetry using Burnside's lemma as $$K_n=\frac 1 2 \left(B_n + F_n\right),$$ where $F_n$ is the number of partitions that are invariant under the symmetry. Counting these is more difficult than I imagined, when I made my comment earlier.

To tackle the problem, I wrote a Sage script to find $K_n$ and $F_n$:

B = []
K = []
F = []

for n in range(1,8):
    partitions = SetPartitions(n).list()
    B_n = len(partitions)

    for p in partitions:
        flipped = p.apply_permutation(Permutations(n).identity().reverse())
        if p != flipped:
            partitions.remove(flipped)

    K_n = len(partitions)
    F_n = 2*K_n-B_n

    B.append(B_n)
    K.append(K_n)
    F.append(F_n)

The results are $$ \begin{align*} B_n &= (1, 2, 5, 15, 52, 203, 877, \dots),\\ K_n &= (1, 2, 4, 11, 32, 117, 468, \dots),\\ F_n &= (1, 2, 3, 7, 12, 31, 59, \dots). \end{align*} $$

Plugging the sequences into OEIS we find

• A000110: Bell numbers,
• A103293: Number of ways to color n regions arranged in a line such that consecutive regions do not have the same color,
• A080107: Number of fixed points of permutation of SetPartitions under $\{1,2,\dots,n\}\to\{n,n-1,\dots,1\}$.

Exactly what we were looking for. The formular given for $F_n$ on OEIS involes $q$-analog Bell numbers, which I haven't heard of before.

Answer 2

This is a case of Power Group Enumeration where we substitute $N$ colors into $N$ slots with the symmetric group acting on the colors and the group consisting of a single flip acting on the slots. Two Maple programs for this problem were posted at this MSE link.

We need the cycle index of the group $F_k$ containing the identity and a single flip of the row of slots into which we distribute the $N$ colors. We have that when $k$ is even, $$Z(F_k) = \frac{1}{2} a_1^k + \frac{1}{2} a_2^{k/2}$$ and when $k$ is odd, $$Z(F_k) = \frac{1}{2} a_1^k + \frac{1}{2} a_1 a_2^{(k-1)/2}.$$

This software gives the following generating functions for small numbers of symbols, e.g. for $N=3$ $${\it Q1\_Q1\_Q1}+{\it Q3}+2\,{\it Q1\_Q2}$$ and for $N=4$ $$3\,{\it Q2\_Q2}+{\it Q4}+2\,{\it Q1\_Q3}+{\it Q1\_Q1\_Q1\_Q1}+4\,{\it Q1\_Q1\_Q2}$$ and for $N=5$ $$6\,{\it Q1\_Q1\_Q1\_Q2}+9\,{\it Q1\_Q2\_Q2}+6\,{\it Q1\_Q1\_Q3}\\+{\it Q1\_Q1\_Q1\_Q1\_Q1}+{\it Q5}+6\,{\it Q2\_Q3}+3\,{\it Q1\_Q4}$$ and finally for $N=6$ $$9\,{\it Q2\_Q4}+3\,{\it Q1\_Q5}+{\it Q1\_Q1\_Q1\_Q1\_Q1\_Q1}+27\,{\it Q1\_Q1\_Q2\_Q2}\\+11\,{\it Q2\_Q2\_Q2}+9\,{\it Q1\_Q1\_Q1\_Q1\_Q2}+9\,{\it Q1\_Q1\_Q4 }+30\,{\it Q1\_Q2\_Q3}\\+10\,{\it Q1\_Q1\_Q1\_Q3}+{\it Q6}+7\,{\it Q3\_Q3}. $$ Counting the number of different sequences we obtain $$1, 2, 4, 11, 32, 117, 468, 2152, 10743, 58487, 340390, 2110219, 13830235, 95475556\ldots$$ which is indeed OEIS A103294. Here is another MSE link where the cycle index of the flip group was used.