5
$\begingroup$

Simple task from combinatorics: How much sequences does exist, that consist of letters A, B, C, D, ..., O, P; if no sequence could have any of these words: PONK, DOBA, COP. This task is about Inclusion-exclusion principle, but I can't understand why. I think that sets that inlude PONK, COP or DOBA doesn't have any common elements, because there is just one letter O. Can anyone explain me how to solve this task? thanks

Oh, I have understood the complexity of this question just now. A real task also describe, that:

edit: sequence can't have any of words {PONK, DOBA, COP} also if we delete some letters. That means that sequence A P C O D N E K F ... also should not be counted

1 Answers 1

4

In the corrected problem there are still $16!$ sequences altogether. The number that include the letters PONK in that order (but not necessarily adjacent) can be computed as follows: there are $\binom{16}4$ ways to choose the four positions to be filled by the letters P, O, N, and K, and there are then $12!$ ways to permute the remaining letters, so there are $\binom{16}412!$ sequences that contain ...P...O...N...K... .

In similar fashion you can count the sequences that contain ...D...O...B...A... and those that contain ...C...O...P... . However, the sets $\{\text{P,N,K}\}$, $\{\text{D,B,A}\}$, and $\{\text{C,P}\}$ are pairwise disjoint, so a sequence can contain two or even all three of these subsequences, and we’ll need to go through the complete inclusion-exclusion calculation.

Let’s try to count the sequences that contain both ...P...O...N...K... and ...D...O...B...A... . First we choose $7$ of the $16$ places for the letters P, O, N, K, D, B, and A; this can be done in $\binom{16}7$ ways. The O must fill the third of these seven positions. The P and D must fill the first two, but they can do so in either order. There are $\binom42$ ways to choose the two positions for N and K, which must go in that order, and B and A will then fill the remaining positions, again in that order. Finally, the other $9$ letters can be permuted arbitrarily. The total is therefore

$\binom{16}7\cdot2\cdot\binom42\cdot9!\;.$

You should be able to use similar analyses to calculate the remaining terms of the inclusion-exclusion calculation.

  • 0
    @George: You’re very welcome.2012-12-03