Words without subwords
Task number: 3491
How many sequences of the letters A, B, D, E, I, K, M, N, R, Ů, Z exist such that by removing letters we are never left with any of the (Czech) words:
Variant
BAR, DEN, RAZIE
Solution
The total number of possible words is \(11!\).
The number of words containing BAR is \(\frac{11!}{3!}\), because there are \(\binom{11}{3}\) ways to choose the positions where we write BAR and we can place the other letters in \(6!\) ways. (Alternatively we can imagine that only \(\frac{1}{3!}\) of the words have BAR in the correct order.) The number of words containing DEN is identital, and the number of words containing RAZIE is \(\frac{11!}{5!}\).
The number of words containing both BAR and DEN is \(\frac{11!}{3!3!}\), because we can choose one triple of positions for BAR, a second for DEN and we can arrange the remaining five letters in any way.
No words can contain BAR and RAZIE simultaneously (or all of the words BAR, RAZIE, DEN), because the letters R and A appear in a different order in the two words.
The number of words containing both DEN and RAZIE is \(5\frac{11!}{7!}\), because there are \(\binom{11}{7}\) ways to choose seven positions for the letters D,E,N,R,A,Z,I. The last two of these seven positions must contain E and N (in that order). The letter D may be in any one of the first five chosen positions, but as soon as we make this choice, the positions of R,A,Z,I are now fixed.
It remains to compute \(11!-2\frac{11!}{3!}-\frac{11!}{5!}+\frac{11!}{3!3!}+5\frac{11!}{7!}= 39{,}916,800-13{,}305,600-332{,}640+1{,}108,800+39{,}600=27{,}426,960 \)
Answer
The number of words we seek is \(11!-2\frac{11!}{3!}-\frac{11!}{5!}+\frac{11!}{3!3!}+5\frac{11!}{7!}=27{,}426,960\).
Variant
ARZEN, DRAK, DŮM, DŮRAZ
Solution
The total number of words is \(6!\).
Let \(A_1\) denote the set of words with the subword ARZEN. There are \(|A_1|=\frac{11!}{5!}\) of these; similarly for the subword DRAK we have \(|A_2|=\frac{11!}{4!}\), for DŮM \(|A_3|=\frac{11!}{3!}\) and for DŮRAZ \(|A_4|=\frac{11!}{5!}\).
In the word ARZEN we have the letters A and R in the opposite order as in the words DRAK and DŮRAZ, so \(\emptyset=A_1\cap A_2=A_1\cap A_4=A_1\cap A_2\cap A_3 = A_1\cap A_2 \cap A_4 = A_1\cap A_3 \cap A_4 = A_1\cap A_2 \cap A_3 \cap A_4\).
Further \(|A_1\cap A_3|=\frac{11!}{5!3!}\), \(|A_2\cap A_3|=\frac{11!}{6!}\binom{5}{3}\), \(|A_2\cap A_4|=\frac{11!}{6!}\binom{2}{1}\), \(|A_3\cap A_4|=\frac{11!}{6!}\binom{4}{1}\) a \(|A_2\cap A_3\cap A_4|=\frac{11!}{7!}\binom{5}{1}\binom{2}{1}\).
It remains to compute \(11!-\frac{11!}{5!}-\frac{11!}{4!}-\frac{11!}{3!}-\frac{11!}{5!} +\frac{11!}{5!3!}+\frac{11!}{6!}\binom{5}{3}+\frac{11!}{6!}\binom{2}{1}+\frac{11!}{6!}\binom{4}{1}-\frac{11!}{7!}\binom{5}{1}\binom{2}{1}=\\ =39{,}916,800-332{,}640-1663{,}200-6{,}652,800-332{,}640+55{,}440+\\ +554{,}400+110{,}880+221{,}760+79{,}200=31{,}957,200 \)
Answer
The number of words we seek is \(11!-\frac{11!}{5!}-\frac{11!}{4!}-\frac{11!}{3!}-\frac{11!}{5!} +\frac{11!}{5!3!}+\frac{11!}{6!}\binom{5}{3}+\frac{11!}{6!}\binom{2}{1}+\frac{11!}{6!}\binom{4}{1}-\frac{11!}{7!}\binom{5}{1}\binom{2}{1}=31{,}957,200 \)
