I was asked this question during my interview recently and despite the amount of thinking i put into this, I am yet to figure it out:
Given $n$ balls which are painted by $k$ colors. Let $s_i$ number of balls painted color $i$, $\sum(s_i)=n$. If we go from left to right, what is the expected number of color change?
Example: for ($n$=8, $k$=3), this configuration $(1,1,1,2,2,2,3,3)$ has $2$ color changes. (previously I typed $3$ instead of $2$). Another configuration, $(1,2,3,1,3,2,2,1)$ has 6
Updated: It was $2$ instead of $3$