Number of assignments with $s$ unique values and $t$ identical neighbors In how many ways can we assign the numbers $\{ 1,2,\dots,s\}$ to the variables $a_1, \dots,a_k$ such that each number appears at least once, and exactly $t$ of the pairs $(a_1,a_2), (a_2,a_3), \dots,(a_k,a_1)$ are identical? 
For instance, let $k = 6$, $s=3$, and $t = 2$. Then the following are some of the valid sequences:
$123321$,
$212322$,
$333121$,
$113233$, etc.
I tried first choosing the $t$ identical pairs (in $\binom{k}{t}$ ways), "packaging" them into a single element. Then the problem reduces to finding the number of ways $s$ values can be assigned such that each variable appears at least once, and no same value appears consecutively. This is where I got stuck, any help/pointers would be appreciated.
 A: It is very likely that  an analysis with cases and binomial coefficients, as you suggested, will eventually work out. However, there is a general technique, called the Goulden-Jackson cluster method of counting strings that avoid particular patterns that solves most problems of this type in one fell stroke. This method has several advantages.


*

*It is no harder to learn than solving your original problem.

*It efficiently produces a generating function for the enumeration problem.

*A Maple implementation of the method is freely available, thanks to Doron Zeilberger and John Noonan.


I highly recommend spending an hour or two learning the method. If so, the analysis would go like this.
Let $a_{k,s,t}$ be the number of sequences of length $k$ composed of digits $1,\ldots, s$ with exactly $t$ pairs of consecutive digits being identical. Define the generating function $F_s(z,w)=\sum_{k,t}a_{k,s,t}\,z^k w^t.$ The GJ method then gives 
$$F_s(z,w)=\frac1{1-sz-C},$$
where $C$ is the weight enumerator of the so-called clusters. The method also gives 
$$C=-\frac{sz^2(w-1)}{1+z-zw},$$
resulting in 
$$F_s(z,w)=\frac{1+z-zw}{1-(s-1)z-zw}.$$
Because of the basic form of this generating function, it is straightforward to extract its coefficients. Then, the solution to your problem is
$$a_{k,s,t}=[z^kw^t]F_s(z,w)= s\binom{k-1}{t}(s-1)^{k-1-t}.$$
Note: The exact problem you stated had a couple conditions that I did not include.


*

*Each digit must appear at least once.

*A pair of identical digits can "circle back" from the end of the sequence to the beginning.


The first item is easy to fix, just with subtraction: the number of such sequences with each digit appearing is just $a_{k,s,t}-a_{k,s-1,t}$. The second item is more subtle, but there is an adaption of the GJ method for cyclic words.
