Słowotok - liczba wszystkich ciągów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
przem_as
Użytkownik
Użytkownik
Posty: 105
Rejestracja: 20 wrz 2006, o 21:51
Płeć: Mężczyzna
Podziękował: 25 razy
Pomógł: 10 razy

Słowotok - liczba wszystkich ciągów

Post autor: przem_as »

Witajcie,
niedawno natrafiłem na aplikację Słowotok, która polega na ułożeniu jak najdłuższych wyrazów z 16 losowo wybranych liter ułożonych w kwadracie 4x4. Wyrazy muszą być co najmniej 3-literowe a litery muszą się stykać (nie tylko bokami, ale również "wierzchołkami").

Kolega napisał programik, który dla określonego słownika generuje listę słów, które można odnaleźć zgodnie z tymi zasadami. Algorytm sprawdza wszystkie możliwe ciągi liter i zwraca go, jeśli występuje w słowniku.

Chciałem jakoś oszacować liczbę wszystkich ciągów. Zacząłem od tego, że pominąłem układ tych liter. Założyłem, że mamy 16-elementowy zbiór, w którym musimy znaleźć wszystkie co najmniej 3-elementowe podzbiory i poszukać ich wszystkich możliwych permutacji. Wtedy liczba wszystkich ciągów liter wynosi:
\(\displaystyle{ \sum_{k=3}^{16} {16 \choose k}\cdot k!}\)
Oczywiście jest to bardzo grube oszacowanie i w ogóle nie oddaje charakteru możliwych ciągów, ale niestety nie umiem jeszcze bardziej tego urealnić. Macie jakieś pomysły?
ODPOWIEDZ