The problem concerns strings of length $\ell$, containing only a few unique elements of a larger alphabet, such that no two neighboring elements are the same. The problem:
- I have an alphabet $\{a,b,c,d...\}$ of size $n$.
- Given $\ell$ and some $m\leq n$, how many strings are there of length $\ell$, with exactly $m$ unique characters such that no two neighbors in the string are the same?
Example 1: For $\ell=5$ and $m=3$ the string $ababc$ is in this set.
Example 2: For $\ell=5$ and $m=3$ the string $abbac$ is not in this set as we have two repeated neighbours ($bb$).
My first approach is to count the number of strings containing up to $m$ elements with no repeated neighbors, which I believe is given by $${n\choose m}m(m-1)^{\ell-1}$$ however this includes strings consisting of only $2$ elements (e.g., $ababab...$) and is therefore only an upper bound for $m>2$.
Additionally I have for $m=\ell$ : $${n\choose \ell}\ell!$$ but I am struggling to find a formula for $2<m<\ell$, i.e., when some elements appear multiple times in the string but they cannot be next to each other.
Thanks in advance for your help, any advice is appreciated!