5
$\begingroup$

Let $A$ be a set of objects where $|A|=n$. We want to count all the possible ways that we can arrange these objects into $n$ bags with exactly $n$ objects in each. We can reuse any object, however, no repetition is allowed inside the bags.

With $A=\{a,b,c\}$, for example, $[(a,b,c), (a,b,c), (b,c,a)]$ is a valid outcome.

Obviously there are $(n!)^n$ ways to do this.

Now we want to add two extra constraints:

  • The order of bags is not important.

For example, $[(a,b,c), (a,b,c), (b,c,a)]$ would be identical to $[(b,c,a), (a,b,c), (a,b,c)]$.

  • The label of objects inside the bags do not matter. Only the relative positions are important.

For example, $[(a,b,c), (a,b,c), (b,c,a)]$ would be identical to $[(c,b,a), (c,b,a), (b,a,c)]$ and is identical to $[(a,c,b), (a,c,b), (c,b,a)]$ etc.

Questions are:

  • How many ways can we set these bags given the above constrains ?
  • Is there any algorithm to output all these possible combinations?
$\endgroup$
  • $\begingroup$ I don't understand the sentence about relative positions. Relative to what? $\endgroup$ – Brendan McKay May 18 '14 at 0:57
  • $\begingroup$ Fair enough. Basically changing the labels of objects throughout all the bags will keep the combination similar to what it was before. I think the example underneath is illustrating what I mean. $\endgroup$ – NeoN May 18 '14 at 1:00
  • $\begingroup$ You might get estimates for bounds on the problem by using a couple of models. The first model draws n-1 nonidentity permutations from a bag, so n! - 1 choose n-1. Although this might involve some double counting, it may provide a lower bound. The second model is to choose n-1 out of a multiset of n-1 copies of nonidentity permutations. This will provide an upper bound, but does not take all symmetries into account. Gerhard "Ask Me About System Design" Paseman, 2014.05.17 $\endgroup$ – Gerhard Paseman May 18 '14 at 1:01
  • $\begingroup$ Brendan, I won't interpret relative positions, but I believe that he wants equivalence classes mod Perm A, so that if S is some multiset of permutations of A, then pS is equivalent to S, where pS is the multiset {ps for s in S} and p a permutation of A. Gerhard "Ask Me About Definiton Guessing" Paseman, 2014.05.17 $\endgroup$ – Gerhard Paseman May 18 '14 at 1:05
  • 2
    $\begingroup$ It seems that you want the number of conjugacy classes of multisets of $n$ permutations in $S_n$. (Two multisets are conjugate in $S_n$ if you can consistently relabel the base set $a,b,\ldots$ in one of the multisets to get the other.) This is a hard problem. There might be a formula of sorts using Polya Theory but that's all. $\endgroup$ – Brendan McKay May 18 '14 at 3:05
5
$\begingroup$

First, let's note that there's no reason why the number of ``bags'' should be the same as $|A|$. The problem is nicer if we let the number of bags $m$ be independent of $n$.

As Brendan noted, the problem can be viewed as counting orbits of a certain set under an action of $S_m\times S_n$. However, the action of $S_m$ just reduces counting sequences to counting multisets, so if we can count orbits of multisets in some other way, we don't need this action and we can just count orbits of multisets under an action of $S_n$.

More generally, we could start with a finite group $G$ acting on a set $T$. Then $G$ acts in a natural way on multisets of elements of $T$. We would like to count orbits under this action of multisets of $m$ elements of $T$. We can do this using (the weighted form of) Burnside's lemma.

it is sufficient to count, for each $g\in G$, the number of $m$-multisets fixed by $g$. But a multiset is fixed by $g$ if and only if it is a multiset union of orbits of $g$ on $T$. In our example, $G$ is the symmetric group $S_n$ and $T$ is also $S_n$, and $G$ acts on $T$ by multiplication. The orbits of $g$ are easy to determine, as described below.

Let's look first at the case $n=2$. There are two permutations of $\{1,2\}$, which I'll denote as $\iota=\binom{1\ 2}{1\ 2}$ and $\tau=\binom{1\ 2}{2\ 1}$. The generating function for multisets of these permutations is $1/(1-x)^2$ (where the weight of a multiset of size $j$ is $x^j$) and this is the same as the generating function for multisets fixed by $\iota$. There is only one orbit of $\tau$, which is all of $S_2$, so multisets fixed by $\tau$ have the same number of copies of $\iota$ and $\tau$, and the generating function for these is $1/(1-x^2)$. So by Burnside's lemma, the number of orbits of multisets is $$\frac12\left(\frac{1}{(1-x)^2} +\frac{1}{1-x^2}\right) =\frac{1}{(1-x)(1-x^2)}. $$

