Use Inclusion-Exclusion to find the number of arrangements of 4 A's, 5 B's, 6 C's, 7 D's , 8 E's with exactly 2 adjacent C's

242 Views Asked by At

I found the number of arrangements in the problem stated above by arranging the letters other than C and then counting the number of ways to insert the C's into the gaps, giving an answer of

$\displaystyle\hspace{1.2 in}\frac{24!}{4!5!7!8!}\binom{25}{5}\binom{5}{1}=281625478590456000$,

but I would like to find out how to work this problem using Inclusion-Exclusion instead.

2

There are 2 best solutions below

4
On BEST ANSWER

To find the number of arrangements with exactly one pair of C's, we must use a generalization of the Inclusion-Exclusion Principle. Let $A_k$ denote the set of arrangements with $k$ pairs of adjacent C's.

One pair of adjacent C's

We have $29$ objects to arrange: $4$ A's, $5$ B's, $1$ CC, $4$ C's, $7$ D's, $8$ E's. They can be arranged in $$|A_1| = \frac{29!}{4!5!1!4!7!8!}$$ distinguishable ways.

Two pairs of adjacent C's

Two disjoint pairs of C's: We have $28$ objects to arrange: $4$ A's, $5$ B's, $2$ CC's, $2$ C's, $7$ D's, $8$ E's. They can be arranged in $$\frac{28!}{4!5!2!2!7!8!}$$ distinguishable ways.

Two overlapping pairs of C's: We have $28$ objects to arrange: $4$ A's, $5$ B's, $1$ CCC, $3$ C's, $7$ D's, $8$ E's. They can be arranged in $$\frac{28!}{4!5!1!3!7!8!}$$ distinguishable ways.

Hence, $$|A_2| = \frac{28!}{4!5!2!2!7!8!} + \frac{28!}{4!5!1!3!7!8!}$$

Three pairs of adjacent C's

Three disjoint pairs of adjacent C's: We have $27$ objects to arrange: $4$ A's, $5$ B's, $3$ CC's, $7$ D's, $8$ E's. They can be arranged in $$\frac{27!}{4!5!3!7!8!}$$ distinguishable ways.

One pair of adjacent C's and two overlapping pairs of adjacent C's: We have $27$ objects to arrange: $4$ A's, $5$ B's, $1$ CC, $1$ CCC, $1$ C, $7$ D's, $8$ E's. They can be arranged in $$\frac{27!}{4!5!1!1!1!7!8!}$$ distinguishable ways.

Three overlapping pairs of adjacent C's: We have $27$ objects to arrange: $4$ A's, $5$ B's, $1$ CCCC, $2$ C's, $7$ D's, $8$ E's. They can be arranged in $$\frac{27!}{4!5!1!2!7!8!}$$ distinguishable ways.

Hence, $$|A_3| = \frac{27!}{4!5!3!7!8!} + \frac{27!}{4!5!1!1!1!7!8!} + \frac{27!}{4!5!1!2!7!8!}$$

Four pairs of adjacent C's

Two sets of two overlapping pairs of adjacent C's: We have $26$ objects to arrange: $4$ A's, $5$ B's, $2$ CCC's, $7$ D's, $8$ E's. They can be arranged in $$\frac{26!}{4!5!2!7!8!}$$ distinguishable ways.

One pair of adjacent C's and three overlapping pairs of adjacent C's: We have $26$ objects to arrange: $4$ A's, $5$ B's, $1$ CC, $1$ CCCC, $7$ D's, $8$ E's. They can be arranged in $$\frac{26!}{4!5!1!1!7!8!}$$ distinguishable ways.

Four overlapping pairs of adjacent C's: We have $26$ objects to arrange: $4$ A's, $5$ B's, $1$ CCCCC, $1$ C, $7$ D's, $8$ E's. They can be arranged in $$\frac{26!}{4!5!1!1!7!8!}$$ distinguishable ways.

Hence, $$|A_4| = \frac{26!}{4!5!2!7!8!} + \frac{26!}{4!5!1!1!7!8!} + \frac{26!}{4!5!1!1!7!8!}$$

Five pairs of adjacent C's

We have $25$ objects to arrange: $4$ A's, $5$ B's, $1$ CCCCCC, $7$ D's, $8$ E's. They can be arranged in $$|A_5| = \frac{25!}{4!5!1!7!8!}$$ distinguishable ways.

Let $|B_k|$ denote the number of arrangements with at least $k$ pairs of adjacent C's.

Number of arrangements with at least one pair of adjacent C's $$|B_1| = |A_1| - |A_2| + |A_3| - |A_4| + |A_5|$$

Number of arrangements with at least two pairs of adjacent C's $$|B_2| = |A_2| - |A_3| + |A_4| - |A_5|$$

Number of arrangements with at least three pairs of adjacent C's $$|B_3| = |A_3| - |A_4| + |A_5|$$

Number of arrangements with at least four pairs of adjacent C's $$|B_4| = |A_4| - |A_5|$$

Number of arrangements with five pairs of adjacent C's $$|B_5| = |A_5|$$

The number of arrangements with exactly one pair of adjacent C's is \begin{align*} |B_1| & - |B_2| + |B_3| - |B_4| + |B_5|\\ & = (|A_1| - |A_2| + |A_3| - |A_4| + |A_5|) - (|A_2| - |A_3| + |A_4| - |A_5|) + (|A_3| - |A_4| + |A_5|) - (|A_4| - |A_5|) + |A_5|\\ & = |A_1| - 2|A_2| + 3|A_3| - 4|A_4| + 5|A_5|\\ & = 281625478590456000 \end{align*}

11
On

4A,5B,1 Pair of C, 4C, 7D, 8E

$A1=\frac{29!}{4!*5!*7!*8!*4!.2}$

4A,5B,2 Pair of C, 2C, 7D, 8E

$A2=\frac{28!}{4!*5!*7!*8!*2!*2!.4}$

4A,5B,3 Pair of C, 7D, 8E

$A3=\frac{27!}{4!*5!*7!*8!*3!.8}$

4A,5B,1 Pair of C,1 triplet of C, 1C, 7D, 8E

$A4=\frac{27!}{4!*5!*7!*8!*3!*2}$

4A,5B,1 Pair of C,1 quadrapulet of C, 7D, 8E

$A5=\frac{26!}{4!*5!*7!*8!*4!.2}$

Using Principle of Exclusion and INclusion:

$A = A1-A2+A3-A4+A5=2.81034E+17$