3
$\begingroup$

we colored vertices of a hexagon convex by three different colors ; such that every color appears exactly only two times in the vertices . Find the number of possibilities in order to get every vertice of this hexagon colored such that any two neighboring points have distinct colors.

The answer must be either 4 or 5.

Can we generalize the solution to a problem like this? we colored vertices of a 2n-gon convex by n different colors ; such that every color appears exactly only two times in the vertices . Find the number of possibilities in order to get every vertice of this convex colored such that any two neighboring points have distinct colors.

please post some hints. I don't want actually a full solution.

$\endgroup$
  • 1
    $\begingroup$ What does "...every top of this hexagon..." mean? $\endgroup$ – N. Shales Mar 30 '17 at 9:15
  • $\begingroup$ top = vertice , sorry , this is my third year learning English $\endgroup$ – Omar Sehlouli Mar 30 '17 at 9:17
  • $\begingroup$ No problem, I understand now. There is a general method that uses generating functions for the cycle index of such a combinatorial "necklace". $\endgroup$ – N. Shales Mar 30 '17 at 9:22
  • $\begingroup$ thanks , I'll try to search this "necklace" $\endgroup$ – Omar Sehlouli Mar 30 '17 at 9:33
  • $\begingroup$ I didn't find enough explanation . any good pdf / website explaining "necklace"? $\endgroup$ – Omar Sehlouli Mar 30 '17 at 9:36
2
$\begingroup$

We present the five non-isomorphic proper colorings of the hexagon with two instances of three different colors under rotational symmetry for the reader to peruse in retracing the symmetries.

Coloring the hexagon

The Maple code for this was as follows.

with(combinat);

PLOTCIRCNOADJ3 :=
proc()
local n, src, neckl, pos, perm, orbits, orbit, uniqorbs,
    nxt, loc, fd, current, vert1, vert2,
    line, prolog, rot, colors, bbox;

    orbits := table();

    n := 3;
    src := [seq(q, q=1..n), seq(q, q=1..n)];

    for perm in permute(src) do
        neckl := [op(perm), perm[1]];

        for pos to 2*n do
            if neckl[pos] = neckl[pos+1] then
                break;
            fi;
        od;

        if pos = 2*n+1 then
            orbit := [];

            for rot to 2*n do
                nxt :=
                [seq(perm[q], q=rot..2*n),
                 seq(perm[q], q=1..rot-1)];
                orbit := [op(orbit), nxt];
            od;

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

    od;

    uniqorbs := [indices(orbits, 'nolist')];

    fd := fopen(`noniso-circnoadj3.ps`, WRITE);

    bbox := [120, 600];

    prolog :=
    ["%!PS-Adobe-1.0",
     "%%Creator: Marko Riedel",
     "%%Title: graph orbits",
     sprintf("%%%%BoundingBox: 0 0 %d %d", bbox[1], bbox[2]),
     "%%Pages: 1",
     "%%EndComments"];

    for line in prolog do
        fprintf(fd, "%s\n", line);
    od;

    fprintf(fd, "%%Page 1 1\n\n");

    colors :=
    [[1,0,0], [0,0,1], [1,1,0]];

    fprintf(fd, "8 setlinewidth 0 0.72 0 setrgbcolor\n");
    fprintf(fd, "0 0 moveto %d 0 lineto %d %d lineto\n",
            bbox[1], bbox[1], bbox[2]);
    fprintf(fd, "0 %d lineto closepath stroke\n",
           bbox[2]);

    fprintf(fd, "0.05 setlinewidth 0 setgray\n");

    fprintf(fd, "30 30 scale\n");

    for current to nops(uniqorbs) do
        fprintf(fd, "gsave\n");
        fprintf(fd, "%f %f translate\n",
                2, 2+4*(current-1));

        for pos from 0 to 5 do
            loc := exp(2*Pi*I*pos/6);
            vert1 := [Re(loc), Im(loc)];

            loc := exp(2*Pi*I*(pos+1)/6);
            vert2 := [Re(loc), Im(loc)];

            fprintf(fd, "%f %f moveto\n",
                   vert1[1], vert1[2]);
            fprintf(fd, "%f %f lineto\n",
                   vert2[1], vert2[2]);

            fprintf(fd, "closepath stroke\n");

            fprintf(fd, "gsave\n");

            fprintf(fd, "%f %f translate\n",
                    (vert1[1]+vert2[1])/2,
                    (vert1[2]+vert2[2])/2);

            fprintf(fd, "0.2 0.2 scale\n");

            fprintf(fd, "%f rotate\n",
                    90 + (pos-1)*60);

            fprintf(fd, "-0.5 0 moveto\n");
            fprintf(fd, "0.5 0 lineto\n");
            fprintf(fd, "0 2 lineto\n");

            fprintf(fd, "closepath fill\n");

            fprintf(fd, "grestore\n");
        od;

        for pos to 6 do
            loc := exp(2*Pi*I*(pos-1)/6);
            vert1 := [Re(loc), Im(loc)];

            fprintf(fd, "%f %f %f setrgbcolor\n",
                   colors[uniqorbs[current][pos]][1],
                   colors[uniqorbs[current][pos]][2],
                   colors[uniqorbs[current][pos]][3]);
            fprintf(fd, "%f %f 0.24 0 360 arc\n",
                    vert1[1], vert1[2]);
            fprintf(fd, "fill\n");


            fprintf(fd, "0 0 0 setrgbcolor\n");
            fprintf(fd, "%f %f 0.24 0 360 arc\n",
                    vert1[1], vert1[2]);
            fprintf(fd, "stroke\n");
        od;

        fprintf(fd, "grestore\n");
    od;


    fprintf(fd, "showpage\n");
    fclose(fd);

    true;
