Prawdopodobieństwo, że nie narysuje słowa z worka liter w Scrabble

Załóżmy, że masz torbę z płytkami, z których każda zawiera literę. Są kafelki z literą „A”, z „B” itd., I „symbole wieloznaczne” (mamy ). Załóżmy, że masz słownik ze skończoną liczbą słów. Z torby wybierasz płytek bez wymiany. Jak obliczysz (lub oszacujesz) prawdopodobieństwo, że możesz sformułować zero słów ze słownika, biorąc pod uwagę wybrane płytek?n A n B n ∗ n = n A + n B + … + n Z + n ∗ k $n$$n_A$$n_B$$n_*$$n = n_A + n_B + \ldots + n_Z + n_*$$k$$k$

W przypadku osób niezaznajomionych ze Scrabble (TM) można użyć znaku zastępczego, aby dopasować dowolną literę. Zatem słowo [ BOOT ] może być „ortograficzne” z kafelkami „B”, „*”, „O”, „T”.

Aby dać wyobrażenie o skali problemu, jest małe, na przykład 7, wynosi około 100, a słownik zawiera około 100 000 słów o wielkości lub mniejszej.n $k$$n$$k$

edytuj: Przez „uformuj słowo” mam na myśli słowo o długości nie większej niż . Tak więc, jeśli słowo [ A ] znajduje się w słowniku, to poprzez wyciągnięcie nawet jednego „A” z torby, „uformowano słowo”. Problem symboli wieloznacznych jest radykalnie uproszczony, jeśli można założyć, że w słowniku znajdują się słowa o długości 1. Jeśli tak, każde losowanie symbolu wieloznacznego może automatycznie dopasować długość 1 słowa, a zatem można skoncentrować się na przypadku, w którym nie ma symboli wieloznacznych. Tak więc bardziej śliska forma problemu nie zawiera słów 1-literowych w słowniku.$k$

Powinienem również wyraźnie stwierdzić, że kolejność, w jakiej litery są wyciągane z torby, jest nieistotna. Nie trzeba rysować liter w „poprawnej” kolejności słowa.

To jest (długi!) Komentarz do dobrej pracy opublikowanej przez @vqv w tym wątku. Ma na celu uzyskanie ostatecznej odpowiedzi. Ciężko pracował nad uproszczeniem słownika. Pozostaje tylko wykorzystać go w pełni. Jego wyniki sugerują, że możliwe jest rozwiązanie z użyciem siły brutalnej . W końcu, włączając w to symbol wieloznaczny, istnieje co najwyżej słów, które można sformułować za pomocą 7 znaków, i wygląda na to, że mniej niż 1/10000 z nich - powiedzmy, około miliona - nie będzie zawierać niektórych poprawnych słowo. $27^7 = 10,460,353,203$

Pierwszym krokiem jest uzupełnienie minimalnego słownika znakiem wieloznacznym „?”. 22 litery pojawiają się w dwuliterowych słowach (wszystkie oprócz c, q, v, z). Dołącz znak wieloznaczny do tych 22 liter i dodaj je do słownika: {a ?, b ?, d ?, ..., y?} Już są. Podobnie możemy sprawdzić minimalne trzyliterowe słowa, powodując dodatkowe słowa pojawić się w słowniku. Na koniec dodajemy „??” do słownika. Po usunięciu powtórzeń zawiera 342 minimalne słowa.

Elegancki sposób postępowania - taki, który używa bardzo niewielkiej ilości kodowania - polega na postrzeganiu tego problemu jako algebraicznego . Słowo, uważane za nieuporządkowany zestaw liter, jest po prostu monomialne. Na przykład „spats” to monomialne . Słownik jest zatem zbiorem monomialów. To wygląda jak$a p s^2 t$

$$\{a^2, a b, a d, ..., o z \psi, w x \psi, \psi^2\}$$

(gdzie, aby uniknąć zamieszania, napisałem dla znaku wieloznacznego).$\psi$

Stojak zawiera prawidłowe słowo, tylko wtedy, gdy to słowo dzieli stojak.

