Liczba słów

[schnier]

Znajdź liczbę słów długości \(\displaystyle{ 8}\), w których każda z liter \(\displaystyle{ A, B, C, D}\) występuje dwa razy, przy czym dokładnie jedna para jednakowych liter występuje na sąsiednich pozycjach.

Moje rozwiązanie: alternatywnie, możemy zapytać, ile jest ciągów długości \(\displaystyle{ 6}\), w których każda z liter \(\displaystyle{ A, B, C}\) występuje dwa razy i żadna para liter na sąsiednich pozycjach nie jest złożona z jednakowych liter. W takim \(\displaystyle{ 6}\)-literowym ciągu patrzymy na pierwsze trzy pozycje, mamy dwa przypadki:
1) na pierwszych trzech pozycjach są litery \(\displaystyle{ A, B, C}\)
2) z pierwszych trzech dwie są jednakowe
No to dla 1) mamy \(\displaystyle{ 3 \cdot 2 \cdot 2 \cdot 2 = 24}\), a dla 2) jest \(\displaystyle{ 3 \cdot 2 = 6}\), łącznie \(\displaystyle{ 30}\) takich możliwości.
Ponieważ trzy litery spośród czterech możemy wybrać na cztery sposoby, to \(\displaystyle{ 4 \cdot 30 = 120}\). Teraz wybieramy miejsce na parę sąsiednich, jednakowych liter, czyli \(\displaystyle{ 120 \cdot 7 = 840}\).

Czy to rozwiązanie jest prawidłowe?

[Premislav]

alternatywnie, możemy zapytać, ile jest ciągów długości \(\displaystyle{ 6}\), w których każda z liter \(\displaystyle{ A, B, C}\) występuje dwa razy i żadna para liter na sąsiednich pozycjach nie jest złożona z jednakowych liter.

No chyba nie. Przecież jak masz ustawienie
\(\displaystyle{ ACBBCA}\), to nie jest ono sześciowyrazowym ciągiem, w którym nie ma tych samych liter na żadnych sąsiednich dwóch pozycjach (wszak są dwie \(\displaystyle{ B}\) na trzeciej i czwartej pozycji), a jednak jeśli dołożysz po środku \(\displaystyle{ DD}\), to otrzymasz ośmiowyrazowy ciąg spełniający warunki zadania. Nie zliczasz w ten sposób takich przypadków.

[schnier]

Czy to jedyne przypadki, które pominąłem? Jeśli tak, to czy wynik wynosi \(\displaystyle{ 840 + 4 \cdot 5 \cdot 6 = 960}\)?

[Premislav]

Tak, to są jedyne przypadki, które wcześniej pominąłeś, natomiast nie wiem, jak je zliczyłeś, jestem słaby z kombinatoryki.

[schnier]

Powinienem był napisać \(\displaystyle{ 5!}\), ponieważ na \(\displaystyle{ 4}\) sposoby wybieram \(\displaystyle{ 3}\) litery spośród \(\displaystyle{ {A, B, C, D}}\) do \(\displaystyle{ 6}\)-elementowego ciągu, na \(\displaystyle{ 3}\) sposoby wybieram parę takich samych sąsiadujących liter, na \(\displaystyle{ 5}\) sposobów mogę wybrać miejsce dla tej pary w \(\displaystyle{ 6}\)-elementowym ciągu, wtedy pozostałe litery mogę ułożyć na \(\displaystyle{ 2}\) sposoby i żeby uzyskać odpowiedni ciąg \(\displaystyle{ 8}\)-elementowy, na \(\displaystyle{ 1}\) sposób mogę wstawić parę identycznych, sąsiadujących (jeszcze nie używanych) liter (pomiędzy wcześniej wstawioną parę). Wtedy odpowiedź to \(\displaystyle{ 960}\).

Próbowałem rozwiązać to zadanie innym sposobem i wyszło mi \(\displaystyle{ 984}\), któryś z tych wyników jest poprawny?

Drugie rozwiązanie:
Rozpatruję \(\displaystyle{ 8}\)-elementowe ciągi utworzone z elementów zbiorów \(\displaystyle{ \left\{AA, BB, CC, DD \right\}, \left\{AA, BB, CC, D \right\}, \left\{AA, BB, C, D \right\}, \left\{AA, B, C, D \right\}}\) (zapis \(\displaystyle{ AA}\) oznacza, że \(\displaystyle{ A}\) może występować tylko podwójnie, obok siebie) takie, że litery "podwójne" występują raz, a litery "pojedyncze" dwa razy w każdym z takich ciągów (czyli każda litera występuje \(\displaystyle{ 2}\) razy). W ten sposób chcę policzyć wszystkie \(\displaystyle{ 8}\)-elementowe ciągi składające się z liter \(\displaystyle{ \left\{A, B, C, D \right\}}\) takie, że każda litera wystąpi \(\displaystyle{ 2}\) razy i tylko \(\displaystyle{ A}\) może sąsiadować z taką samą jak ona literą.

\(\displaystyle{ |A| = |\left\{AA, BB, CC, DD \right\} | = 4!}\)
\(\displaystyle{ |B| = |\left\{AA, BB, CC, D \right\}| = {5 \choose 2} \cdot 3! = \frac{5!}{2}}\)
\(\displaystyle{ |C| = |\left\{AA, BB, C, D \right\}| = {6 \choose 2} \cdot {4 \choose 2} \cdot 2! = \frac{6!}{4}}\)
\(\displaystyle{ |D| = |\left\{AA, B, C, D \right\}| = {7 \choose 2} \cdot {5 \choose 2} \cdot {3 \choose 2} = \frac{7!}{8}}\)

Teraz zauważam, że \(\displaystyle{ A \subset B \subset C \subset D}\).
Z zasady włączeń i wyłączeń:
\(\displaystyle{ \frac{7!}{8} - 3 \cdot \frac{6!}{4} + 3 \cdot \frac{5!}{2} - 4! = 246}\)
I jeszcze razy \(\displaystyle{ 4}\), bo tak samo mogę postąpić dla \(\displaystyle{ B, C, D}\), czyli \(\displaystyle{ 4 \cdot 246 = 984}\)