end;
$\endgroup$
1
$\begingroup$

First hint.

Consult this MSE link to learn how a closely related problem was solved.

Second hint.

There is a Perl script that computes the first six proper colorings of an $2n$-gon using two instances of $n$ different colors, with rotational symmetries being taken into account and not being taken into account. The data that were obtained go like this: for no symmetries we find

$$0, 2, 24, 744, 35160, 2394720, \ldots$$

and with rotational symmetries taken into account

$$0, 1, 5, 96, 3528, 199620, \ldots $$

The reader may use these to check their computational results.

Third hint.

The relevant cycle index is

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

Can you determine the number of proper colorings fixed by each shape of permutation and apply Burnside? There are only three cases, a trivial one, one that can be solved by inspection and one that yields to a simple argument by inclusion-exclusion. Substitute these into the cycle index to obtain the second sequence, you will have encountered the first one at this point. You should now have a simple formula that lets you compute enough of these two sequences to qualify for a query of / a new entry in the OEIS, where it appears the second one is not included yet. The first one provides a particularly relevant entry.

For consultation.

The Perl script goes like this.

#! /usr/bin/perl -w
#

sub choose2n {
    my ($n, $slots, $sofar, $func, @fargs) = @_;
    my $len = scalar( @{ $sofar } );

    if($len == $n){
        my @data = (0) x (2*$n);

        for(my $val = 0; $val < $n; $val++){
            $data[$sofar->[$val]->[0]] = $val;
            $data[$sofar->[$val]->[1]] = $val;
        }

        &$func(\@data, @fargs);
        return;
    }

    my $rest = 2*$n - 2*$len;
    for(my $p=0; $p < $rest; $p++){
        for(my $q=$p+1; $q < $rest; $q++){
            my ($pos1, $pos2) = 
                ($slots->[$p], $slots->[$q]);

            next if $pos1 + 1 == $pos2 ||
                ($pos1 == 0 && $pos2 == 2*$n-1);

            splice @$slots, $q, 1;
            splice @$slots, $p, 1;

            push @$sofar, [$pos1, $pos2];
            choose2n($n, $slots, $sofar, 
                     $func, @fargs);
            pop @$sofar;

            splice @$slots, $p, 0, $pos1;
            splice @$slots, $q, 0, $pos2;
        }
    }
}

sub account {
    my ($dref, $n, $orbref, $nosymref) = @_;

    $$nosymref++;

    my %orbit;
    for(my $shft = 0; $shft < 2*$n; $shft++){
        my $str =
            join('-', 
                 @$dref[$shft..2*$n-1], 
                 @$dref[0..$shft-1]);
        $orbit{$str} = 1;
    }

    my $orbstr = (sort(keys %orbit))[0];
    $orbref->{$orbstr} = 1;
}

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

    my @nosymres = (0); my @res = (0);

    for(my $n=2; $n <= $mx; $n++){
        my %orbits = (); my $nosym = 0;

        my @src = (0..(2*$n-1));
        choose2n($n, \@src, [], 
                 \&account, $n, \%orbits, \$nosym);

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

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

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

    1;
}

More hints as per request

Web resources to consult are

How to compute with the cycle index. Consider the $\varphi(d)$ permutations with cycle shape $a_d^{2n/d}$ where $d|2n.$ We apply Burnside and ask how many of the proper colorings are fixed by these permutations. Note however that no coloring can be constant on a cycle of length $d$ where $d\gt 2$ because there are only two instances of each color, for a zero contribution. This leaves $d=1$ and $d=2.$ The latter case has permutation shape $a_2^n.$ In order to be constant on these $n$ two-cycles we must place a permutation of the two instances of each color on the two-cycles which can be done in $n!$ ways.(This automatically ensures that two identical colors are never next to each other.) We are left to ask how many colorings are fixed by the identity permutation. These are precisely the proper colorings of the $2n$-gon with no symmetries and we can compute these with inclusion-exclusion. The nodes $P$ of the poset here represent colorings where the colors in $P$ are next to each other, plus possibly some more pairs that are also next to each other. The weight of such a node is $(-1)^{|P|}.$ This means that the colorings with no identical neighbors are only included when $P$ is the empty set, for a weight of one. Colorings with exactly $p$ colors next to each other are included in all nodes $Q$ that are subsets of these $p$ colors $P$ for a contribution of

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