In the general case we need to find the generating function for multisets of elements of $S_n$ fixed by a permutation $\pi\in S_n$. A multiset fixed by $\pi$ must be a multiset union of orbits $\pi$ on $S_n$. Let $o(\pi)$ be the order of $\pi$, that is, the least $k$ such that $\pi^k$ is the identity permutation. Then every orbit of $\pi$ on $S_n$ has $o(\pi)$ elements and there are $n!/o(\pi)$ orbits. Thus the generating function for multisets of these orbits, which is the generating function for multisets of elements of $S_n$ fixed by $\pi$, is $$ \frac{1}{(1-x^{o(\pi)})^{n!/o(\pi)}} $$ and thus the generating function for orbits of multisets under the action of $S_n$ is $$\frac{1}{n!} \sum_{\pi\in S_n} \frac{1}{(1-x^{o(\pi)})^{n!/o(\pi)}}.$$ (If $\pi$ has cycles of length $\lambda_1,\dots, \lambda_k$ then $o(\pi)$ is the least common multiple of $\lambda_1,\dots, \lambda_k$.)

Since $o(\pi)$ depends only on the cycle type of $\pi$ we can get a sum with fewer terms by summing over cycle types, which are partitions of $n$. For a partition $\lambda=(\lambda_1, \lambda_2,\dots, \lambda_k)$ of $n$ in which $i$ occurs $m_i$ times as a part, let $z_\lambda=\prod_i i^{m_i}m_i!$, so there are $n!/z_\lambda$ permutations in $S_n$ of cycle type $\lambda$. Let $o(\lambda) = {\rm lcm}(\lambda_1,\dots, \lambda_k)$. Then the generating function may be written $$\sum_{\lambda\vdash n} \frac{1}{z_\lambda(1-x^{o(\lambda)})^{n!/o(\lambda)}}$$ where the sum is over all partitions of $n$. The answer to the OP's original question is the coefficient of $x^n$ in this generating function; here any partitions $\lambda$ with $o(\lambda)>n$ can be ignored.

For $n=3$ the generating function is \begin{multline*} \frac16\left(\frac{1}{(1-x)^6} +\frac{3}{(1-x^2)^3}+\frac{2}{(1-x^3)^2} \right) = \frac{1+{x}^{2}+3{x}^{3}+5{x}^{4}+{x}^{5}+{x}^{6}}{(1-x)(1-x^2)^3(1-x^3)^2}\\ = 1+x+5{x}^{2}+10{x}^{3}+24{x}^{4}+42{x}^{5}+83{x}^{6}+132{x}^{7}+\cdots \end{multline*} (OEIS sequence A037240). The coefficient of $x^3$ is 10, which agrees with bof.

For $n=4$ the generating function is \begin{multline*} \frac1{24} \left( 1-x \right) ^{-24}+\frac38 \left( 1-{x}^{2} \right) ^{-12} +\frac13 \left( 1-{x}^{3} \right) ^{-8}+\frac14 \left( 1-{x}^{4} \right) ^ {-6}\\ =1+x+17{x}^{2}+111{x}^{3}+762{x}^{4}+4095{x}^{5}+19941{x}^{6} +84825{x}^{7}+\cdots \end{multline*} and for $n=5$ it is \begin{multline*} \frac {1}{120} \left( 1-x \right) ^{-120}+{\frac {5}{24}} \left( 1-{x}^{2} \right) ^{-60}+\frac16 \left( 1-{x}^{3} \right) ^{-40} +\frac16 \left( 1-{x}^{6} \right) ^{-20}\\ +\frac14 \left( 1-{x}^{4} \right) ^{-30}+\frac15 \left( 1-{x}^{5} \right) ^{-24}\\ =1+x+73{x}^{2}+2467{x}^{3}+76044{x}^{4}\\+1876255{x}^{5}+39096565 {x}^{6}+703593825{x}^{7}+\cdots \end{multline*}

The first few values of the numbers $a_n$ corresponding to the OP's original problem are $a_1=1$, $a_2=2$, $a_3=10$, $a_4 = 762$, $a_5=1876255$, $a_6=274382326290$, $a_7=3265588553925722827, \dots$ It's easy to go much further ($n=30$ takes just over a second in Maple) but the numbers get very big quickly.

