在拼字遊戲中不從一袋字母中抽出單詞的概率
假設你有一個包瓷磚，每個上面都有一個字母。有帶有字母“A”的瓷磚，與“B”，依此類推，並且’通配符’瓷磚（我們有）。假設您有一本包含有限數量單詞的字典。你選從袋子裡取出瓷磚，無需更換。你將如何計算（或估計）你可以從字典中形成零個單詞的概率選擇瓷磚？
對於不熟悉 Scrabble (TM) 的人來說，通配符可用於匹配任何字母。因此，單詞 [ BOOT ] 可以用拼貼“B”、“*”、“O”、“T”來“拼寫”。
為了對問題的規模有所了解，很小，像 7，大約是 100，字典包含大約 100,000 個大小的單詞或更小。
編輯： “形成一個詞”，我的意思是一個長度不大於. 因此，如果單詞 [ A ] 在字典中，那麼通過從袋子中抽出一個“A”，一個人就“形成了一個單詞”。如果可以假設字典中有長度為 1 的單詞，那麼通配符的問題就大大簡化了。因為如果有的話，任何一個通配符的抽取都會自動匹配一個長度為 1 的單詞，因此可以專注於沒有通配符的情況。因此，更難解決的問題形式在字典中沒有 1 個字母的單詞。
另外，我應該明確指出，從袋子中取出字母的順序無關緊要。不必按照單詞的“正確”順序繪製字母。
這是對@vqv 在此線程中發布的出色工作的（長！）評論。它旨在獲得明確的答案。他為簡化字典做了艱苦的工作。剩下的就是充分利用它。他的結果表明，蠻力解決方案是可行的。畢竟，包括通配符在內，最多有一個可以用 7 個字符組成的單詞，看起來只有不到 1/10000 的單詞——比如大約一百萬——將無法包含一些有效的單詞。
第一步是使用通配符“？”來擴充最小字典。其中 22 個字母出現在兩個字母的單詞中（除了 c、q、v、z）。將通配符連接到這 22 個字母並將它們添加到字典中：{a?, b?, d?, …, y?} 現在在其中。類似地，我們可以檢查最小的三字母單詞，從而產生一些額外的單詞出現在字典中。最後，我們添加“？？” 到字典。刪除重複的結果後，它包含 342 個最少的單詞。
一種優雅的處理方式——確實使用非常少量的編碼——是將這個問題視為一個代數問題。一個單詞，被認為是一組無序的字母，只是一個單項式。例如，“spats”是單項式. 因此，字典是單項式的集合。看起來像
（為了避免混淆，我寫了對於通配符）。
當且僅當該單詞將機架分開時，機架才包含有效單詞。
一個更抽象但非常強大的說法是字典生成了一個理想在多項式環中並且具有有效單詞的機架在商環中變為零，而沒有有效單詞的機架在商中保持非零。如果我們形成所有機架的總和並在這個商環中計算它，那麼沒有單詞的機架數等於商中不同單項式的數量。
此外，所有機架的總和是直截了當的表達。讓是字母表中所有字母的總和。 每個機架包含一個單項式。（作為一個額外的好處，它的係數計算了每個機架可以形成的方式的數量，如果我們願意，我們可以計算它的概率。）
作為一個簡單的例子（看看它是如何工作的），假設（a）我們不使用通配符並且（b）從“a”到“x”的所有字母都被認為是單詞。那麼唯一不能構成單詞的可能的格子必須完全由 y 和 z 組成。我們計算以產生的理想為模一步一步，因此：
我們可以從最終答案中讀出獲得非單詞機架的機會，：每個係數計算可以繪製相應機架的方式。例如，有 21 種（26^7 種可能）方法來繪製 2 個 y 和 5 個 z，因為等於 21。
從初步計算來看，很明顯這是正確的答案。關鍵在於，無論字典的內容如何，此過程都有效。
請注意，在每個階段減少理想的功率模數是如何減少計算的：這就是這種方法所揭示的捷徑。（示例結束。）
多項式代數係統實現這些計算。例如，這裡是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]（可以從@vqv 的 min.dict 以直接的方式構建字典；我在這裡放了一行，表明它足夠短，如果您願意，可以直接指定。）
輸出 - 需要十分鐘的計算 - 是 577958。（注意在此消息的早期版本中，我在準備字典時犯了一個小錯誤並獲得了 577940。我已經編輯了文本以反映我現在希望的內容正確的結果！）比我預期的少一點，但數量級相同。
為了計算獲得這樣一個架子的機會，我們需要考慮可以繪製架子的方式的數量。正如我們在示例中看到的，這等於它的係數. 抽出這樣的機架的機會是所有這些係數的總和，通過將所有字母設置為 1 很容易找到：
nonwords /. (# -> 1) & /@ (List @@ alphabet)答案等於 1066056120，有 10.1914% 的機會抽出一個無法組成有效單詞的架子（如果所有字母的可能性相同）。
當字母的概率不同時，只需將每個字母替換為它被繪製的機會：
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)輸出為1.079877553303%，即準確答案（儘管使用了近似模型，並進行了替換繪製）。回想起來，輸入數據（字母、字典和字母頻率）花了四行，而完成這項工作只用了三行：描述如何獲取下一個冪模塊，遞歸取 7 次方，並用概率代替字母。