2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Are you looking for strings of length $n$? Two symbols could make $111$ or $112$ for example, if three symbols were allowed. $\endgroup$ – Mark Bennet Aug 21 '13 at 18:43
  • $\begingroup$ Ah, yes sorry about that. I did mean of strings of length n. I'll edit the question now. Thanks! $\endgroup$ – Numeri says Reinstate Monica Aug 21 '13 at 18:56
  • $\begingroup$ 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 oeis.org $\endgroup$ – Barry Cipra Aug 21 '13 at 19:07
  • 1
    $\begingroup$ 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) $\endgroup$ – Christoph Aug 21 '13 at 19:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Numeri says Reinstate Monica Aug 22 '13 at 1:39
  • $\begingroup$ 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. $\endgroup$ – Christoph Aug 22 '13 at 6:16
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer @Marko! This problem wasn't quite so simple as I thought it would be! :D $\endgroup$ – Numeri says Reinstate Monica Dec 28 '13 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.