Consider n points A1,A2,…,An 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≥3 we can reduce this recursively as follows(this is quite an old idea):For Cn denoting the circle graph on n vertices, and Pn denoting a path on n vertices,it is easy to see that if f(Cn,p) is the desired number,then f(Cn,p)=f(Pn,p)−f(Cn−1,p).this is easy since every proper coloring of Cn leads to a proper coloring of Pn as well(just delete an edge).conversely the only proper colorings of Pn that extend to a proper coloring of Cn are those for which the end vertices have different colors.The colorings of Pn with the end vertices of the same color are equivalent to colorings of Cn−1 (where you 'identify' the end vertices as one single vertex). finally f(Pn,p)=p(p−1)n−1 and the rest is induction.
12.03.2005 22:37
seshadri wrote: For Cn denoting the circle graph on n vertices, and Pn 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
Cn is the cycle with n vertices (you can draw it as a polygon with n vertices), and Pn is what you get from Cn 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.