Combining symbols with symmetry 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
 A: 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.
A: 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.