Bardziej abstrakcyjnym, ale niezwykle potężnym sposobem na powiedzenie tego jest to, że słownik generuje idealne w pierścieniu wielomianowym i że stojaki z poprawnymi słowa stają się zerowe w pierścieniu ilorazowym , natomiast stojaki bez prawidłowych słów pozostają niezerowe w ilorazie. Jeśli utworzymy sumę wszystkich stojaków w i obliczymy je w tym pierścieniu ilorazowym, wówczas liczba stojaków bez słów jest równa liczbie różnych jednomianów w ilorazie.R = Z [ a , b , … , z , ψ ] R / I $I$$R = \mathbb{Z}[a, b, \ldots, z, \psi]$$R/I$$R$

Ponadto suma wszystkich stojaków w jest łatwa do wyrażenia. Niech będzie sumą wszystkich liter alfabetu. zawiera jeden monomial na każdy stojak. (Jako dodatkowy bonus, jego współczynniki liczą liczbę sposobów, w jakie można utworzyć każdy stojak, co pozwala nam obliczyć jego prawdopodobieństwo, jeśli chcemy.)α = a + b + ⋯ + z + ψ α $R$$\alpha = a + b + \cdots + z + \psi$$\alpha^7$

Jako prosty przykład (aby zobaczyć, jak to działa) załóżmy, że (a) nie używamy symboli wieloznacznych i (b) wszystkie litery od „a” do „x” są uważane za słowa. Zatem jedyne możliwe stojaki, z których nie można utworzyć słów, muszą składać się wyłącznie z liter y i z. Obliczamy modulo ideału generowanego przez krok po kroku, w ten sposób: { a , b , c , … , x $\alpha=(a+b+c+\cdots+x+y+z)^7$$\{a,b,c, \ldots, x\}$

$$\eqalign{ \alpha^0 &= 1 \cr \alpha^1 &= a+b+c+\cdots+x+y+z \equiv y+z \mod I \cr \alpha^2 &\equiv (y+z)(a+b+\cdots+y+z) \equiv (y+z)^2 \mod I \cr \cdots &\cr \alpha^7 &\equiv (y+z)^6(a+b+\cdots+y+z) \equiv (y+z)^7 \mod I \text{.} }$$

Z ostatecznej odpowiedzi możemy odczytać szansę otrzymania stojaka bez słów, : każdy współczynnik zlicza sposoby, w jakie można narysować odpowiedni stojak. Na przykład istnieje 21 (z 26 ^ 7 możliwych) sposobów na narysowanie 2 lat i 5 z, ponieważ współczynnik wynosi 21.$y^7 + 7 y^6 z + 21 y^5 z^2 + 35 y^4 z^3 + 35 y^3 z^4 + 21 y^2 z^5 + 7 y z^6 + z^7$$y^2 z^5$

Z elementarnych obliczeń wynika, że ​​jest to poprawna odpowiedź. Chodzi o to, że ta procedura działa niezależnie od zawartości słownika.

Zauważ, jak redukcja modułu mocy ideału na każdym etapie zmniejsza obliczenia: oto skrót ujawniony w tym podejściu. (Koniec przykładu.)

Systemy algebry wielomianowej realizują te obliczenia . Na przykład, oto kod Mathematica :

alphabet =  a + b + c + d + e + f + g + h + i + j + k + l + m + n + o + 
            p + q + r + s + t + u + v + w + x + y + z + \[Psi];
dictionary = {a^2, a b, a d, a e, ..., w z \[Psi], \[Psi]^2};
next[pp_] := PolynomialMod[pp alphabet, dictionary];
nonwords = Nest[next, 1, 7];
Length[nonwords]

(Słownik można zbudować w prosty sposób z min.dict @ vqv; wstawiłem tutaj wiersz pokazujący, że jest on wystarczająco krótki, aby można go było podać bezpośrednio, jeśli chcesz).

Wynik - który zajmuje dziesięć minut obliczeń - wynosi 577958. ( Uwaga: We wcześniejszej wersji tego komunikatu popełniłem niewielki błąd podczas przygotowywania słownika i otrzymałem 577940. Edytowałem tekst, aby odzwierciedlić to, co mam nadzieję teraz poprawne wyniki!) Nieco mniej niż milion oczekiwałem, ale tego samego rzędu wielkości.

Aby obliczyć szansę na uzyskanie takiego stojaka, musimy wziąć pod uwagę liczbę sposobów, w jakie można go wyciągnąć. Jak widzieliśmy w przykładzie, jest to równe jego współczynnikowi w . Szansa rysunek jakiś taki stojak jest sumą wszystkich tych współczynników, łatwo znaleźć poprzez ustawienie wszystkich liter równy 1:$\alpha^7$

nonwords /. (# -> 1) & /@ (List @@ alphabet)

Odpowiedź równa się 1066056120, co daje 10,1914% szansy na wyciągnięcie stojaka, z którego nie można utworzyć prawidłowego słowa (jeśli wszystkie litery są jednakowo prawdopodobne).

Gdy prawdopodobieństwa liter są różne, po prostu zamień każdą literę na szansę na narysowanie:

tiles = {9, 2, 2, 4, 12, 2, 3, 2, 9, 1, 1, 4, 2, 6, 8, 2, 1, 6, 4, 6, 
         4, 2, 2, 1, 2, 1, 2};
chances = tiles / (Plus @@ tiles);
nonwords /. (Transpose[{List @@ alphabet, chances}] /. {a_, b_} -> a -> b)

Wynik wynosi 1.079877553303%, dokładna odpowiedź (choć przy użyciu modelu przybliżonego, rysunek z zamiennikiem). Patrząc wstecz, dane zajęły cztery linie (alfabet, słownik i częstotliwości alfabetu) i tylko trzy linie do wykonania pracy: opisz, jak pobrać następną potęgę modulo , rekurencyjnie weź siódmą potęgę i zamień ją prawdopodobieństwa liter.$\alpha$$I$

Bardzo trudno jest narysować stojak, który nie zawiera żadnego poprawnego słowa w Scrabble i jego wariantach. Poniżej znajduje się program R, który napisałem w celu oszacowania prawdopodobieństwa, że ​​początkowy 7-kafelkowy stojak nie zawiera poprawnego słowa. Wykorzystuje podejście Monte Carlo i leksykon Words With Friends (nie mogłem znaleźć oficjalnego leksykonu Scrabble w łatwym formacie). Każda próba polega na narysowaniu 7-kafelkowego stojaka, a następnie sprawdzeniu, czy stojak zawiera prawidłowe słowo.

Minimalne słowa

Nie musisz skanować całego leksykonu, aby sprawdzić, czy stojak zawiera prawidłowe słowo. Wystarczy zeskanować minimalny leksykon składający się z minimalnej liczby słów. Słowo jest minimalne, jeśli nie zawiera innego słowa jako podzestawu. Na przykład „em” to minimalne słowo; „pusty” nie jest. Chodzi o to, że jeśli stojak zawiera słowo x, to musi również zawierać dowolny podzbiór x . Innymi słowy: stojak nie zawiera słów iff nie zawiera minimalnych słów. Na szczęście większość słów w leksykonie nie jest minimalna, więc można je wyeliminować. Możesz także łączyć słowa równoważne permutacji. Udało mi się zmniejszyć leksykon Words With Friends z 172 820 do 201 minimalnych słów.

Symbole wieloznaczne można łatwo obsługiwać, traktując stojaki i słowa jako rozkład na litery. Sprawdzamy, czy stojak zawiera słowo, odejmując jedną dystrybucję od drugiej. Daje nam to numer każdej brakującej litery w stojaku. Jeśli suma tych liczb jest liczbą symboli wieloznacznych, to słowo znajduje się w szafie.$\leq$

Jedynym problemem związanym z podejściem monte carlo jest to, że wydarzenie, które nas interesuje, jest bardzo rzadkie. Dlatego oszacowanie przy wystarczająco małym błędzie standardowym powinno zająć wiele, wiele prób. Uruchomiłem mój program (wklejony na dole) z prób i uzyskałem szacunkowe prawdopodobieństwo 0,004, że początkowy stojak nie zawiera poprawnego słowa . Szacowany błąd standardowy tego oszacowania wynosi 0,0002. Uruchomienie mojego komputera Mac Pro zajęło zaledwie kilka minut, w tym pobranie leksykonu.$N=100,000$

Chciałbym sprawdzić, czy ktoś może wymyślić skuteczny algorytm dokładny. Wydaje się, że naiwne podejście oparte na wykluczeniu włączenia mogłoby obejmować wybuch kombinatoryczny.

Włączenie-wykluczenie

Myślę, że to złe rozwiązanie, ale tutaj i tak jest niepełny szkic. Zasadniczo możesz napisać program do wykonania obliczeń, ale specyfikacja byłaby skomplikowana.

Prawdopodobieństwo, które chcemy obliczyć, to Zdarzenie wewnątrz prawdopodobieństwa po prawej stronie jest zdarzeń: gdzie jest minimalnym leksykonem. Możemy go rozwinąć, stosując formułę włączenia-wykluczenia. Polega ona na rozważeniu wszystkich możliwych skrzyżowań powyższych wydarzeń. Niech oznacza zbiór mocy , czyli zbiór wszystkich możliwych podzbiorów . Następnie

$$P(k\text{-tile rack does not contain a word}) = 1 - P(k\text{-tile rack contains a word}) .$$ $$P(k\text{-tile rack contains a word}) = P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right),$$ $M$$\mathcal{P}(M)$$M$$M$ $$\begin{align} &P(k\text{-tile rack contains a word}) \\ &= P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{j=1}^{|M|} (-1)^{j-1} \sum_{S \in \mathcal{P}(M) : |S| = j} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \end{align}$$

Ostatnią rzeczą do określenia jest sposób obliczenia prawdopodobieństwa w ostatnim wierszu powyżej. Obejmuje wielowymiarową hipergeometrię. jest zdarzeniem, że regał zawiera każde słowo . Jest to ból, z którym trzeba sobie radzić z powodu symboli wieloznacznych. Będziemy musieli rozważyć, kondycjonując, każdy z następujących przypadków: stojak nie zawiera symboli wieloznacznych, stojak zawiera 1 symbol wieloznaczny, stojak zawiera 2 symbole wieloznaczne, ...

$$\cap_{x \in S} \{ k\text{-tile rack contains }x \}$$ $S$

Następnie

$$\begin{align} &P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{w=0}^{n_{*}} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} | k\text{-tile rack contains } w \text{ wildcards} \right) \\ &\quad \times P(k\text{-tile rack contains } w \text{ wildcards}) . \end{align}$$

