2
$\begingroup$

Consider all vectors $(n_1,n_2,\dots , n_{10})$ with $1\le n_i\le 6$.

$A)$ Discounting all permutations of the entries, how many vectors are there which use each number $1,2,\dots,6$ at least once.

$B)$ Let $G$ be the group of symmetries generated by $(n_1,n_2,\dots, n_{10})$ to $(n_{10},n_1,n_2,\dots, n_9)$. Discounting the action of $G$, how many vectors are there which use each number $1,2,\dots, 6$ at least once?

I know this is a Polya's Theory of Counting problem. I don't know to set up the generating function to get the coefficients that I need from the pattern inventory.

$\endgroup$
1
$\begingroup$

There are two possible solutions here, one using the Polya Enumeration Theorem and another one using Burnside's lemma and Stirling numbers of the second kind. The second solution is much more efficient than the first one. The answers are $126$ for the action of the symmetric group and $1643544$ for the cyclic group.

For both solutions we need the cycle indices of the respective groups which are

$$Z(S_{10}) = 1/9\,a_{{9}}a_{{1}}+1/16\,a_{{8}}{a_{{1}}}^{2}+1/42\,a_{{7}}{a_{ {1}}}^{3}+{\frac {a_{{6}}{a_{{1}}}^{4}}{144}}+{\frac {a_{{2}}{a_ {{1}}}^{8}}{80640}}\\+{\frac {a_{{3}}{a_{{1}}}^{7}}{15120}}+{ \frac {{a_{{1}}}^{6}{a_{{2}}}^{2}}{5760}}+{\frac {a_{{4}}{a_{{1} }}^{6}}{2880}}+{\frac {a_{{5}}{a_{{1}}}^{5}}{600}}+{\frac {{a_{{ 1}}}^{4}{a_{{2}}}^{3}}{1152}}+{\frac {{a_{{1}}}^{4}{a_{{3}}}^{2} }{432}}+{\frac {{a_{{1}}}^{2}{a_{{4}}}^{2}}{64}}\\+{\frac {{a_{{1} }}^{2}{a_{{2}}}^{4}}{768}}+{\frac {a_{{1}}{a_{{3}}}^{3}}{162}}+{ \frac {{a_{{2}}}^{3}a_{{4}}}{192}}+{\frac {{a_{{2}}}^{2}{a_{{3}} }^{2}}{144}}+1/48\,{a_{{2}}}^{2}a_{{6}}+{\frac {a_{{2}}{a_{{4}}} ^{2}}{64}}\\+1/16\,a_{{2}}a_{{8}}+{\frac {{a_{{3}}}^{2}a_{{4}}}{72 }}+1/21\,a_{{3}}a_{{7}}+1/24\,a_{{4}}a_{{6}}+{\frac {1}{50}}\,{a _{{5}}}^{2}+1/10\,a_{{10}}\\+{\frac {{a_{{1}}}^{10}}{3628800}}+{ \frac {{a_{{2}}}^{5}}{3840}}+1/24\,a_{{1}}a_{{2}}a_{{3}}a_{{4}}+ {\frac {a_{{1}}{a_{{2}}}^{3}a_{{3}}}{144}}+1/40\,a_{{1}}{a_{{2}} }^{2}a_{{5}}\\+1/14\,a_{{1}}a_{{2}}a_{{7}}+1/18\,a_{{1}}a_{{3}}a_{ {6}}+1/20\,a_{{1}}a_{{4}}a_{{5}}+{\frac {{a_{{1}}}^{2}{a_{{2}}}^ {2}a_{{4}}}{64}}+{\frac {{a_{{1}}}^{2}a_{{2}}{a_{{3}}}^{2}}{72}} \\+1/24\,{a_{{1}}}^{2}a_{{2}}a_{{6}}+1/30\,{a_{{1}}}^{2}a_{{3}}a_{ {5}}+{\frac {{a_{{1}}}^{3}{a_{{2}}}^{2}a_{{3}}}{144}}+{\frac {{a _{{1}}}^{3}a_{{2}}a_{{5}}}{60}}+{\frac {{a_{{1}}}^{3}a_{{3}}a_{{ 4}}}{72}}\\+{\frac {{a_{{1}}}^{5}a_{{2}}a_{{3}}}{720}}+{\frac {{a_ {{1}}}^{4}a_{{2}}a_{{4}}}{192}}+1/30\,a_{{2}}a_{{3}}a_{{5}}$$

and $$Z(C_{10}) = 1/10\,{a_{{1}}}^{10}+1/10\,{a_{{2}}}^{5}+2/5\,{a_{{5}}}^{2}+2/5 \,a_{{10}}.$$

Using a CAS like Maple we can then perform coefficient extraction of all terms in

$$Z(S_{10})(B_1+B_2+\cdots+B_6)$$

and

$$Z(C_{10})(B_1+B_2+\cdots+B_6)$$

that contain all six variables, e.g. from $$[B_1^5 B_2 \cdots B_6] Z(C_{10})(B_1+B_2+\cdots+B_6).$$

