2

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

Numeri
  • 194
  • 1
    Are you looking for strings of length $n$? Two symbols could make $111$ or $112$ for example, if three symbols were allowed. – Mark Bennet Aug 21 '13 at 18:43
  • Ah, yes sorry about that. I did mean of strings of length n. I'll edit the question now. Thanks! – Numeri Aug 21 '13 at 18:56
  • If I've done things correctly, the combinations for $n=4$ are $$1111, 1112, 1121, 1122, 1221, 1212, 1123, 1213, 1231, 2113, 1234$$ so the sequence for the number of $n$-length combinations starts $1,2,4,11$. You might try carefully doing another couple of examples and then see if the sequence matches up with anything at http://oeis.org – Barry Cipra Aug 21 '13 at 19:07
  • 1
    You might consider counting symmetrical duplicates first and then use Burnside's Lemma to fix that afterwards. (Two-element group acting on the strings, the non-identity element mirrors) – Christoph Aug 21 '13 at 19:39

2 Answers2

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.

Christoph
  • 24,912
  • Thank you for the answer!! Could you clarify to me though, what you mean by "the number of partitions of the set {1,2,…,n} up to symmetry"? Thanks! – Numeri Aug 22 '13 at 01:39
  • The Wikipedia article on Partitions explains what partitions of a set are. In your case, let $n=3$ then $112$ corresponds to ${{1,2},{3}$ since the first and second position are labelled $1$, while the third position is labelled $3$. Flipping the numbers transforms this partition into ${{2,3},{1}}$ which is not the same partition, but up to symmetry it is. – Christoph Aug 22 '13 at 06:16
1

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.

Marko Riedel
  • 61,317
  • Thanks for the answer @Marko! This problem wasn't quite so simple as I thought it would be! :D – Numeri Dec 28 '13 at 02:41