Zatrzymam się tutaj, ponieważ rozszerzenia są trudne do napisania i wcale nie są pouczające. Aby to zrobić, łatwiej jest napisać program komputerowy. Ale do tej pory powinieneś zobaczyć, że podejście włączenia-wykluczenia jest trudne. Obejmuje warunki, z których każdy jest również bardzo skomplikowany. W przypadku leksykonu rozważałem powyżej .$2^{|M|}$$2^{|M|} \approx 3.2 \times 10^{60}$

Skanowanie wszystkich możliwych stojaków

Myślę, że jest to obliczeniowo łatwiejsze, ponieważ jest mniej możliwych stojaków niż możliwe podzbiory minimalnych słów. Sukcesywnie zmniejszamy zbiór możliwych wartości$k$-podstawiać stojaki, dopóki nie otrzymamy zestawu stojaków, które nie zawierają słów. W przypadku Scrabble (lub Words With Friends) liczba możliwych 7-kafelkowych półek wynosi kilkadziesiąt miliardów. Liczenie liczby tych, które nie zawierają możliwego słowa, powinno być wykonalne za pomocą kilkudziesięciu wierszy kodu R. Ale myślę, że powinieneś być w stanie zrobić coś lepszego niż tylko wyliczenie wszystkich możliwych stojaków. Na przykład „aa” to minimalne słowo. To natychmiast eliminuje wszystkie szafy zawierające więcej niż jedno „a”. Możesz powtórzyć innymi słowami. Pamięć nie powinna być problemem dla współczesnych komputerów. 7-kafelkowy stojak Scrabble wymaga mniej niż 7 bajtów pamięci. W najgorszym przypadku wykorzystalibyśmy kilka gigabajtów do przechowywania wszystkich możliwych stojaków, ale nie sądzę, że to też dobry pomysł. Ktoś może chcieć więcej o tym pomyśleć.

