Given an $n$-sided polygon, how many ways can you color the vertices using $k$ colors so that no two adjacent vertices have the same color?
(Inspired by 2011 AMC 12 A #16 – I'm able to do this for small cases but not in general.)
Given an $n$-sided polygon, how many ways can you color the vertices using $k$ colors so that no two adjacent vertices have the same color?
(Inspired by 2011 AMC 12 A #16 – I'm able to do this for small cases but not in general.)
Here are two ways to do the problem, both of which use graph theory. The problem is equivalent to counting the number of closed walks of length $n$ on the complete graph $K_k$ on $k$ vertices. The number of closed walks of length $n$ on a graph $G$ with adjacency matrix $A$ is given by $\text{tr } A^n = \sum_{i=1}^k \lambda_i^n$ where $\lambda_i$ are the eigenvalues of $A$.
So it suffices to compute the eigenvalues of the adjacency matrix of $K_k$. This is a nice exercise, but for the sake of completeness I will tell you that they are $k-1, -1, -1, ...$. So the final answer is
$(k-1)^n + (k-1)(-1)^n.$
The second method is to observe that the problem is equivalent to computing the chromatic polynomial of the cyclic graph $C_n$. This can be done by induction and the deletion-contraction recurrence, and you get the same answer.
Note that these two solutions generalize in different directions. The first solution suggests a generalization of the problem where you replace $K_k$ with a more complicated graph, whereas the second solution suggests a generalization of the problem where you replace $C_n$ with a more complicated graph. Both problems are in turn special cases of the following problem.
Definition: Let $G, H$ be two (undirected, simple) graphs. A morphism $f : G \to H$ is a function $f : V_G \to V_H$ sending vertices of $G$ to vertices of $H$ such that, if $u, v \in G$ are connected by an edge, then $f(u), f(v)$ are also connected by an edge.
Problem: How many morphisms are there from a given graph $G$ to a given graph $H$?
The walk problem corresponds to letting $G = C_n$ and letting $H$ be arbitrary, while the coloring problem corresponds to letting $H = K_k$ and letting $G$ be arbitrary. Both of these are very special cases. The general problem is interesting; I have no idea what's known about it.
Do you know about the chromatic polynomial? That has a simple skein formula which can be easily calculated for n-gons. It is a polynomial in k, the number of possible colorings.