Number of ways the word 'Success' can be arranged, such that no two S's and C's are together.
Arrangement of the word 'Success'
-
0No, ignore the capitalization. – 2012-06-24
6 Answers
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.
We start with all arrangements with non-consecutive "S"s, then subtract those where the "C"s are together.
That is, we begin with the arrangements with non-consecutive "S"s over the alphabet {S,U,C,C,E,S,S} and then subtract the arrangements with non-consecutive "S"s over the alphabet {S,U,CC,E,S,S}. Note the double "C" in the second alphabet.
Using the formula from my answer here, we get
${5\choose 3}{4!\over 2!}-{4\choose 3}{3!}=120-24=96. \ \ \ \ $
-
0@IshaanSingh Thanks, I've corrected it. – 2012-06-24
The total number of permutation of letters (T)= $\frac{7!}{2!3!}$
With two cc
together (A)= $\frac{6!}{2!}$
With three ss
together (B)= $\frac{6!}{2!} - \frac{5!}{2!}$
With both ss
and cc
together (C)= $5! - 4!$
Answer = T - A - B + C = 96
EDIT::
The number of unique permutation of consecutive $t-1$ $s$'es out of $t$ $s$'es in total of $n$ elements is given by $(n-(t-1))! - (n -t)!$ and this does not include $t$ s'es.
Matlab code for answer:
P = unique(perms(['s' 'u' 'c' 'c' 'e' 's' 's']), 'rows'); count = 0; for i = 1:length(P) for j = 1:6 if P(i,j) == P(i,j+1) count = count+1; break; end end end disp([length(P), count, length(P)-count]);
-
0@Dan try for $|a|b|s|s|$ and $|a|s|s|s|$ the cases where you get consecutive $ss$ – 2012-06-24
Place the letters S separated by some space. This gives four possible spaces for the remaining letters including the ends. Choose 2 of these spaces for the C letters; that is 6 possibilities. If the C letters are placed at the ends are two ways to place the U and E. The configuration would look like CSXSXSC. There are thus 2 possibilities. If only one C is at an end, the other is interior say CSCSXS then we can place the U&E in the position of the X and then place the other letter in one of 7 positions for a total of 14 possibilities. If both C letters are interior then we have SCSCS and so we can place the U in any of 6 positions and then the E in any of 7 positions so we get 42 possibilities. This gives a grand total of 42+4*14+2=100. (I've probably overlooked something.)
In my opinion the answer would be as follows $ \frac{7!}{3!\cdot 2!} = 420 $ ways we can arrange word success
by: Javed Masood - FUUAST
-
0You did not factor in the condition that the 's' can not repeat next to each other, nor the 'c'. – 2013-04-22
The total number of permutation of letters (T)= 7! 3!2!
Answer = N!/(N1!*NK!) = 7!/(3!*2!)= 420
The answer from April 22 at 0535 is correct. the rest are dead wrong.
-
1This is incorrect, as Willie Wong's comment pointed out on said answer. – 2013-11-09