Slova bez podslov
Úloha číslo: 3475
Kolik existuje pořadí písmen A, B, D, E, I, K, M, N, R, Ů, Z takových, že po vynechání některých písmen nevznikne ani jedno ze slov:
Varianta
BAR, DEN, RAZIE
Řešení
Všech možných slov je \(11!\).
Těch, která obsahují BAR je \(\frac{11!}{3!}\), protože \(\binom{11}{3}\) způsoby vybereme ti pozice, kam zapíšeme BAR a ostatní písmena rozmístíme \(8!\) způsoby. (Alternativně si lze představit, že jen \(\frac{1}{3!}\) slov má BAR ve správném pořadí.) Slov, co obsahuji DEN je stejně a slov, co obsahují RAZIE je \(\frac{11!}{5!}\).
Slov, co obsahují BAR a DEN je \(\frac{11!}{3!3!}\), protože lze vybrat jednu trojici pozic pro BAR, druhou pro DEN a zbylých pět písmena rozmístit libovolně.
Žádné slovo neobsahuje BAR a RAZIE zároveň (a tedy ani i DEN), protože pořadí písmen R a A je v obou různé.
Slov, co obsahují DEN a RAZIE je \(5\frac{11!}{7!}\), protože \(\binom{11}{7}\) zvolíme sedm pozic pro písmena D,E,N,R,A,Z,I. Na posledních dvou z těchto sedmi pozic musí být E a N (v tomto pořadí). Písmeno D může být na libovolné z prvních pěti vybraných pozic, ale jakmile učiníme tuto volbu, je umístění písmen R,A,Z,I už dané.
Zbývá dopočítat \(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 \)
Odpověď
Požadovaných slov je \(11!-2\frac{11!}{3!}-\frac{11!}{5!}+\frac{11!}{3!3!}+5\frac{11!}{7!}=27\,426\,960\).
Varianta
ARZEN, DRAK, DŮM, DŮRAZ
Řešení
Všech slov je \(11!\).
Označme symbolem \(A_1\) množinu slov s podslovem ARZEN. Je jich \(|A_1|=\frac{11!}{5!}\), podobně pro podslovo DRAK máme \(|A_2|=\frac{11!}{4!}\), pro DŮM \(|A_3|=\frac{11!}{3!}\) a pro DŮRAZ \(|A_4|=\frac{11!}{5!}\).
Ve slově ARZEN mají písmena A a R obrácené pořadí než ve slovech DRAK a DŮRAZ, proto \(\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\).
Dále \(|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}\).
Zbývá dopočítat \(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-1\,663\,200-6\,652\,800-332\,640+55\,440+\\ +554\,400+110\,880+221\,760+79\,200=31\,957\,200 \)
Odpověď
Hledaných slov je \(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 \).