We then sum these and set the six variables to one to get the count we are interested in. The substitution follows the standard rule of $a_q = B_1^q + B_2^q + \cdots + B_6^q.$ An excerpt from $Z(C_{10})$ looks like this: $$\cdots +504\,B_{{3}}B_{{4}}{B_{{5}}}^{3}{B_{{6}}}^ {5}+252\,B_{{3}}B_{{4}}{B_{{5}}}^{2}{B_{{6}}}^{6}+72\,B_{{3}}B_{{4} }B_{{5}}{B_{{6}}}^{7}\\+9\,B_{{3}}B_{{4}}{B_{{6}}}^{8}+B_{{3}}{B_{{5} }}^{9}+9\,B_{{3}}{B_{{5}}}^{8}B_{{6}}+36\,B_{{3}}{B_{{5}}}^{7}{B_{{ 6}}}^{2}+84\,B_{{3}}{B_{{5}}}^{6}{B_{{6}}}^{3}\\+126\,B_{{3}}{B_{{5}} }^{5}{B_{{6}}}^{4}+126\,B_{{3}}{B_{{5}}}^{4}{B_{{6}}}^{5}+84\,B_{{3 }}{B_{{5}}}^{3}{B_{{6}}}^{6}\\+36\,B_{{3}}{B_{{5}}}^{2}{B_{{6}}}^{7}+ 9\,B_{{3}}B_{{5}}{B_{{6}}}^{8}+B_{{3}}{B_{{6}}}^{9}\\+{B_{{4}}}^{10}+ {B_{{4}}}^{9}B_{{5}}+{B_{{4}}}^{9}B_{{6}}+5\,{B_{{4}}}^{8}{B_{{5}}} ^{2}+9\,{B_{{4}}}^{8}B_{{5}}B_{{6}}+\cdots$$

This is what the procedures V1 and W1 do. This method is very costly as we must carry out expensive polynomial exponentiations to get the coefficients and coefficients are being computed that do not contribute to the desired result.

A much more efficient approach is to use the Burnside lemma directly. Given a term from the cycle index $Z(S_{10})$ or $Z(C_{10})$ the admissible assignments must be constant on each cycle and in the context of this particular problem all six colors must be present. This means we have a set partition of the cycles into six non-empty sets where each set receives one color. Set partitions are counted by the Stirling numbers of the second kind. Before we conclude we need to take into account that all $720$ permutations of the six colors correspond to a valid assignment. This gives a very efficient algorithm with good time and space complexity parameters (number of operations proportional to the number of terms in the cycle index). The algorithm is implemented in V2 and W2.

The Maple code for these was as follows:

with(combinat);
with(numtheory);

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;


pet_cycleind_cyclic :=
proc(n)
local d, s;

    s := 0;
    for d in divisors(n) do
        s := s + phi(d)*a[d]^(n/d);
    od;

    s/n;
end;


pet_cycleind_symm :=
proc(n)
local p, s;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;


pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), seq(v, k=1..d)];
        cf := cf/v^d;
    od;

    [cf, terml];
end;


V1 :=
proc()
    local sind, res, term;

    sind :=
    pet_varinto_cind(add(cat('B', q), q=1..6),
                     pet_cycleind_symm(10));

    res := 0;

    for term in expand(sind) do
        if nops(indets(term)) = 6 then
            res := res + term;
        fi;
    od;


    subs([seq(cat('B', q)=1, q=1..6)], res);
end;

W1 :=
proc()
    local sind, res, term;

    sind :=
    pet_varinto_cind(add(cat('B', q), q=1..6),
                     pet_cycleind_cyclic(10));

    res := 0;

    for term in expand(sind) do
        if nops(indets(term)) = 6 then
            res := res + term;
        fi;
    od;


    subs([seq(cat('B', q)=1, q=1..6)], res);
end;

V2 :=
proc()
    local ind, term, flat, res;

    ind := pet_cycleind_symm(10);

    res := 0;

    for term in ind do
        flat := pet_flatten_term(term);

        res := res + flat[1]*
        6!*stirling2(nops(flat[2]), 6);
    od;

    res;
end;

W2 :=
proc()
    local ind, term, flat, res;

    ind := pet_cycleind_cyclic(10);

    res := 0;

    for term in ind do
        flat := pet_flatten_term(term);

        res := res + flat[1]*
        6!*stirling2(nops(flat[2]), 6);
    od;

    res;
end;

Addendum 02 Jun 2016. The case of the symmetric group has a simple closed form as seen at this MSE link. In this particular instance we obtain

$$6! \times\frac{1}{10!} \sum_{q=1}^{10} \left[10\atop q\right] {q\brace 6} = 126.$$

Using the Stirling numbers of the first kind to count terms in the cycle index of the symmetric group that consist of $q$ cycles is of course much better than computing all terms of the cycle index.

The closed form for the cyclic group is $$6! \times \frac{1}{10}\sum_{d|10} \varphi(d) {10/d\brace 6} = 1643544.$$

The case of cyclic and dihedral symmetry including Maple code is documented at OEIS A087854 and OEIS A273891.

$\endgroup$

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.