Coloring of rectangle $3\times 4$

Question

We are colorings fields of rectangle with $3$ rows and $4$ columns in use of $2$ colors. Two colorings are the same if one is created from second in use any permutation of rows and cyclic shift of columns. Find number of different colorings, in which each color is used $6$ times.

A = \begin{bmatrix} a & a & a \\ a & a & a \\ b & b & b \\ b & b & b \end{bmatrix} $A^T$ give me $1$ coloring. A = \begin{bmatrix} a & a & a \\ a & a & b \\ a & b & b \\ b & b & b \end{bmatrix} $A^T$ give me $1$ coloring. A = \begin{bmatrix} a & a & b \\ a & a & b \\ a & a & b \\ b & b & b \end{bmatrix} $A^T$ give me $1$ coloring. A = \begin{bmatrix} a & a & b \\ a & a & b \\ a & b & b \\ a & b & b \end{bmatrix}

$A^T$ give me $1$ coloring. etc... But is there any smarter way to do this? Writing all combinations is really slow and will cause an mistake so... I would like to see how to solve tasks like this when we are coloring structure with additional conditions.

Answer 1

Here is a computational contribution that treats the problem for matrices with dimenstion $n$ rows by $m$ columns, with the symmetric group permuting the rows and the cyclic group permuting the columns. As pointed out this problem can be solved using the Polya Enumeration Theorem. We just need to compute the cycle index of the group acting on the slots of the matrix.

These cycle indices are easy to compute and we do not need to iterate over all $n!\times m$ pairs of permutations (acting on rows and columns) but instead it is sufficient to iterate over pairs of terms from the cycle index $Z(S_n)$ of the symmetric group $S_n$ and the cycle index $Z(C_m)$ of the cyclic group according to their multiplicities to obtain the cycle index $Z(Q_{n,m})$ of the combined action on rows and columns. The number of terms here is the much better count of the number of partitions of $n$ times $m$ (upper bound).

Now for a pair of cycles, one of length $l_1$ from a row permutation $\alpha$ and another of length $l_2$ from a column permutation $\beta$ their contribution to the disjoint cycle decomposition product for $(\alpha,\beta)$ in the cycle index $Z(Q_{n,m})$ is by inspection $$a_{\mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / \mathrm{lcm}(l_1, l_2)} = a_{\mathrm{lcm}(l_1, l_2)}^{\gcd(l_1, l_2)}.$$

The algorithm now becomes very simple -- iterate over pairs of terms as described above, collect the contribution from each pair of cycles and add it to the cycle index being computed.

This gives the following cycle indices:

$$Z(Q_{3,4}) = 1/24\,{a_{{1}}}^{12}+1/6\,{a_{{2}}}^{6}+1/3\,{a_{{4}} }^{3}\\+1/8\,{a_{{1}}}^{4}{a_{{2}}}^{4}+1/12\,{a_{{3}}} ^{4}+1/12\,{a_{{6}}}^{2}+1/6\,a_{{12}}$$

and

$$Z(Q_{4,3}) = {\frac {{a_{{1}}}^{12}}{72}}+1/4\,{a_{{3}}}^{4}+1/12 \,{a_{{1}}}^{6}{a_{{2}}}^{3}+1/6\,{a_{{3}}}^{2}a_{{6} }\\+1/9\,{a_{{1}}}^{3}{a_{{3}}}^{3}+1/24\,{a_{{2}}}^{6} +1/12\,{a_{{6}}}^{2}+1/12\,{a_{{4}}}^{3}+1/6\,a_{{12}}.$$

The PET-substituted cycle indices are

$$Z(Q_{3,4}; A+B) = {A}^{12}+{A}^{11}B+5\,{A}^{10}{B}^{2}+12\,{A}^{9}{B}^ {3}\\+28\,{A}^{8}{B}^{4}+38\,{A}^{7}{B}^{5}+48\,{A}^{6} {B}^{6}+38\,{A}^{5}{B}^{7}+28\,{A}^{4}{B}^{8}\\+12\,{A} ^{3}{B}^{9}+5\,{A}^{2}{B}^{10}+A{B}^{11}+{B}^{12}$$

and

$$Z(Q_{4,3}; A+B) = {A}^{12}+{A}^{11}B+3\,{A}^{10}{B}^{2}+8\,{A}^{9}{B}^{ 3}\\+14\,{A}^{8}{B}^{4}+19\,{A}^{7}{B}^{5}+24\,{A}^{6}{ B}^{6}+19\,{A}^{5}{B}^{7}\\+14\,{A}^{4}{B}^{8}+8\,{A}^{ 3}{B}^{9}+3\,{A}^{2}{B}^{10}+A{B}^{11}+{B}^{12}.$$

We thus have the desired answer that for a matrix that is $3\times 4$ we obtain with $A$ and $B$ each used six times

$$\bbox[5px,border:2px solid #00A000]{48}$$

colorings and for a $4\times 3$,

$$\bbox[5px,border:2px solid #00A000]{24.}$$

This is the Maple code for this computation, which also includes an enumeration routine to verify the output from PET for small values of the parameters.

with(numtheory);

pet_cycleind_cyclic :=
n -> add(phi(d)*a[d]^(n/d), d in divisors(n))/n;


pet_cycleind_symm :=
proc(n)
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_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_mat :=
proc(n, m)
option remember;
local rowind, colind, cind, term_a, term_b, v_a, v_b,
    len_a, len_b, inst_a, inst_b, p;

    cind := 0;

    if n=1 then
        return pet_cycleind_cyclic(m);
    else
        rowind := pet_cycleind_symm(n);
    fi;

    if m=1 then
        return pet_cycleind_symm(n);
    else
        colind := pet_cycleind_cyclic(m);
    fi;

    for term_a in rowind do
        for term_b in colind do
            p := 1;
            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    p := p*a[lcm(len_a, len_b)]
                    ^(gcd(len_a, len_b)*inst_a*inst_b);
                od;
            od;

            cind := cind +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    cind;
end;

v :=
proc(n, m)
    option remember;
    local cind, vars, sbl;

    cind := pet_cycleind_mat(n, m);

    vars := indets(cind);
    sbl := [seq(v=2, v in vars)];

    subs(sbl, cind);
end;

colors_AB :=
proc(n, m)
    option remember;
    local cind;

    cind := pet_cycleind_mat(n, m);

    expand(pet_varinto_cind(A+B, cind));
end;

with(combinat);

colors_AB_verif :=
proc(n, m)
option remember;
local idx, d, mat, pmat, orbit, orbits,
    gf, cnt, rperm, c, cperm;

    orbits := table();

    for idx from 2^(n*m) to 2^(n*m+1)-1 do
        d := convert(idx, base, 2)[1..n*m];

        mat := [seq([seq(d[p*m+q+1], q=0..m-1)],
                    p=0..n-1)];

        orbit := [];

        rperm := firstperm(n);
        while type(rperm, `list`) do
            for c to m do
                cperm :=
                [seq(p, p=c..m), seq(p, p=1..c-1)];

                pmat :=
                [seq([seq(mat[rperm[p]][cperm[q]],
                          q=1..m)], p=1..n)];

                orbit := [op(orbit), pmat];
            od;

            rperm := nextperm(rperm);
        od;

        orbits[sort(orbit)[1]] := 1;
    od;

    gf := 0;

    for orbit in [indices(orbits, 'nolist')] do
        cnt := add(add(orbit[p][q], p=1..n), q=1..m);
        gf := gf + A^cnt * B^(n*m-cnt);
    od;

    gf;
end;

This MSE Link has a very similar PET computation.