Program Monte Carlo R.

# 
#  scrabble.R
#  
#  Created by Vincent Vu on 2011-01-07.
#  Copyright 2011 Vincent Vu. All rights reserved.
# 

# The Words With Friends lexicon
# http://code.google.com/p/dotnetperls-controls/downloads/detail?name=enable1.txt&can=2&q=
url <- 'http://dotnetperls-controls.googlecode.com/files/enable1.txt'
lexicon <- scan(url, what=character())

# Words With Friends
letters <- c(unlist(strsplit('abcdefghijklmnopqrstuvwxyz', NULL)), '?')
tiles <- c(9, 2, 2, 5, 13, 2, 3, 4, 8, 1, 1, 4, 2, 5, 8, 2, 1, 6, 5, 7, 4, 
           2, 2, 1, 2, 1, 2)
names(tiles) <- letters

# Scrabble
# tiles <- c(9, 2, 2, 4, 12, 2, 3, 2, 9, 1, 1, 4, 2, 6, 8, 2, 1, 6, 4, 6, 4, 
#            2, 2, 1, 2, 1, 2)


# Reduce to permutation equivalent words
sort.letters.in.words <- function(x) {
  sapply(lapply(strsplit(x, NULL), sort), paste, collapse='')
}

min.dict <- unique(sort.letters.in.words(lexicon))
min.dict.length <- nchar(min.dict)

