[Math] Arrangement of the word ‘Success’

combinatorics

Number of ways the word 'Success' can be arranged, such that no two S's and C's are together.

Best Answer

These problems quickly get out of hand if the words are long and there are lots of multiple letters. Here is a sophisticated solution that uses ideas from algebraic combinatorics. I learned it from Jair Taylor's wonderful answer here. See this question also.

Define polynomials for $k\geq 1$ by $q_k(x) = \sum_{i=1}^k \frac{(-1)^{i-k}}{i!} {k-1 \choose i-1}x^i$. Here are the first few polynomials: $$q_1(x)=x,\quad q_2(x)=x^2/2-x,\quad q_3(x)=x^3/6-x^2+x.$$

The number of permutations with no equal neighbors, using an alphabet with frequencies $k_1,k_2,\dots$ is:

$$\int_0^\infty \prod_j q_{k_j}(x)\, e^{-x}\,dx.$$

For the "success" problem, the product of the $q$ functions is $$ q_3(x)\, q_2(x)\, q_1(x)^2=(x^3/6-x^2+x)(x^2/2-x)x^2 = x^7/12-2x^6/3+3x^5/2-x^4,$$

and performing the integral gives the answer 96.