I have the following question:
We are going to generate permutations from a,a,b,b,b,c,c,c,c. Please compute the number of permutations such that:
(a) for any consecutive 4 elements, they are not all the same;
(b) for any consecutive 3 elements, they are not all the same;
(c) for any consecutive 2 elements, they are not all the same.
See Arrangements of $a,a,b,b,b,c,c,c,c$ in which no four/three/two consecutive letters are the same for the first two parts.
I got an answer for part c but I am not sure if it is correct or not.
My step is the following.
I found that there are six pairs containing adjacent identical letters. I will define them as$S_1, S_2,…, S_6$ the small number is the number of pairs of adjacent identical letters.
$$S_0 =\binom{9}{2,3,4}$$
$$S_1 =\binom{8}{3,4} + \binom{8}{2,4} + \binom{8}{2,3,2}$$
$$S_2 = \frac{7!}{4!}+\binom{7}{3,2}+\binom{7}{4,2} + \binom{7}{3,2} + \binom{6}{3,2}+\binom{7}{2,2}$$
$$S_3 = \frac{6!}{4!}+\frac{6!}{3!}+\frac{5!}{3!} + \binom{6}{2,2} + \frac{6!}{2!} + \frac{5!}{2!}$$
$$S_4 = \frac{5!}{2!}+\frac{5!}{3!}+\frac{5!}{2!} + \frac{5!}{2!} + {5!}+{4!}$$
$$S_5 = {4!}+{3!}+\frac{4!}{2!} $$
$$S_6 = 3!$$
I sum these up by the inclusion-exclusion principle, and I got the answer of the following:
$$N = S_0 – S_1+ S_2- S_3 +S_4 -S_5+ S_6 = 473$$
I want to know if there is any miscalculation or if the wrong steps exist. Could anyone please help?
Best Answer
Such problems become intractable very rapidly, I prefer to use a form of the generalized Laguerre polynomial as described by Jair Taylor
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$.
The number of permutations will be given by
We get $q_2(x) = (x^2-2x)/2!$
$q_3(x) = (x^3-6x^2+6x)/3!$
$q_4(x) = (x^4-12x^2+36x^2-24x)/4!$
Using the above method, I get an answer of 79