# Find all minimal words of length k by elimination
# This is held constant across iterations:
#   All words in min.dict contain no other words of length k or smaller
k <- 1
while(k < max(min.dict.length))
{
  # List all k-letter words in min.dict
  k.letter.words <- min.dict[min.dict.length == k]

  # Find words in min.dict of length > k that contain a k-letter word
  for(w in k.letter.words)
  {
    # Create a regexp pattern
    makepattern <- function(x) {
      paste('.*', paste(unlist(strsplit(x, NULL)), '.*', sep='', collapse=''), 
            sep='')
    }
    p <- paste('.*', 
               paste(unlist(strsplit(w, NULL)), 
                     '.*', sep='', collapse=''), 
               sep='')

    # Eliminate words of length > k that are not minimal
    eliminate <- grepl(p, min.dict) & min.dict.length > k
    min.dict <- min.dict[!eliminate]
    min.dict.length <- min.dict.length[!eliminate]
  }
  k <- k + 1
}

# Converts a word into a letter distribution
letter.dist <- function(w, l=letters) {
  d <- lapply(strsplit(w, NULL), factor, levels=l)
  names(d) <- w
  d <- lapply(d, table)
  return(d)
}

# Sample N racks of k tiles
N <- 1e5
k <- 7
rack <- replicate(N,
                  paste(sample(names(tiles), size=k, prob=tiles), 
                        collapse=''))

contains.word <- function(rack.dist, lex.dist)
{
  # For each word in the lexicon, subtract the rack distribution from the 
  # letter distribution of the word.  Positive results correspond to the 
  # number of each letter that the rack is missing.
  y <- sweep(lex.dist, 1, rack.dist)

  # If the total number of missing letters is smaller than the number of 
  # wildcards in the rack, then the rack contains that word
  any(colSums(pmax(y,0)) <= rack.dist[names(rack.dist) == '?'])
}

# Convert rack and min.dict into letter distributions
min.dict.dist <- letter.dist(min.dict)
min.dict.dist <- do.call(cbind, min.dict.dist)
rack.dist <- letter.dist(rack, l=letters)

# Determine if each rack contains a valid word
x <- sapply(rack.dist, contains.word, lex.dist=min.dict.dist)

message("Estimate (and SE) of probability of no words based on ", 
        N, " trials:")
message(signif(1-mean(x)), " (", signif(sd(x) / sqrt(N)), ")")

Srikant ma rację: najlepszym rozwiązaniem jest badanie Monte Carlo. Są dwa powody. Po pierwsze, odpowiedź zależy w dużej mierze od struktury słownika. Dwie skrajności to (1), że słownik zawiera każde możliwe jedno literowe słowo. W takim przypadku szansa, że ​​nie utworzy słowa w losowaniu lub więcej liter, wynosi zero. (2) Słownik zawiera tylko słowa utworzone z jednej litery ( np. „A”, „aa”, „aaa” itp .). Szansa, że ​​nie będzie słowa w losowaniu liter, jest łatwa do ustalenia i oczywiście jest niezerowa. Każda określona odpowiedź w formie zamkniętej musiałaby obejmować całą strukturę słownika i byłaby naprawdę okropną i długą formułą.$1$$k$

Drugi powód jest taki, że MC rzeczywiście jest wykonalne: musisz po prostu zrobić to dobrze. Poprzedni akapit zawiera wskazówkę: nie generuj słów losowo i sprawdzaj je; zamiast tego najpierw przeanalizuj słownik i wykorzystaj jego strukturę.

