Podciągi w ciągu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
strefa61
Użytkownik
Użytkownik
Posty: 185
Rejestracja: 12 gru 2013, o 22:22
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 77 razy

Podciągi w ciągu

Post autor: strefa61 »

Hej, mam takie zadanie:
Dajmy, że mamy litery \(\displaystyle{ a,b,c,d}\) i kolejno liter jest \(\displaystyle{ 5,6,7,8}\) i chcę ułożyć wszystkie litery w ciągi (taka sama litera nie jest rozróżnialna), ale takie ciągi, w których nie wystąpuje podciąg \(\displaystyle{ ab}\).
Czy mój sposób jest ok:

załóżmy, że rozróżnimy litery \(\displaystyle{ a}\), czyli mamy \(\displaystyle{ a_1,a_2,\ldots}\)
\(\displaystyle{ A_i}\) to zbiór wszystkich ciągów, w których występuje podciąg \(\displaystyle{ a_ib}\). Liczę z zasady włączeń i wyłączeń:
\(\displaystyle{ \left| A_i\right| = {25 \choose 1} {24 \choose 4} 4! \left( {20 \choose 7} {13 \choose 8} \right) }\), gdzie pierwsze ustawiam \(\displaystyle{ a_ib}\), następnie ustawiam pozostałe cztery \(\displaystyle{ a_k}\) i uwzględniam ich kolejność, a w nawiasie ustawiam na pozostałych miejscach \(\displaystyle{ c}\) oraz \(\displaystyle{ d}\).

Analogicznie:
\(\displaystyle{ \left| A_i \cap A_j \right| = {24 \choose 2} 2! {22 \choose 3} 3! \left( {19 \choose 7} {12 \choose 8} \right) }\), gdzie w pierwszym czynniku rozkładam \(\displaystyle{ a_ib}\) oraz \(\displaystyle{ a_jb}\) uwzględniając kolejność, potem rozkładam pozostałe trzy \(\displaystyle{ a_k}\) i uwzględniam kolejność itd. zaś na końcu podzielę całą sumę z włączeń i wyłączeń przez \(\displaystyle{ 5!}\), żeby wyrzucić 'rozróżnianie \(\displaystyle{ a_i}\).

Może ktoś potwierdzić, że sposób jest ok? Może jest jakiś sprytny trik na liczenie tego bez klepania 'na piechotę'?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Podciągi w ciągu

Post autor: kerajs »

Proponuję porównanie wyników z rozwiązaniem:
Ustawiam litery b,c,d na \(\displaystyle{ {21! \choose 6!7!8!}}\) sposobów.
Rozważam przypadki:
1) litery a, a, a, a, a nie sąsiadują ze sobą.
W powyższe ciągi mogę je wstawić na \(\displaystyle{ {16 \choose 5} }\) sposobów.
2) układy aa, a, a, a nie sąsiadują ze sobą.
W powyższe ciągi mogę je wstawić na \(\displaystyle{ {16 \choose 1} {15 \choose 3} }\) sposobów
3) układy aaa, a, a nie sąsiadują ze sobą.
W powyższe ciągi mogę je wstawić na \(\displaystyle{ {16 \choose 1} {15 \choose 2} }\) sposobów.
4) układy a, aa, aa nie sąsiadują ze sobą.
W powyższe ciągi mogę je wstawić na \(\displaystyle{ {16 \choose 1} {15 \choose 2} }\) sposobów.
5) układy aaaaa, a nie sąsiadują ze sobą.
W powyższe ciągi mogę je wstawić na \(\displaystyle{ {16 \choose 1} {15 \choose 1} }\) sposobów.
6) układy aaa, aa nie sąsiadują ze sobą.
W powyższe ciągi mogę je wstawić na \(\displaystyle{ {16 \choose 1} {15 \choose 1} }\) sposobów.
7) układ aaaaa w powyższe ciągi mogę wstawić na \(\displaystyle{ {16 \choose 1} }\) sposobów..
ODPOWIEDZ