because $p\ge 1$ for a total weight of zero. Now to actually count the elements of $P$ we have two possibilities. First, none of the pairs of colors are placed on the special wrap-around slot pair that connects the last element to the first. This gives $\frac{(2n-2p+p)!}{2^{n-p}}$ or $$\frac{(2n-p)!}{2^{n-p}}$$ possibilities. Second, one of the pairs is located on the bridge slot. That means we must choose the pair, for a factor of $p$ and permute the rest, for a contribution of $p\frac{(2n-2p+p-1)!}{2^{n-p}}$ or $$p\frac{(2n-p-1)!}{2^{n-p}}.$$ We thus obtain for colorings with no symmetries taken into account by inclusion-exclusion for $n\ge 2$

$$\sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}} ((2n-p)! + p(2n-p-1)!).$$

This is the following sequence, which is now easy to calculate:

$$2, 2, 24, 744, 35160, 2394720, 222712560, 27154350720, \\ 4205374225920, 806700010233600, 187793061031699200, \\ 52162131258836121600,\ldots$$

Substituting this into the cycle index we obtain for rotational symmetries taken into account

$$\bbox[5px,border:2px solid #00A000]{\frac{1}{2} (n-1)! + \frac{1}{2n} \sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}} ((2n-p)! + p(2n-p-1)!).}$$

We may thus compute the sequence under rotational symmetries, confirming and extending the values from the Perl script, which used enumeration. We obtain

$$1, 1, 5, 96, 3528, 199620, 15908400, 1697149440, 233631921600, \\ 40335000693120, 8536048230528000, \\ 2173422135804796800,\ldots$$

Solving the case of dihedral symmetry

We get for the cycle index

$$Z(D_{2n}) = \frac{1}{4n} \sum_{d|2n} \varphi(d) a_d^{2n/d} + \frac{1}{4} a_1^2 a_2^{n-1} + \frac{1}{4} a_2^n.$$

Observe that the permutations with shape $a_2^n$ swap adjacent beads (those immediately to the left and the right of the axis of reflection) which would have to be the same color as they are on the same two-cycle. This is impossible so this term does not contribute. On the other hand for the shape $a_1^2 a_2^{n-1}$ we must place pairs of colors on the two-cycles, leaving two identical colors on the slots that are fixed and are situated on the axis of reflection. This yields $n\times (n-1)!$ possibilities. We get for our answer

$$\bbox[5px,border:2px solid #00A000]{\frac{1}{4} (n-1)! + + \frac{1}{4} n! + \frac{1}{4n} \sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}} ((2n-p)! + p(2n-p-1)!).}$$

This yields the following sequence.

$$0, 1, 4, 54, 1794, 99990, 7955460, 848584800, 116816051520, \\ 20167501253760, 4268024125243200, 1086711068022148800,\ldots $$

The Perl code for this version has a different function to do the accounting.

sub account {
    my ($dref, $n, $orbref, $nosymref) = @_;

    $$nosymref++;

    my %orbit;

    for(my $shft = 0; $shft < 2*$n; $shft++){
        my (@data) = 
            (@$dref[$shft..2*$n-1], 
             @$dref[0..$shft-1]);

        my $str = join('-', @data);
        $orbit{$str} = 1;

        for(my $swap = 0; $swap < $n; $swap++){
            my $tmp = $data[$swap];
            $data[$swap] = $data[2*$n-1-$swap];
            $data[2*$n-1-$swap] = $tmp;
        }

        $str = join('-', @data);
        $orbit{$str} = 1;
    }

    my $orbstr = (sort(keys %orbit))[0];
    $orbref->{$orbstr} = 1;
}
$\endgroup$
  • $\begingroup$ Thank you so much Marko. I'm not familiar too much with cycle index and Burnside. can you give me some courses which can be helpful. $\endgroup$ – Omar Sehlouli Mar 31 '17 at 13:15
0
$\begingroup$

For a hexagon, careful counting will get you there. The first color can either have its two vertices opposite or next but one to each other. If they are opposite, the next color can either be opposite or both next to the same one of the first, two choices. If the first color is next but one, placing a color in the space between them forces everything, so two more for a total of four. If you count by hand the first few you can look in OEIS to see if you can find the sequence. That often finds references.

$\endgroup$
  • $\begingroup$ I tried to do so . but I failed :( $\endgroup$ – Omar Sehlouli Mar 30 '17 at 17:06

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.