Jeden ze sposobów reprezentuje słowa w słowniku jako drzewo. Drzewo jest zakorzenione w pustym symbolu i rozgałęzia się na każdej literze do końca; jego liście to (oczywiście) same słowa. Jednak możemy również wstawić wszystkie nieszablonowe permutacji każdego słowa w drzewo, zbyt (do z nich dla każdego wyrazu). Można to zrobić skutecznie, ponieważ nie trzeba przechowywać wszystkich tych permutacji; należy dodać tylko krawędzie drzewa. Liście pozostają takie same. W rzeczywistości można to jeszcze bardziej uprościć, nalegając, aby drzewo było śledzone w kolejności alfabetycznej .$k!-1$

Innymi słowy, aby ustalić, czy w słowniku znajduje się wielu znaków, najpierw ułóż elementy w posortowanej kolejności,$k$następnie poszukaj tego posortowanego „słowa” w drzewie zbudowanym z posortowanych przedstawicieli słów w oryginalnym słowniku. To będzie faktycznie mniejsze niż oryginalne drzewo, ponieważ łączy wszystkie zestawy słów, które są równoważne sortowaniu, takie jak {stop, post, pots, opts, spot}. W słowniku angielskim ta klasa słów i tak nigdy nie byłaby dostępna, ponieważ „tak” byłoby znalezione jako pierwsze. Zobaczmy to w akcji. Posortowany multiset to „opst”; „o” rozgałęzia się na wszystkie słowa zawierające tylko litery {o, p, ..., z}, „p” rozgałęzia się na wszystkie słowa zawierające tylko {o, p, ..., z} i co najwyżej jeden „o”, a na końcu „s” rozgałęzi się do liścia „so”! (Przyjąłem, że żaden z możliwych kandydatów „o”, „op”, „

Potrzebna jest modyfikacja do obsługi symboli wieloznacznych: Pozwolę programistom na zastanowienie się nad tym. Nie zwiększy rozmiaru słownika (powinien go zmniejszyć); nieco spowolni przejście drzewa, ale nie zmieni go w żaden fundamentalny sposób. W każdym słowniku zawierającym jedno litrowe słowo, takim jak angielski („a”, „i”), nie ma komplikacji: obecność znaku wieloznacznego oznacza, że ​​możesz utworzyć słowo! (To sugeruje, że oryginalne pytanie może nie być tak interesujące, jak się wydaje.)

Rezultat jest taki, że wyszukiwanie pojedynczego słownika wymaga (a) sortowania wielisetowego biuletynu i (b) przejścia nie więcej niż krawędzi drzewa. Czas działania to . Jeśli sprytnie wygenerujesz losowe multisety w posortowanej kolejności (mogę wymyślić kilka skutecznych sposobów, aby to zrobić), czas działania zmniejsza się do . Pomnóż to przez liczbę iteracji, aby uzyskać całkowity czas działania.k O ( k log ( k ) ) O ( k $k$$k$$O(k \log(k))$$O(k)$

Założę się, że możesz przeprowadzić to badanie z prawdziwym zestawem Scrabble i milionem iteracji w ciągu kilku sekund.

Podejście Monte Carlo

Szybkim i brudnym podejściem jest przeprowadzenie badania Monte Carlo. Narysuj płytek razy i dla każdego losowania płytek sprawdź, czy możesz utworzyć słowo. Oznacz, ile razy możesz utworzyć słowo przez . Pożądane prawdopodobieństwo wynosi:m k m $k$$m$$k$$m_w$

$$1 - \frac{m_w}{m}$$

Bezpośrednie podejście

Niech liczba słów w słowniku być podane przez . Niech będzie liczbą sposobów, w jakie możemy utworzyć słowo . Niech liczba liter potrzebnych przez słowo będzie oznaczona przez (tzn. Słowo potrzebuje liczby liter „a” itp). Oznaczają liczbę słów możemy tworzyć z wszystkich płytek przez .t y s p e ty m , m b , . . . , m z s th m a$S$$t_s$$s^\mbox{th}$$s^\mbox{th}$${m_a, m_b, ..., m_z}$$s^\mbox{th}$$m_a$$N$

$$N = \binom{n}{k}$$

i

$$t_s = \binom{n_a}{m_a} \binom{n_b}{m_b} ... \binom{n_z}{m_z}$$

(Uwzględnienie wpływu żetonów symboli wieloznacznych jest nieco trudniejsze. Na razie odłożę ten problem.)

Zatem pożądane prawdopodobieństwo wynosi:

$$1 - \frac{\sum_s{t_s}}{N}$$