Let $A_1,A_2,......,A_n$ be points on a circle. Find the number of possible colorings of these points with $p$ colors, $p\ge2$, such that any two neighboring points have distinct colors.
2 Answers
Let $C_n$ be the number of such colourings. Suppose $n\ge3$. Now the number of colourings of $A_1,\ldots,A_n$ such that $A_i$ and $A_{i+1}$ have different colours is evidently $p(p-1)^{n-1}$. But that includes the colourings where $A_1$ and $A_n$ have the same colour. But there are $C_{n-1}$ such colourings (why?). Thus $$C_n=p(p-1)^{n-1}-C_{n-1}=p(p-1)^{n-1}-p(p-1)^{n-2}+p(p-1)^{n-3}-\cdots$$ etc.
-
$\begingroup$ [+1] Excellent. See a more involved proof in (math.stackexchange.com/q/2164399) $\endgroup$ Jan 5, 2018 at 0:07
We can pretend the colors are elements of the additive group $G$ of integers mod $p$. The number $N$ of such colorings is equal to the number of sequences $x_1,x_2,\ldots,x_n$ of non-zero elements of $G$ for which $\sum_{i=1}^n x_i \equiv 0 \pmod p$. Here $x_i$ denotes the difference between person $i$'s color and that of her neighbor to the right, person $((i+1)\bmod p)$; the condition that the $x_i$ sum to $0$ mod $p$ is needed to make person 1's color equal to what it is, in this setup and 1's left neighbor, person $n$.
$N$ can be calculated by considering the signed measure $\sigma=p u -\delta_0$ on $G$, where $u$ is the uniform probability distribution on $G$ and $\delta_0$ is the point mass at $0\in G$. Let $\tau=\sigma^{*n}$ be the $n$-fold convolution product of $\sigma$ with itself; the desired answer is $N=\tau(\{0\})$. The convolution product in turn can be calculated by the binomial theorem: $$ \tau = \sum_{k=0}^n \binom n k p^k u^{*k} (-1)^{n-k}\delta^{*(n-k)} = (-1)^n \delta_0 + \sum_{k=1}^{n} \binom n k p^k\,u \,(-1)^{n-k},$$ making free use of $u*u=u*\delta_0=u$ and $\delta_0*\delta_o=\delta_0$. So $$N=\tau(\{0\}) = (-1)^n + \left(\sum_{k=0}^{n} \binom n k p^k\,(-1)^{n-k} - (-1)^n\right)u(\{0\})$$ $$ = (-1)^n + \frac{ (p-1)^n - (-1)^n} p = \frac{(p-1)^n + (-1)^n(p-1)} p.$$