3-colourings of a 3×3 table with one of 3 colors up to symmetries
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Color each cell of a $3×3$ table with $3$ colors. What is the number of ways to do so if adjacent cells have different colors?
Of course we consider two paintings the same (equivalent) if exist reflection or rotation which take one to another. So
beginarray r
hline
colorblueB& coloryellowY &colorredR \
hline
colorredR& colorredR&colorredR\
hline
colorredR& colorredR& colorredR \
hline
endarray
and
beginarray r
hline
colorredR& colorredR& colorblueB \
hline
colorredR& colorredR& coloryellowY \
hline
colorredR& colorredR& colorredR \
hline
endarray
are the same paintings (by the way, how can I aline them?).
Since marked cells are ''independent'' we can color them at random but not with all 3 colors.
beginarray r
hline
& X & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 1: If all $X$ are colored with the same color, then for each unmarked cell we have 2 posibilites. So in this case we have $3cdot 2^5$ possibile colorings. But clearly some of them are equivalent. What should I do? Divide this with 4? Or 16? Something else?
Case 2: $Y$ is of different color then $X$. Now we have $3$ colors for $Y$ and $2$ for $X$. Rest of the places we can color $1^3cdot 2^2$ so we have $6cdot 2^2$ possibile colorings. But again reflections across midlle colum give us equivalent colorings so we should divide this by $2$?
beginarray r
hline
& Y & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 3: ...
beginarray r
hline
& Y & \
hline
Y & &X \
hline
& X& \
hline
endarray
Is there more elegant aproach?
combinatorics graph-theory coloring
add a comment |Â
up vote
4
down vote
favorite
Color each cell of a $3×3$ table with $3$ colors. What is the number of ways to do so if adjacent cells have different colors?
Of course we consider two paintings the same (equivalent) if exist reflection or rotation which take one to another. So
beginarray r
hline
colorblueB& coloryellowY &colorredR \
hline
colorredR& colorredR&colorredR\
hline
colorredR& colorredR& colorredR \
hline
endarray
and
beginarray r
hline
colorredR& colorredR& colorblueB \
hline
colorredR& colorredR& coloryellowY \
hline
colorredR& colorredR& colorredR \
hline
endarray
are the same paintings (by the way, how can I aline them?).
Since marked cells are ''independent'' we can color them at random but not with all 3 colors.
beginarray r
hline
& X & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 1: If all $X$ are colored with the same color, then for each unmarked cell we have 2 posibilites. So in this case we have $3cdot 2^5$ possibile colorings. But clearly some of them are equivalent. What should I do? Divide this with 4? Or 16? Something else?
Case 2: $Y$ is of different color then $X$. Now we have $3$ colors for $Y$ and $2$ for $X$. Rest of the places we can color $1^3cdot 2^2$ so we have $6cdot 2^2$ possibile colorings. But again reflections across midlle colum give us equivalent colorings so we should divide this by $2$?
beginarray r
hline
& Y & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 3: ...
beginarray r
hline
& Y & \
hline
Y & &X \
hline
& X& \
hline
endarray
Is there more elegant aproach?
combinatorics graph-theory coloring
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Color each cell of a $3×3$ table with $3$ colors. What is the number of ways to do so if adjacent cells have different colors?
Of course we consider two paintings the same (equivalent) if exist reflection or rotation which take one to another. So
beginarray r
hline
colorblueB& coloryellowY &colorredR \
hline
colorredR& colorredR&colorredR\
hline
colorredR& colorredR& colorredR \
hline
endarray
and
beginarray r
hline
colorredR& colorredR& colorblueB \
hline
colorredR& colorredR& coloryellowY \
hline
colorredR& colorredR& colorredR \
hline
endarray
are the same paintings (by the way, how can I aline them?).
Since marked cells are ''independent'' we can color them at random but not with all 3 colors.
beginarray r
hline
& X & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 1: If all $X$ are colored with the same color, then for each unmarked cell we have 2 posibilites. So in this case we have $3cdot 2^5$ possibile colorings. But clearly some of them are equivalent. What should I do? Divide this with 4? Or 16? Something else?
Case 2: $Y$ is of different color then $X$. Now we have $3$ colors for $Y$ and $2$ for $X$. Rest of the places we can color $1^3cdot 2^2$ so we have $6cdot 2^2$ possibile colorings. But again reflections across midlle colum give us equivalent colorings so we should divide this by $2$?
beginarray r
hline
& Y & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 3: ...
beginarray r
hline
& Y & \
hline
Y & &X \
hline
& X& \
hline
endarray
Is there more elegant aproach?
combinatorics graph-theory coloring
Color each cell of a $3×3$ table with $3$ colors. What is the number of ways to do so if adjacent cells have different colors?
Of course we consider two paintings the same (equivalent) if exist reflection or rotation which take one to another. So
beginarray r
hline
colorblueB& coloryellowY &colorredR \
hline
colorredR& colorredR&colorredR\
hline
colorredR& colorredR& colorredR \
hline
endarray
and
beginarray r
hline
colorredR& colorredR& colorblueB \
hline
colorredR& colorredR& coloryellowY \
hline
colorredR& colorredR& colorredR \
hline
endarray
are the same paintings (by the way, how can I aline them?).
Since marked cells are ''independent'' we can color them at random but not with all 3 colors.
beginarray r
hline
& X & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 1: If all $X$ are colored with the same color, then for each unmarked cell we have 2 posibilites. So in this case we have $3cdot 2^5$ possibile colorings. But clearly some of them are equivalent. What should I do? Divide this with 4? Or 16? Something else?
Case 2: $Y$ is of different color then $X$. Now we have $3$ colors for $Y$ and $2$ for $X$. Rest of the places we can color $1^3cdot 2^2$ so we have $6cdot 2^2$ possibile colorings. But again reflections across midlle colum give us equivalent colorings so we should divide this by $2$?
beginarray r
hline
& Y & \
hline
X & &X \
hline
& X& \
hline
endarray
Case 3: ...
beginarray r
hline
& Y & \
hline
Y & &X \
hline
& X& \
hline
endarray
Is there more elegant aproach?
combinatorics graph-theory coloring
combinatorics graph-theory coloring
edited 29 mins ago
asked 2 hours ago


