How many ways are there to color the vertices with $n$ colors such that adjacent vertices get different colors?
I know this will use Inclusion-Exclusion.
Since there are $5$ vertices, the total number of ways to color the vertices without restriction is $n^5$.
I am trying to figure out what my sets $A_i$ will be.
$A_1=\{1 \text{ and } 2 \text{ same color}\}$
$A_2=\{2 \text{ and } 3 \text{ same color}\}$
$A_3=\{3 \text{ and } 4 \text{ same color}\}$
$A_4=\{4 \text{ and } 5 \text{ same color}\}$
$A_5=\{1 \text{ and } 3 \text{ same color}\}$
$A_6=\{1 \text{ and } 4 \text{ same color}\}$
$A_7=\{1 \text{ and } 5 \text{ same color}\}$
I am stuck on where to go from here. I know that I need to find:
$|A_i|, |A_i \cap A_j|, |A_i \cap A_j \cap A_k|,...|A_1 \cap A_2 \cap A_3 \cap \dots \cap A_7|$.
$|A_i|=\binom{7}{1} \cdot n\cdot 1\cdot n\cdot n\cdot n = \binom{7}{1} \cdot n^4$
$|A_i \cap A_j|=\binom{7}{2} \cdot n\cdot 1 \cdot 1 \cdot n \cdot n = \binom{7}{2}\cdot n^3$
I am stuck finding the rest.
edit: solution in textbook
$n^5 −C(7,1)×n^4 +C(7,2)×n^3 −{C(7,3)−3)×n^2 +3×n^3} +{(C(7,4)−14)×n+14×n^2}−{(C(7,5)−2)×n+2×n^2}+{C(7,6) −C(7,7)}×n$.
I am trying to attempt to understand how the textbook solution was derived.
Your graph has a very nice pattern for which you can determine the chromatic polynomial without the contraction-deletion recurrence.
Suppose you had $k$ colours. Then vertex $(2)$ can be chosen as any of the $k$ colours, vertex $(1)$ can then be any of the remaining $k-1$ colors and vertex $(3)$ any of the remaining $k-2$ colours. Therefore there are $k(k-1)(k-3)$ ways to colour the left-most triangle.
Now, for any colouring of this triangle, vertex $(4)$ can be coloured $k-2$ ways, namely anything except the colours used for $(1)$ and $(3)$. Likewise, for any colouring of vertices $(1) - (4)$, vertex $(5)$ can also be coloured $k-2$ ways, namely whatever colours $(1)$ and $(4)$ are not. The chromatic polynomial must therefore be $$\chi_G(k) = k(k-1)(k-2)^3.$$