Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks a lot, I didn't thought that it would be so easy. total nr. of sequences = 16! nr. with PONK = 13! nr. with DOBA = 13! nr. with COP = 14! so result should be 16! - 13! - 13! - 14! ? I just can't forget the main axiom of math - if somethings is solved easy - it is solved wrong –  George Dec 3 '12 at 0:10
    
@George: You’re welcome, and yes, your answer is correct. I like that axiom! :-) –  Brian M. Scott Dec 3 '12 at 0:21
    
Unfortunately, task was given in very interesting form, so I did a mistake in description. I am sorry. –  George Dec 3 '12 at 0:37
    
@George: I’ve updated the answer to reflect the corrected problem. –  Brian M. Scott Dec 3 '12 at 1:09
    
I really appreciate that. Thanks for your time and attention. –  George Dec 3 '12 at 1:28
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.