greedoid
32.6k114388
32.6k114388
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
We can use Burnside's lemma to account for symmetries. By the OEIS, there are 246 different 3-colourings of a labelled 3×3 grid graph (i.e. before accounting for symmetry).
This graph's non-identity symmetries are as follows. The general form of a colouring invariant under this symmetry is shown, then a calculation of the number of such colourings.
90° left/right rotations. A colouring invariant under this transformation looks like this:
$$beginarrayr
hline a&b&a\
hline b&c&b\
hline a&b&a\hlineendarray$$
After $b$ is chosen, we have two possibilities each for $a,c$. Thus there are $3×2×2=12$ such colourings invariant under each of these symmetries.
180° rotation.
$$beginarrayr
hline a&b&c\
hline d&e&d\
hline c&b&a\hlineendarray$$
Either $b,d$ are different colours (6 ways), in which case $a,c,e$ can only assume the third colour, or $b,d$ are the same (3 ways) and $a,c,e$ can be one of two colours. There are $6×1^3+3×2^3=30$ invariant colourings.
Horizontal/vertical reflections.
$$beginarrayr
hline a&b&c\
hline d&e&f\
hline a&b&c\hlineendarray$$
This is equivalent to the number of 3-colourings of a 2×3 grid graph. Appealing to the OEIS again, we see that there are 54 such colourings for each symmetry.
Diagonal reflections.
$$beginarrayr
hline a&b&c\
hline d&e&b\
hline f&d&a\hlineendarray$$
This is equivalent to the number of colourings of a square, 18 according to the OEIS, multiplied by 4, yielding 72. The square is formed by $a,b,d,e$, and for each colouring of the square $c,f$ can be either of the two colours not used for $b,d$ respectively, hence the $2^2$ multiplier.
Burnside's lemma then gives the number of colourings up to symmetries as
$$frac246+2×12+30+2×54+2×728=colorred69$$
add a comment |Â
up vote
1
down vote
My colors are $0$ and $pm1$. I put a $0$ in the center. Then up to rotations, reflections, and multiplication by $-1$ we only have the four following patterns to analyze further:
$$pmleft[matrix&1&cr1&0&1cr&1&crright]>,quadpmleft[matrix&-1&cr1&0&1cr&1&crright]>,quadleft[matrix&-1&cr1&0&1cr&-1&crright]>,quadleft[matrix&1&cr-1&0&1cr&-1&crright] .tag1$$
As an example consider the second pattern (apart from th $pm$). Here two $0$s in the upper corner are enforced. In the lower corner we can have zero, one,or two $0$s and the rest $-1$s:
$$left[matrix0&-1&0cr1&0&1cr-1&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&0crright] .$$
These three solutions have different numbers of z$0$s in total, hence are essentially different. And we don't have to be afraid that they are the same as solutions stemming from the other patterns in $(1)$.
I leave the other patterns in $(1)$ to you. At the end multiply by $3!$ in order to assign your colors to mine.
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
We can use Burnside's lemma to account for symmetries. By the OEIS, there are 246 different 3-colourings of a labelled 3×3 grid graph (i.e. before accounting for symmetry).
This graph's non-identity symmetries are as follows. The general form of a colouring invariant under this symmetry is shown, then a calculation of the number of such colourings.
90° left/right rotations. A colouring invariant under this transformation looks like this:
$$beginarrayr
hline a&b&a\
hline b&c&b\
hline a&b&a\hlineendarray$$
After $b$ is chosen, we have two possibilities each for $a,c$. Thus there are $3×2×2=12$ such colourings invariant under each of these symmetries.
180° rotation.
$$beginarrayr
hline a&b&c\
hline d&e&d\
hline c&b&a\hlineendarray$$
Either $b,d$ are different colours (6 ways), in which case $a,c,e$ can only assume the third colour, or $b,d$ are the same (3 ways) and $a,c,e$ can be one of two colours. There are $6×1^3+3×2^3=30$ invariant colourings.
Horizontal/vertical reflections.
$$beginarrayr
hline a&b&c\
hline d&e&f\
hline a&b&c\hlineendarray$$
This is equivalent to the number of 3-colourings of a 2×3 grid graph. Appealing to the OEIS again, we see that there are 54 such colourings for each symmetry.
Diagonal reflections.
$$beginarrayr
hline a&b&c\
hline d&e&b\
hline f&d&a\hlineendarray$$
This is equivalent to the number of colourings of a square, 18 according to the OEIS, multiplied by 4, yielding 72. The square is formed by $a,b,d,e$, and for each colouring of the square $c,f$ can be either of the two colours not used for $b,d$ respectively, hence the $2^2$ multiplier.
Burnside's lemma then gives the number of colourings up to symmetries as
$$frac246+2×12+30+2×54+2×728=colorred69$$
add a comment |Â
up vote
3
down vote
We can use Burnside's lemma to account for symmetries. By the OEIS, there are 246 different 3-colourings of a labelled 3×3 grid graph (i.e. before accounting for symmetry).
This graph's non-identity symmetries are as follows. The general form of a colouring invariant under this symmetry is shown, then a calculation of the number of such colourings.
90° left/right rotations. A colouring invariant under this transformation looks like this:
$$beginarrayr
hline a&b&a\
hline b&c&b\
hline a&b&a\hlineendarray$$
After $b$ is chosen, we have two possibilities each for $a,c$. Thus there are $3×2×2=12$ such colourings invariant under each of these symmetries.
180° rotation.
$$beginarrayr
hline a&b&c\
hline d&e&d\
hline c&b&a\hlineendarray$$
Either $b,d$ are different colours (6 ways), in which case $a,c,e$ can only assume the third colour, or $b,d$ are the same (3 ways) and $a,c,e$ can be one of two colours. There are $6×1^3+3×2^3=30$ invariant colourings.
Horizontal/vertical reflections.
$$beginarrayr
hline a&b&c\
hline d&e&f\
hline a&b&c\hlineendarray$$
This is equivalent to the number of 3-colourings of a 2×3 grid graph. Appealing to the OEIS again, we see that there are 54 such colourings for each symmetry.
Diagonal reflections.
$$beginarrayr
hline a&b&c\
hline d&e&b\
hline f&d&a\hlineendarray$$
This is equivalent to the number of colourings of a square, 18 according to the OEIS, multiplied by 4, yielding 72. The square is formed by $a,b,d,e$, and for each colouring of the square $c,f$ can be either of the two colours not used for $b,d$ respectively, hence the $2^2$ multiplier.
Burnside's lemma then gives the number of colourings up to symmetries as
$$frac246+2×12+30+2×54+2×728=colorred69$$
add a comment |Â
up vote
3
down vote
up vote
3
down vote
We can use Burnside's lemma to account for symmetries. By the OEIS, there are 246 different 3-colourings of a labelled 3×3 grid graph (i.e. before accounting for symmetry).
This graph's non-identity symmetries are as follows. The general form of a colouring invariant under this symmetry is shown, then a calculation of the number of such colourings.
90° left/right rotations. A colouring invariant under this transformation looks like this:
$$beginarrayr
hline a&b&a\
hline b&c&b\
hline a&b&a\hlineendarray$$
After $b$ is chosen, we have two possibilities each for $a,c$. Thus there are $3×2×2=12$ such colourings invariant under each of these symmetries.
180° rotation.
$$beginarrayr
hline a&b&c\
hline d&e&d\
hline c&b&a\hlineendarray$$
Either $b,d$ are different colours (6 ways), in which case $a,c,e$ can only assume the third colour, or $b,d$ are the same (3 ways) and $a,c,e$ can be one of two colours. There are $6×1^3+3×2^3=30$ invariant colourings.
Horizontal/vertical reflections.
$$beginarrayr
hline a&b&c\
hline d&e&f\
hline a&b&c\hlineendarray$$
This is equivalent to the number of 3-colourings of a 2×3 grid graph. Appealing to the OEIS again, we see that there are 54 such colourings for each symmetry.
Diagonal reflections.
$$beginarrayr
hline a&b&c\
hline d&e&b\
hline f&d&a\hlineendarray$$
This is equivalent to the number of colourings of a square, 18 according to the OEIS, multiplied by 4, yielding 72. The square is formed by $a,b,d,e$, and for each colouring of the square $c,f$ can be either of the two colours not used for $b,d$ respectively, hence the $2^2$ multiplier.
Burnside's lemma then gives the number of colourings up to symmetries as
$$frac246+2×12+30+2×54+2×728=colorred69$$
We can use Burnside's lemma to account for symmetries. By the OEIS, there are 246 different 3-colourings of a labelled 3×3 grid graph (i.e. before accounting for symmetry).
This graph's non-identity symmetries are as follows. The general form of a colouring invariant under this symmetry is shown, then a calculation of the number of such colourings.
90° left/right rotations. A colouring invariant under this transformation looks like this:
$$beginarrayr
hline a&b&a\
hline b&c&b\
hline a&b&a\hlineendarray$$
After $b$ is chosen, we have two possibilities each for $a,c$. Thus there are $3×2×2=12$ such colourings invariant under each of these symmetries.
180° rotation.
$$beginarrayr
hline a&b&c\
hline d&e&d\
hline c&b&a\hlineendarray$$
Either $b,d$ are different colours (6 ways), in which case $a,c,e$ can only assume the third colour, or $b,d$ are the same (3 ways) and $a,c,e$ can be one of two colours. There are $6×1^3+3×2^3=30$ invariant colourings.
Horizontal/vertical reflections.
$$beginarrayr
hline a&b&c\
hline d&e&f\
hline a&b&c\hlineendarray$$
This is equivalent to the number of 3-colourings of a 2×3 grid graph. Appealing to the OEIS again, we see that there are 54 such colourings for each symmetry.
Diagonal reflections.
$$beginarrayr
hline a&b&c\
hline d&e&b\
hline f&d&a\hlineendarray$$
This is equivalent to the number of colourings of a square, 18 according to the OEIS, multiplied by 4, yielding 72. The square is formed by $a,b,d,e$, and for each colouring of the square $c,f$ can be either of the two colours not used for $b,d$ respectively, hence the $2^2$ multiplier.
Burnside's lemma then gives the number of colourings up to symmetries as
$$frac246+2×12+30+2×54+2×728=colorred69$$
edited 1 hour ago
answered 1 hour ago


