3
$\begingroup$

I know from previous MSE posts that the number of circular permutations of of $n$ objects where $n_1$ objects are identical of one kind, $n_2$ objects are .. and $n_m$ objects are of one kind is given by $$\frac{1}{n}\,\sum_{d\mid\gcd(n_1,n_2,\ldots,n_m)}\,\phi(d)\,\binom{n/d}{n_1/d,n_2/d,\ldots,n_m/d}$$

where $\phi(d)$ is the Euler's totient function (the proof uses Polya's enumeration theorem).

Q. But what is the the number of free circular permutations of n objects where $n_1$ objects are identical of one kind, $n_2$ objects are .. and $n_m$ objects are of one kind?

A free circular permutation is one which has rotational and reflectional symmetry; so the symmetry group is the dihedral group $D_n$ instead of the cyclic group $C_n$. Note that if all the objects were distinct, then the number of free circular permutations is simply $\frac{(n-1)!}{2}$ if $n > 2$ and $1$ otherwise, but I dont know enough abstract algebra to use Polya's enumeration theorem.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Here are some ideas that the reader is invited to extend to a complete solution. Application of PET to necklaces and bracelets requires the cycle indices of the cyclic and the dihedral group. For the first one we have the cycle index of the cyclic group:

$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$

For second one we have the cycle index of the dihedral group

$$Z(D_n) = \frac{1}{2} Z(C_n) + \begin{cases} \frac{1}{2} a_1 a_2^{(n-1)/2} & n \text{ odd} \\ \frac{1}{4} \left( a_1^2 a_2^{n/2-1} + a_2^{n/2} \right) & n \text{ even.} \end{cases}$$

Those dihedral symmetries are reflections i.e. flips of the bracelet. They must fix one slot if $n$ is odd and we can reflect over two types of axes when $n$ is even, with the axis of reflection passing through opposite slots ($n/2$ permutations) or opposite edges (another $n/2$ permutations). The desired quantities are then obtained by making the Polya substitution into the cycle index and extracting the coefficient. This is written as

$$[N_1^{n_1} N_2^{n_2} \cdots N_m^{n_m}] Z(C_n; N_1+ N_2+ \cdots +N_m)$$

and

$$[N_1^{n_1} N_2^{n_2} \cdots N_m^{n_m}] Z(D_n; N_1+ N_2+ \cdots +N_m).$$

where $n= n_1 + n_2 + \cdots + n_m$.

The PET substitution is given by

$$a_d = N_1^d + N_2^d + \cdots + N_m^d$$

which arises from Burnside (an assignment of colors is fixed by a permutation if it is constant on the cycles which means a cycle of length $d$ makes a contribution of $N_1^d + N_2^d + \cdots + N_m^d$).

Now for the cyclic group we get

$$[N_1^{n_1} N_2^{n_2} \cdots N_m^{n_m}] \frac{1}{n} \sum_{d|n} \varphi(d) (N_1^d+N_2^d+\cdots+N_m^d)^{n/d}.$$

Clearly when we look at the sum term we will only produce multiples of $d$ in the exponents so $d$ must divide all of $n_1,n_2,\ldots,n_m.$ We then get from the multinomial theorem

$$\frac{1}{n} \sum_{d|\gcd(n_1, n_2, \ldots, n_m)} \varphi(d) {n/d\choose n_1/d, n_2/d, \ldots, n_m/d}.$$

The dihedral group contributes some extra terms which require suitable casework, as we shall see in the following examples.

First example

Say we have three colors, with three instances of the first and the second and six of the third. We get from the cyclic component

$$\frac{1}{12} [N_1^3 N_2^3 N_3^6] (\varphi(1) (N_1^1 + N_2^1 + N_3^1)^{12} + \varphi(3) (N_1^3 + N_2^3 + N_3^3)^4) \\ = \frac{1}{12} \left({12\choose 3,3,6} + 2 {4\choose 1,1,2}\right) = 1542.$$

The dihedral component gives (here $n$ is even)

$$\frac{1}{4} [N_1^3 N_2^3 N_3^6] \left((N_1+N_2+N_3)^2 (N_1^2+N_2^2+N_3^2)^5 + (N_1^2+N_2^2+N_3^2)^6\right) \\ = \frac{1}{4} 2 [N_1^2 N_2^2 N_3^6] (N_1^2+N_2^2+N_3^2)^5 \\ = \frac{1}{2} [N_1 N_2 N_3^3] (N_1+N_2+N_3)^5 = \frac{1}{2} {5\choose 1,1,3} = 10.$$

Collecting the two components gives

$$\frac{1}{2} 1542 + 10 = 781.$$

Second example

We take three colors, with three instances of the first and six of the second and third. We get from the cyclic component

