An even number $n$ of people sit around a table with $d$ choices for colors ... Assume you have $n$ people who sit around a circular table. Assume also that $n$ is even. Each person could have a shirt whose color is one $d$ choices. How many options are to pick the colors of the people in the table under the condition that no two adjacent people could have the same color?
I tried using inclusion-exclusion. $A_i$ would be the number of options to have $a_i \neq a_{i-1}$ where each $a_i$ is the color of the person in the seat $i$, and we have no other restraints regarding the colors of the other people. And then we would take $|A_1\cap \dots \cap A_n|$, but then, when you use inclusion-exclusion you would have to differentiate between different situations - if the $A_i$'s are adjacent or not.
 A: This is a very beautiful problem. It seems at a first glance that the size of an arbitrary intersection $A_{i(1)}\cap A_{i(2)}\cap \dots \cap A_{i(k)}$ should depened on how many of the indices $i(1),i(2),\dots,i(k)$ are adjacent to each other. For example, $|A_2\cap A_3|$ is the number of sequences where $a_1=a_2=a_3$, and $|A_2\cap A_4|$ is the number of sequences where $a_1=a_2$ and separately $a_3=a_4$. Surely these have different enumerations, right? Well, no. In both cases, there are $n-2$ groups of objects to color. For $|A_2\cap A_3|$, there is one group of three, $\{a_1,a_2,a_3\}$, and $n-3$ singletons. For $|A_2\cap A_4|$, there are two pairs, $\{a_1,a_2\}$ and $\{a_3,a_4\}$, and $m-4$ singletons. But each group must be colored as a unit, so these behave the same, and we get
$$
|A_2\cap A_3|=|A_2\cap A_4|=d^{n-2} 
$$
This same idea persists for the more complicated intersections. It turns out that for any choice of indices $1\le i(1)<i(2)<\dots<i(k)\le n$, where $k<n$, we have
$$
|A_{i(1)}\cap \dots \cap A_{i(k)}|=d^{n-k},\qquad \color{red}{0\le k<n}
$$
The idea is that without any restrictions, the objects are in $n$ singleton groups, but each restriction $A_{i(j)}$ joins two groups together. Therefore, no matter what the adjacencies are, the facts that there are initially $n$ groups and $k$ joinings that each reduce the number of groups by one, imply that there will be $n-k$ groups, which can be colored in $d^{n-k}$ ways.
There is only one exception. I emphasized that the above is only true when $k<n$. When, $k=n$, we are considering the intersection of all conditions $A_1\cap \dots \cap A_n$. These are just colorings where all items are the same, so there are $d$ colorings. The idea is that one of these joinings is redundant; the last connection does not affect the number of groups.
This means that the inclusion exclusion formula works out very nicely, since we can lump together all intersections of the same order. The result is
$$
\left(\sum_{k=0}^{n-1}(-1)^k\binom nk d^{n-k}\right)+d
$$
Using the binomial theorem, you can show that this simplifies to
$$
(d-1)^n+(-1)^n(d-1)
$$
We did not need the assumption of $n$ being even, but adding in this assumption, that expression further simplifies to $(d-1)[(d-1)^{n-1}+1]$.
A: Just to provide an alternative answer, notice that your question may be asked in a different form:
What is the number of proper vertex colourings of a cycle on $n$ vertices $C_n$ using at most $d$ colours?
And a known tool from graph theory which can provide the answer to the above question is the graph's chromatic polynomial.
Specifically, we look for the value of the polynomial $\mathcal{P}(C_n, d)$. Using the deletion-contraction formula, we get that
$$\mathcal{P}(C_n, d) = \mathcal{P}(P_n, d) - \mathcal{P}(C_{n-1}, d),$$
where $P_n$ denotes the path graph on $n$ vertices. Now, the number of colourings of path using $d$ colours is rather simple - we color the first vertex with any colour, and we colour each next vertex using any of the $d-1$ colours other, than the previous ones. This gives us
$$\mathcal{P}(P_n, d) = d(d-1)^{n-1}$$
Solving the recurrence equalities down to $\mathcal{P}(C_3, d) = d(d-1)(d-2)$, we obtain the same result:
$$\mathcal{P}(C_n, d) = (d-1)^n + (-1)^n (d-1)$$
