I have problem with this: How many permutations of the letters A,B,D,E,I,K,M,N,R,U,Z are there so that none of the words: ARZEN, DRAK, DUM, DURAZ are subsequences of the permutation. This means it should be impossible to make these words by leaving out letters from the permutation, but leaving the remaining ones in order.
This task is about Inclusion-exclusion principle, but I can't understand.
Can anyone explain me how to solve this task? thanks
edit:I have understood the complexity of this question just now. A real task also describe, that: sequence can't have any of words {ARZEN,DRAK,DUM,DURAZ}. That means that sequence "A B D R K Z M E N U I" also should not be counted, because the bold letters form the forbidden word ARZEN. Sequence must have 11 letters.
Let's denote the set of permutations with subsequence $s$ by $B_s$. The result is $$11! - \left(|B_{ARZEN}| + |B_{DRAK}| + \ldots\right) + \left(|B_{ARZEN}\cap B_{DRAK}|+\ldots\right) - \left(|B_{ARZEN}\cap B_{DRAK}\cap B_{DUM}|+\ldots\right) + |B_{ARZEN}\cap B_{DRAK}\cap B_{DUM}\cap B_{DURAZ}|. $$
For example: $|B_{ARZEN}|= 6\cdot7\cdots11=\frac{11!}{5!},$ (we have $6$ possibilities for inserting one letter to the word $ARZEN$, $7$ possibilities for second letter, etc.
$|B_{ARZEN}\cap B_{DRAK}|=0$ because of letters $R$ and $A$,
$|B_{DURAZ}\cap B_{DUM}|=4\cdot 7\cdot8\cdots11.$ ($4$ possibilities for inserting $M$ to $DURAZ$, etc.)