$$\frac{1}{15} [N_1^3 N_2^6 N_3^6] (\varphi(1) (N_1^1 + N_2^1 + N_3^1)^{15} + \varphi(3) (N_1^3 + N_2^3 + N_3^3)^5) \\ = \frac{1}{15} \left({15\choose 3,6,6} + 2 {5\choose 1,2,2}\right) = 28032.$$

The dihedral component gives (here $n$ is odd)

$$\frac{1}{2} [N_1^3 N_2^6 N_3^6] (N_1+N_2+N_3) (N_1^2+N_2^2+N_3^2)^7 \\ = \frac{1}{2} [N_1^2 N_2^6 N_3^6] (N_1^2+N_2^2+N_3^2)^7 \\ = \frac{1}{2} [N_1 N_2^3 N_3^3] (N_1+N_2+N_3)^7 = \frac{1}{2} {7\choose 1,3,3} = 70.$$

Collect the two components to get

$$\frac{1}{2} 28032 + 70 = 14086.$$

Third example

Note that when all $n_q$ are even we get from $\frac{1}{4} a_1^2 a_2^{n/2-1}$ the contribution

$$\frac{1}{4} [N_1^{n_1} N_2^{n_2} \cdots N_m^{n_m}] (N_1+N_2+\cdots+N_m)^2 (N_1^2+N_2^2+\cdots+N_m^2)^{n/2-1} \\ = \frac{1}{4} \sum_{q=1}^m [N_1^{n_1} \cdots N_q^{n_q-2} \cdots N_m^{n_m}] (N_1^2+N_2^2+\cdots+N_m^2)^{n/2-1} \\ = \frac{1}{4} \sum_{q=1}^m {n/2-1\choose n_1/2, n_2/2, \ldots, n_q/2-1, \ldots n_m/2} \\ = \frac{1}{4} {n/2\choose n_1/2, n_2/2, \ldots, n_q/2, \ldots n_m/2} \frac{1}{n/2} \sum_{q=1}^m n_q/2 \\ = \frac{1}{4} {n/2\choose n_1/2, n_2/2, \ldots, n_m/2}.$$

Of course the term $\frac{1}{4} a_2^{n/2}$ contributes as well and we get

$$\frac{1}{4} [N_1^{n_1} N_2^{n_2} \cdots N_m^{n_m}] (N_1^2+N_2^2+\cdots+N_m^2)^{n/2} = \frac{1}{4} {n/2\choose n_1/2, n_2/2, \ldots n_m/2}$$

so that adding everything we obtain

$$\frac{1}{2} {n/2\choose n_1/2, n_2/2, \ldots, n_m/2}.$$

For example with four instances each of the first two colors and six of the third we get from the cyclic component

$$\frac{1}{14} [N_1^4 N_2^4 N_3^6] (\varphi(1) (N_1^1 + N_2^1 + N_3^1)^{14} + \varphi(2) (N_1^2 + N_2^2 + N_3^2)^7) \\ = \frac{1}{14} \left({14\choose 4,4,6} + {7\choose 2,2,3}\right) = 15030.$$

The dihedral component yields $\frac{1}{2} {7\choose 2,2,3} = 105$ for an end result answer of

$$\frac{1}{2} 15030 + 105 = 7620.$$

$\endgroup$
2
  • $\begingroup$ I did the computation for some terms (please verify): If $n$ is odd, $$a_1 a_2^{\frac{n-1}{2}} = \begin{cases} \binom{ \frac{n-1}{2}}{ \frac{n_1 - 1}{2} , \frac{n_2}{2} .. \frac{n_m}{2} } &\text{Exactly one of $n_1, n_2, .. n_m$ is odd; say $n_1$ is odd} \\ 0 &\text{o.w.} \end{cases}$$ $\endgroup$ Commented Jan 22 at 17:10
  • $\begingroup$ $n$ is even: Use $a_1^2 = a_2 + 2\sum_{i < j} N_i N_j$, thus $a_1^2 a_2^{\frac{n}{2} - 1} + a_2^{\frac{n}{2}} = 2(a_2^{\frac{n}{2}} + a_2^{\frac{n}{2} - 1} \cdot \sum_{i < j} N_i N_j )$. Then: $$ a_1^2 a_2^{\frac{n}{2} - 1} + a_2^{\frac{n}{2}} = \begin{cases} 2\binom{ \frac{n}{2} }{ \frac{n_1}{2}, \frac{n_2}{2} .. \frac{n_m}{2} } &\text{if all of $n_1, n_2, .. n_m$ are even} \\ 2\binom{ \frac{n}{2} - 1}{ \frac{n_1-1}{2}, \frac{n_2-1}{2} .. \frac{n_m}{2} } &\text{if exactly $2$ of $n_1, n_2, .. n_m$ are odd; say $n_1$ and $n_2$} \\ 0 &o.w. \end{cases}$$ $\endgroup$ Commented Jan 22 at 17:24

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.