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?