Given $N$ balls numbered from 1 to N and each ball is assigned some color in the range [1,N].
$p_n$ - the number of permutations of these balls such that it has $n$ pairs of adjacent balls with the same color
$q_n$ - the number of permutations of these balls such that it has at least n pairs of adjacent balls with the same color
What is the relation between $p$ and $q$?
I found the solution somewhere as
$$ q_n=\sum_{k=n}^{N-1}\binom kn p_k $$ But I don't understand how?
Also
$$p_n=\sum_{k=n}^{N-1} (-1)^{k-n}\binom kn q_k$$
It was given that $p_n$ is derived from inclusion exclusion principle. Although i know what is inclusion exclusion principle, i still don't understand how is this derived?