Consider $n$ points $A_1, A_2, \ldots, A_n$ on a circle. How many ways are there if we want to color these points by $p$ colors, so that each two neighbors points are colored with two different colors?
Problem
Source:
Tags: combinatorics
12.03.2005 01:48
if $p=2$ then if $n$ is even you have $2$-colorings,else you have none. If $p\geq 3$ we can reduce this recursively as follows(this is quite an old idea):For $C_n$ denoting the circle graph on $n$ vertices, and $P_n$ denoting a path on $n$ vertices,it is easy to see that if $f(C_n,p)$ is the desired number,then $f(C_n,p)=f(P_n,p)-f(C_{n-1},p)$.this is easy since every proper coloring of $C_n$ leads to a proper coloring of $P_n$ as well(just delete an edge).conversely the only proper colorings of $P_n$ that extend to a proper coloring of $C_n$ are those for which the end vertices have different colors.The colorings of $P_n$ with the end vertices of the same color are equivalent to colorings of $C_{n-1}$ (where you 'identify' the end vertices as one single vertex). finally $f(P_n,p)=p(p-1)^{n-1}$ and the rest is induction.
12.03.2005 22:37
seshadri wrote: For $C_n$ denoting the circle graph on $n$ vertices, and $P_n$ denoting a path on $n$ vertices,it is easy to see... A stupid question - what is a circle graph/path?
12.03.2005 22:43
$C_n$ is the cycle with $n$ vertices (you can draw it as a polygon with $n$ vertices), and $P_n$ is what you get from $C_n$ after you delete an edge (i.e. the path with $n$ vertices).
11.04.2017 08:13
I think that this is a generalization of 2016 AIME II #12. Not a hard extension but pretty cool.