Parcly Taxel
38.5k137098
38.5k137098
add a comment |Â
add a comment |Â
up vote
1
down vote
My colors are $0$ and $pm1$. I put a $0$ in the center. Then up to rotations, reflections, and multiplication by $-1$ we only have the four following patterns to analyze further:
$$pmleft[matrix&1&cr1&0&1cr&1&crright]>,quadpmleft[matrix&-1&cr1&0&1cr&1&crright]>,quadleft[matrix&-1&cr1&0&1cr&-1&crright]>,quadleft[matrix&1&cr-1&0&1cr&-1&crright] .tag1$$
As an example consider the second pattern (apart from th $pm$). Here two $0$s in the upper corner are enforced. In the lower corner we can have zero, one,or two $0$s and the rest $-1$s:
$$left[matrix0&-1&0cr1&0&1cr-1&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&0crright] .$$
These three solutions have different numbers of z$0$s in total, hence are essentially different. And we don't have to be afraid that they are the same as solutions stemming from the other patterns in $(1)$.
I leave the other patterns in $(1)$ to you. At the end multiply by $3!$ in order to assign your colors to mine.
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
add a comment |Â
up vote
1
down vote
My colors are $0$ and $pm1$. I put a $0$ in the center. Then up to rotations, reflections, and multiplication by $-1$ we only have the four following patterns to analyze further:
$$pmleft[matrix&1&cr1&0&1cr&1&crright]>,quadpmleft[matrix&-1&cr1&0&1cr&1&crright]>,quadleft[matrix&-1&cr1&0&1cr&-1&crright]>,quadleft[matrix&1&cr-1&0&1cr&-1&crright] .tag1$$
As an example consider the second pattern (apart from th $pm$). Here two $0$s in the upper corner are enforced. In the lower corner we can have zero, one,or two $0$s and the rest $-1$s:
$$left[matrix0&-1&0cr1&0&1cr-1&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&0crright] .$$
These three solutions have different numbers of z$0$s in total, hence are essentially different. And we don't have to be afraid that they are the same as solutions stemming from the other patterns in $(1)$.
I leave the other patterns in $(1)$ to you. At the end multiply by $3!$ in order to assign your colors to mine.
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
My colors are $0$ and $pm1$. I put a $0$ in the center. Then up to rotations, reflections, and multiplication by $-1$ we only have the four following patterns to analyze further:
$$pmleft[matrix&1&cr1&0&1cr&1&crright]>,quadpmleft[matrix&-1&cr1&0&1cr&1&crright]>,quadleft[matrix&-1&cr1&0&1cr&-1&crright]>,quadleft[matrix&1&cr-1&0&1cr&-1&crright] .tag1$$
As an example consider the second pattern (apart from th $pm$). Here two $0$s in the upper corner are enforced. In the lower corner we can have zero, one,or two $0$s and the rest $-1$s:
$$left[matrix0&-1&0cr1&0&1cr-1&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&0crright] .$$
These three solutions have different numbers of z$0$s in total, hence are essentially different. And we don't have to be afraid that they are the same as solutions stemming from the other patterns in $(1)$.
I leave the other patterns in $(1)$ to you. At the end multiply by $3!$ in order to assign your colors to mine.
My colors are $0$ and $pm1$. I put a $0$ in the center. Then up to rotations, reflections, and multiplication by $-1$ we only have the four following patterns to analyze further:
$$pmleft[matrix&1&cr1&0&1cr&1&crright]>,quadpmleft[matrix&-1&cr1&0&1cr&1&crright]>,quadleft[matrix&-1&cr1&0&1cr&-1&crright]>,quadleft[matrix&1&cr-1&0&1cr&-1&crright] .tag1$$
As an example consider the second pattern (apart from th $pm$). Here two $0$s in the upper corner are enforced. In the lower corner we can have zero, one,or two $0$s and the rest $-1$s:
$$left[matrix0&-1&0cr1&0&1cr-1&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&-1crright]>,quad left[matrix0&-1&0cr1&0&1cr0&1&0crright] .$$
These three solutions have different numbers of z$0$s in total, hence are essentially different. And we don't have to be afraid that they are the same as solutions stemming from the other patterns in $(1)$.
I leave the other patterns in $(1)$ to you. At the end multiply by $3!$ in order to assign your colors to mine.
answered 1 hour ago


Christian Blatter
168k7111319
168k7111319
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
add a comment |Â
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
What about this one: $$pmleft[matrix&1&cr1&-1&1cr&1&crright]$$
– greedoid
37 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
@greedoid: Putting $0$ at the center is no restriction of generality.
– Christian Blatter
15 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2977453%2f3-colourings-of-a-3%25c3%25973-table-with-one-of-3-colors-up-to-symmetries%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password