A different formula for counting orbits of multisets (useful in some other problems, but more complicated for this problem) is described here and used here. Some related papers are Marko V. Jarić and Joseph L. Birman, New algorithms for the Molien function. J. Mathematical Phys. 18 (1977), no. 7, 1456-1458, and Marko V. Jarić and Joseph L. Birman, Calculation of the Molien generating function for invariants of space groups. J. Mathematical Phys. 18 (1977), no. 7, 1459-1465. The second of these papers contains the generating function for $n=3$ given above, though I'm not sure that the interpretation is the same.

$\endgroup$
  • $\begingroup$ Ira, there is no need for $m = n $ as you mentioned. This assumption was put just to make the problem (perhaps) easier. $\endgroup$ – NeoN May 18 '14 at 18:13
  • $\begingroup$ Thanks Ira. My background is not quite close this so I am gonna need to read this a few times to fully digest the analysis. $\endgroup$ – NeoN May 18 '14 at 19:21
2
$\begingroup$

Write the permutations as the rows of a matrix. For example $[(a,b,c),(a,c,b),(b,c,a)]$ becomes $$\begin{matrix} a & b & c\\ a & c & b\\ b & c & a\end{matrix}~~.$$ So far we just have an $n\times n$ matrix whose rows are permutations. Now we have some equivalence rules:

(1) permuting the rows gives an equivalent matrix
(2) permuting the names of the symbols gives an equivalent matrix

Since (1) and (2) are a bit dissimilar, we can instead write the inverses of the permutations in each row (identifying the columns in order as $a,b,c,\ldots\,$). In this example: $$\begin{matrix} a & b & c\\ a & c & b\\ c & a & b\end{matrix}~~.$$ Now the equivalence rules are nicer:

(1) permuting the rows gives an equivalent matrix
(2') permuting the columns gives an equivalent matrix

We can consider this situation as a representation of the permutation group $S_n\times S_n$: the points are the matrices with permutations in each row, and $(g,h)\in S_n\times S_n$ acts by applying $g$ to the columns and $h$ to the rows. The enumeration question is to determine the number of orbits of this permutation group. The standard method for doing this is Pólya's Theorem, which is a sort of Burnside's Lemma on steroids, but it would be some work and the answer might be a horrible summation. The similar problem when the rows are 0-1 vectors rather than permutations is solved here. I'm not so good at this sort of calculation, but if Ira Gessel comes by he might tell us how to do it.

Some ideas don't work: to borrow terminology from Latin squares, we can call the matrix reduced if the first row and first column are in numerical order. Each orbit contains at least one reduced matrix, but the number of reduced matrices in an orbit varies so counting reduced matrices doesn't help much. Something similar works, see below.

Standard computational methods of listing orbit representatives would work here but will run out of steam quickly as the number of orbits is at least $(n!)^{n-2}$. For $n\le 5$ it would be easy, for $n=6$ a big computation, and for $n=7$ exhaustive generation is out of the question. Finding the count for slightly larger $n$ is possible since Burnside's lemma can be applied by computer: it is the sum over $(g,h)\in S_n\times S_n$ of some expression that depends only on the cycle lengths of $g$ and $h$. Since we know how many permutations have a given multiset of cycle lengths, we can write it as a sum of some expression over pairs of partitions of $n$.

The fact that rows are permutations gives this generation algorithm: Given matrix $A$, for $1\le i\le n$ define $A^{(i)}$ like this: starting with $A$, swap row $i$ with row 1, permute the colums so that row 1 is the identity, permute rows $2,\ldots,n$ into lexicographic order. Define $\hat A$ to be the lexicographically largest of $A^{(1)},\ldots,A^{(n)}$. I claim that $\hat A=\hat B$ iff $A$ and $B$ are equivalent. Therefore the matrices $A$ such that $\hat A=A$ are a set of distinct orbit representatives.

$\endgroup$
  • $\begingroup$ Brendan, thanks for your input. Although I am having a problem understanding the first part with the inverse of permutations. In the example, I cannot see how you get to the new matrix. You are right about computation. This is exactly where the motivation for this problem comes from. I was not able to go over $n>6$, so I have been trying to use these sort of symmetries to reduce the counting. $\endgroup$ – NeoN May 18 '14 at 18:10
0
$\begingroup$

With the relative order constraint, it would seem that the number of permutations is back to n!.

$\endgroup$
  • $\begingroup$ Well no. Doing this by hand shows that n=3 has more than 6 permutations. $\endgroup$ – NeoN May 18 '14 at 5:28
  • $\begingroup$ You are correct. It should be n!*n. $\endgroup$ – Brian Megquier May 18 '14 at 6:56

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.