Three Sing-Sing Problems
Gunnar Blom, Lars K. Holst, Dennis Sandell · American Mathematical Monthly · 1995
Linear SingSing problem. If the letters in the word SINGSING are permuted at random, we may obtain, for example, INGGINSS or SNINGISG. In the former case, the permutation contains two pairs of equal neighbours, GG and SS, but in the latter case there are no such neighbours. What is the probability that the permutation has no equal neighbours? As we will show, the answer is 12/35. Using numbers instead of letters, the answer can be obtained from the solution to the linear Sing-Sing problem: What is the probability distribution of the number of equal neighbours in a random permutation of the 2n numbers 1122. .. nn?