2
$\begingroup$

We have a $5\times 5$ square table and $n$ different colours. We cut out $2\times 2$ squares from all vertex and remains $9$ unit squares. We will paint $9$ squares with $n$ colours. Some squares can be same colour. If the rotatings with respect to center of the table or the reftections of hortizonal symmetry axis, vertical symmetry axis, diagonals are indetical coloring, then how many are there distinc colouring (in terms of $n$) ?

For example $n=7$ and colours are $1,2,3,4,5,6,7$. We may not use the colors $6$, $7$. Some identical colorings:

$ \begin{array}{|c|c|c|c|c|} \hline & & 1 & & \\ \hline & & 2 & & \\ \hline 4& 2 & 2 & 2 & 5 \ \\ \hline & & 2 & & \\ \hline & & 3 & & \\ \hline \end{array} \to \text{symmetry w.r.t vertical axis}\to \begin{array}{|c|c|c|c|c|} \hline & & 1 & & \\ \hline & & 2 & & \\ \hline 5& 2 & 2 & 2 & 4 \ \\ \hline & & 2 & & \\ \hline & & 3 & & \\ \hline \end{array} $

$ \begin{array}{|c|c|c|c|c|} \hline & & 1 & & \\ \hline & & 2 & & \\ \hline 4& 2 & 2 & 2 & 5 \ \\ \hline & & 2 & & \\ \hline & & 3 & & \\ \hline \end{array} \to \text{rotate }90^\circ \text{ positive direction }\to \begin{array}{|c|c|c|c|c|} \hline & & 5 & & \\ \hline & & 2 & & \\ \hline 1& 2 & 2 & 2 & 3 \ \\ \hline & & 2 & & \\ \hline & & 4 & & \\ \hline \end{array} $

$\endgroup$
  • 1
    $\begingroup$ The symmetry here is dihedral $D_4.$ Factor the eight permutations to obtain the cycle index and evaluate at $n.$ Why is it we may not use six and seven? $\endgroup$ – Marko Riedel Apr 10 '17 at 21:08
  • 1
    $\begingroup$ I think that means simply that we are allowed to skip them. $\endgroup$ – Phira Apr 10 '17 at 21:10
  • $\begingroup$ If you want, all $9$ squares are same color. If you want you can use all colours. $\endgroup$ – scarface Apr 10 '17 at 21:11
2
$\begingroup$

Computing the cycle index we get from the four rotations

$$a_1^9 + 2 a_1 a_4^2 + a_1 a_2^4$$

and from the horizontal / vertical reflections

$$2 a_1^5 a_2^2$$

and from the diagonal reflections:

$$2 a_1 a_2^4.$$

The cycle index becomes

$$Z(G) = \frac{1}{8} \left(a_1^9 + 2 a_1 a_4^2 + 2 a_1^5 a_2^2 + 3 a_1 a_2^4\right).$$

This yields for colorings with at most $N$ colors the form (here we apply Burnside as PET is not needed and we simply note that we have $N$ choices for coloring a cycle, where the color must be constant on the cycle, e.g. $a_1^5 a_2^2$ has seven cycles and contributes $N^7$)

$$\frac{1}{8} ( N^9 + 2 N^3 + 2 N^7 + 3 N^5 )$$

which is the sequence

$$1, 110, 3105, 37264, 264875, 1332666, 5256475, \\ 17313920, 49645629, 127537750, \ldots$$

The following Perl script will compute the first five entries of this sequence.

#! /usr/bin/perl -w
#


MAIN : {
    my $mx = shift || 2;

    my @src =
        ([-2 ,0], [-1, 0], [0, 0], [1, 0], [2, 0],
         [0, -2], [0, -1], [0, 1], [0, 2]);

    my %coord2pos;

    for(my $pos = 0; $pos < 9; $pos++){
        $coord2pos{join('|', @{ $src[$pos]})} = $pos;
    }

    my @refl =
        (sub { - $_->[0], $_->[1]  },
         sub { $_->[0], - $_->[1]  },
         sub { $_->[1], $_->[0]  },
         sub { - $_->[1], - $_->[0] });

    my @res;

    for(my $n=1; $n <= $mx; $n++){
        my %orbits;

        for(my $idx = $n ** 9; 
            $idx < 2*($n ** 9); $idx++){
            my ($idxit, @digits) = ($idx);

            for(my $pos = 0; $pos < 9; $pos++){
                my $d = $idxit % $n;

                push @digits, $d;
                $idxit = ($idxit - $d) / $n;
            }

            my %orbit;

            my @data = @src;
            for(my $rot = 0; $rot < 4; $rot++){
                my @perm = 
                    map { $digits[$coord2pos{join('|', @$_)}] }
                @data;

                my $orbstr = join('-', @perm);
                $orbit{$orbstr} = 1;

                @data =
                    map { [ $_->[1], - $_->[0] ] }
                @data;
            }

            for(my $rfx = 0; $rfx < 4; $rfx++){
                my @perm = 
                    map { 
                        my @transf = &{ $refl[$rfx] }($_);
                        $digits[$coord2pos{join('|', @transf)}] }
                @src;

                my $orbstr = join('-', @perm);
                $orbit{$orbstr} = 1;
            }

            my $repr = (sort(keys %orbit))[0];
            $orbits{$repr} = 1;
        }

        push @res, scalar(keys %orbits);
    }

    print join(', ', @res);
    print "\n";

    1;
}

We can also answer the question concerning colorings with exactly $N$ colors. Call the colorings with at most $N$ colors $M_N.$ The statistic for an exact number is found by inclusion-exclusion. The nodes $P$ of the poset that we use represent sets of colors and include all configurations that use some subset thereof. A coloring with exactly $p$ colors is included in all nodes that are a superset of these colors. With the weight of a node being given by $(-1)^{N-|P|}$ we get for $p\lt N$ the total weight by choosing the extra colors that join the $p$ colors

$$\sum_{q=0}^{N-p} {N-p\choose q} (-1)^{N-(p+q)} = (-1)^{N-p} \sum_{q=0}^{N-p} {N-p\choose q} (-1)^{q} = 0.$$

On the other hand when $p=N$ these configurations are included only in the node $P$ that includes all $N$ colors with weight $(-1)^{N-N} = 1.$ These are precisely the right weights and we find

$$Q_N = \sum_{p=0}^N {N\choose p} (-1)^{N-p} M_p.$$

This yields the finite sequence

$$1, 108, 2778, 25500, 108510, 241920, \\ 292320, 181440, 45360,0,\ldots$$

which is finite because with nine available slots we can place at most nine different colors. The value $108$ represents the two monochrome colorings being removed. With nine colors all orbits have the same size namely eight for the eight permutations and indeed we obtain $9!/8 = 45360.$

$\endgroup$
  • $\begingroup$ You're great! Thanks for your efforts. $\endgroup$ – scarface Apr 11 '17 at 10:07

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.