Probability of not drawing a word from a bag of letters in Scrabble

Suppose you had a bag with $n$ tiles, each with a letter on it. There are $n_A$ tiles with letter 'A', $n_B$ with 'B', and so on, and $n_*$ 'wildcard' tiles (we have $n = n_A + n_B + \ldots + n_Z + n_*$). Suppose you had a dictionary with a finite number of words. You pick $k$ tiles from the bag without replacement. How would you compute (or estimate) the probability that you can form zero words from the dictionary given the $k$ tiles selected?

For those not familiar with Scrabble (TM), the wildcard character can be used to match any letter. Thus the word [BOOT] could be 'spelled' with the tiles 'B', '*', 'O', 'T'.

To give some idea of the scale of the problem, $k$ is smallish, like 7, $n$ is around 100, and the dictionary contains about 100,000 words of size $k$ or smaller.

edit: By 'form a word', I mean a word of length no greater than $k$. Thus, if the word [A] is in the dictionary, then by drawing even a single 'A' from the bag, one has 'formed a word'. The problem of wildcards is radically simplified if one can assume there are words of length 1 in the dictionary. For if there are, any draw of a wildcard automatically can match a length 1 word, and thus one can concentrate on the case where there are no wildcards. Thus the more slippery form of the problem has no 1-letter words in the dictionary.

Also, I should explicitly state that the order in which the letters are drawn from the bag is immaterial. One does not have to draw the letters in the 'correct' order of the word.

-
Should it not be 'pick k tiles without replacement'? Very interesting question. –  user28 Oct 20 '10 at 0:39
oops. indeed it should. –  shabbychef Oct 20 '10 at 1:58
As far as I remember Scrabble does not allow one letter words, so at least that part of the problem is solved ;) –  nico Oct 21 '10 at 7:07
@nico good point, but I think this is only for mid-game. 1 letter words either don't require one to play a letter, or would allow one to place a single letter anywhere on the board, both clearly unacceptable. However, I was thinking of the opening move. In fact, the question can be compactly stated, for those familiar with Scrabble, as "what is the probability that the first player will have to pass?" –  shabbychef Oct 21 '10 at 16:43
@nico Thank you for that clarification. Theoretically a similar issue pertains in dictionaries containing all possible two-letter combinations as words: when that's the case, any hand of 2 or more letters automatically contains a word. @shabbychef's comment about mid-game shows how irrelevant the original question is to most of Scrabble, because in mid-game you have available an array of word parts (prefixes, suffixes, and even middle sections) in addition to the 7 letters in your hand. This greatly increases the chances of being able to make a word. –  whuber Oct 22 '10 at 16:29

4 Answers

This is a (long!) comment on the nice work @vqv has posted in this thread. It aims to obtain a definitive answer. He has done the hard work of simplifying the dictionary. All that remains is to exploit it to the fullest. His results suggest that a brute-force solution is feasible. After all, including a wildcard, there are at most $27^7 = 10,460,353,203$ words one can make with 7 characters, and it looks like less than 1/10000 of them--say, around a million--will fail to include some valid word.

The first step is to augment the minimal dictionary with a wildcard character, "?". 22 of the letters appear in two-letter words (all but c, q, v, z). Adjoin a wildcard to those 22 letters and add these to the dictionary: {a?, b?, d?, ..., y?} are now in. Similarly we can inspect the minimal three-letter words, causing some additional words to appear in the dictionary. Finally, we add "??" to the dictionary. After removing repetitions that result, it contains 342 minimal words.

An elegant way to proceed--one that uses a very small amount of encoding indeed--is to view this problem as an algebraic one. A word, considered as an unordered set of letters, is just a monomial. For example, "spats" is the monomial $a p s^2 t$. The dictionary therefore is a collection of monomials. It looks like

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

(where, to avoid confusion, I have written $\psi$ for the wildcard character).

A rack contains a valid word if and only if that word divides the rack.

A more abstract, but extremely powerful, way to say this is that the dictionary generates an ideal $I$ in the polynomial ring $R = \mathbb{Z}[a, b, \ldots, z, \psi]$ and that the racks with valid words become zero in the quotient ring $R/I$, whereas racks without valid words remain nonzero in the quotient. If we form the sum of all racks in $R$ and compute it in this quotient ring, then the number of racks without words equals the number of distinct monomials in the quotient.

Furthermore, the sum of all racks in $R$ is straightforward to express. Let $\alpha = a + b + \cdots + z + \psi$ be the sum of all letters in the alphabet. $\alpha^7$ contains one monomial for each rack. (As an added bonus, its coefficients count the number of ways each rack can be formed, allowing us to compute its probability if we like.)

As a simple example (to see how this works), suppose (a) we don't use wildcards and (b) all letters from "a" through "x" are considered words. Then the only possible racks from which words cannot be formed must consist entirely of y's and z's. We compute $\alpha=(a+b+c+\cdots+x+y+z)^7$ modulo the ideal generated by $\{a,b,c, \ldots, x\}$ one step at a time, thus:

\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{.} }

We can read off the chance of getting a non-word rack from the final answer, $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$: each coefficient counts the ways in which the corresponding rack can be drawn. For example, there are 21 (out of 26^7 possible) ways to draw 2 y's and 5 z's because the coefficient of $y^2 z^5$ equals 21.

From elementary calculations, it is obvious this is the correct answer. The whole point is that this procedure works regardless of the contents of the dictionary.

Notice how reducing the power modulo the ideal at each stage reduces the computation: that's the shortcut revealed by this approach. (End of example.)

Polynomial algebra systems implement these calculations. For instance, here is Mathematica code:

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]


(The dictionary can be constructed in a straightforward manner from @vqv's min.dict; I put a line here showing that it is short enough to be specified directly if you like.)

The output--which takes ten minutes of computation--is 577958. (NB In an earlier version of this message I had made a tiny mistake in preparing the dictionary and obtained 577940. I have edited the text to reflect what I hope are now the correct results!) A little less than the million or so I expected, but of the same order of magnitude.

To compute the chance of obtaining such a rack, we need to account for the number of ways in which the rack can be drawn. As we saw in the example, this equals its coefficient in $\alpha^7$. The chance of drawing some such rack is the sum of all these coefficients, easily found by setting all the letters equal to 1:

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


The answer equals 1066056120, giving a chance of 10.1914% of drawing a rack from which no valid word can be formed (if all letters are equally likely).

When the probabilities of the letters vary, just replace each letter with its chance of being drawn:

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)


The output is 1.079877553303%, the exact answer (albeit using an approximate model, drawing with replacement). Looking back, it took four lines to enter the data (alphabet, dictionary, and alphabet frequencies) and only three lines to do the work: describe how to take the next power of $\alpha$ modulo $I$, take the 7th power recursively, and substitute the probabilities for the letters.

-
+1 Adjoining the lexicon and then re-minimizing it is a clever idea. The algebra is beyond me, but it feels like you are calculating a multinomial probability, rather than hypergeometric. So the probability is for sampling with replacement. I think that explains why your answer of 1.08% is so much larger than my estimate of 0.4%. Is there a way to modify your approach to handle sampling without replacement? –  vqv Jan 10 '11 at 18:08
@vqv Yes. Now that we have a list of the half million or so racks with no words, it's straightforward (by changing the last two lines of code) to compute the chance of each rack (without replacement) and obtain the hypergeometric result. The exact answer equals 349870667877/80678106432000 = 0.43366%. With N=100K trials your SE is 0.021%, so your answer should have come between 0.38% and 0.49% (two-sided 99% CI). I'm so glad our answers agree! –  whuber Jan 10 '11 at 19:48
@whuber Could you run the calculation using the Words With Friends (WWF) tile distribution? My estimate of 0.4% is based on the WWF lexicon and WWF tile distribution. I think you are using the Scrabble tile distribution with the WWF lexicon. –  vqv Jan 10 '11 at 20:34
Oops. The exact answer actually is 349870675899 (I was 8022 off due to an error in my dictionary.) This makes no practical difference, fortunately. –  whuber Jan 10 '11 at 20:43
@vqv I'm not familiar with the various tile distributions. I copied mine directly from your code (and I used your dictionary) :-). If you mean the distribution at osxreality.com/2010/01/01/… , then I obtain 1.15444% (with replacement), 0.43366% (without replacement). The second number actually does differ from the Scrabble frequencies at the 8th significant figure. –  whuber Jan 10 '11 at 20:51

It is very hard to draw a rack that does not contain any valid word in Scrabble and its variants. Below is an R program I wrote to estimate the probability that the initial 7-tile rack does not contain a valid word. It uses a monte carlo approach and the Words With Friends lexicon (I couldn’t find the official Scrabble lexicon in an easy format). Each trial consists of drawing a 7-tile rack, and then checking if the rack contains a valid word.

Minimal words

You don’t have to scan the entire lexicon to check if the rack contains a valid word. You just need to scan a minimal lexicon consisting of minimal words. A word is minimal if it contains no other word as a subset. For example 'em’ is a minimal word; 'empty’ is not. The point of this is that if a rack contains word x then it must also contain any subset of x. In other words: a rack contains no words iff it contains no minimal words. Luckily, most words in the lexicon are not minimal, so they can be eliminated. You can also merge permutation equivalent words. I was able to reduce the Words With Friends lexicon from 172,820 to 201 minimal words.

Wildcards can be easily handled by treating racks and words as distributions over the letters. We check if a rack contains a word by subtracting one distribution from the other. This gives us the number of each letter missing from the rack. If the sum of those number is $\leq$ the number of wildcards, then the word is in the rack.

The only problem with the monte carlo approach is that the event that we are interested in is very rare. So it should take many, many trials to get an estimate with a small enough standard error. I ran my program (pasted at the bottom) with $N=100,000$ trials and got an estimated probability of 0.004 that the initial rack does not contain a valid word. The estimated standard error of that estimate is 0.0002. It took just a couple minutes to run on my Mac Pro, including downloading the lexicon.

I’d be interested in seeing if someone can come up with an efficient exact algorithm. A naive approach based on inclusion-exclusion seems like it could involve a combinatorial explosion.

Inclusion-exclusion

I think this is a bad solution, but here is an incomplete sketch anyway. In principle you can write a program to do the calculation, but the specification would be tortuous.

The probability we wish to calculate is $$P(k\text{-tile rack does not contain a word}) = 1 - P(k\text{-tile rack contains a word}) .$$ The event inside the probability on the right side is a union of events: $$P(k\text{-tile rack contains a word}) = P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right),$$ where $M$ is a minimal lexicon. We can expand it using the inclusion-exclusion formula. It involves considering all possible intersections of the events above. Let $\mathcal{P}(M)$ denote the power set of $M$, i.e. the set of all possible subsets of $M$. Then \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}

The last thing to specify is how to calculate the probability on the last line above. It involves a multivariate hypergeometric.
$$\cap_{x \in S} \{ k\text{-tile rack contains }x \}$$ is the event that the rack contains every word in $S$. This is a pain to deal with because of wildcards. We'll have to consider, by conditioning, each of the following cases: the rack contains no wildcards, the rack contains 1 wildcard, the rack contains 2 wildcards, ...

Then \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}

I'm going to stop here, because the expansions are tortuous to write out and not at all enlightening. It's easier to write a computer program to do it. But by now you should see that the inclusion-exclusion approach is intractable. It involves $2^{|M|}$ terms, each of which is also very complicated. For the lexicon I considered above $2^{|M|} \approx 3.2 \times 10^{60}$.

Scanning all possible racks

I think this is computationally easier, because there are fewer possible racks than possible subsets of minimal words. We successively reduce the set of possible $k$-tile racks until we get the set of racks which contain no words. For Scrabble (or Words With Friends) the number of possible 7-tile racks is in the tens of billions. Counting the number of those that do not contain a possible word should be doable with a few dozen lines of R code. But I think you should be able to do better than just enumerating all possible racks. For instance, 'aa' is a minimal word. That immediately eliminates all racks containing more than one 'a’. You can repeat with other words. Memory shouldn’t be an issue for modern computers. A 7-tile Scrabble rack requires fewer than 7 bytes of storage. At worst we would use a few gigabytes to store all possible racks, but I don’t think that’s a good idea either. Someone may want to think more about this.

Monte Carlo R program

#
#  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)), ")")

-
Wow... very nice follow-up. –  Matt Parker Jan 7 '11 at 23:52
I am somewhat surprised it reduced to 201 words. Although for first word played, our house rules accept 'I' and 'A' as words, which would probably further reduce the number of minimal words. I was hoping to see someone bust out the inclusion-exclusion analysis, which should be pretty hairy... –  shabbychef Jan 8 '11 at 6:05
@shabbychef There are no 1-letter words in the lexicon. Most minimal words are 2- and 3-letter words. Here is the full distribution of minimal word lengths: 2: 73, 3:86, 4:31, 5:9, 6:2. The 6-letter words are: GLYCYL and SYZYGY. –  vqv Jan 8 '11 at 17:33
@shabbychef I updated my answer to include a sketch of an exact inclusion-exclusion approach. It is worse than hairy. –  vqv Jan 8 '11 at 20:18
great work! I love that this question, which could be posed as one sentence (to those with sufficient background), has brought out monte carlo, inclusion-exclusion, DAGs, searching trees, polynomial algebra, and that your simulations are confirmed by the theoretical of @whuber. cheers! –  shabbychef Jan 13 '11 at 19:49

Srikant is right: a Monte Carlo study is the way to go. There are two reasons. First, the answer depends strongly on the structure of the dictionary. Two extremes are (1) the dictionary contains every possible single-letter word. In this case, the chance of not making a word in a draw of $1$ or more letters is zero. (2) The dictionary contains only words formed out of a single letter (e.g., "a", "aa", "aaa", etc.). The chance of not making a word in a draw of $k$ letters is easily determined and obviously is nonzero. Any definite closed-form answer would have to incorporate the entire dictionary structure and would be a truly awful and long formula.

The second reason is that MC indeed is feasible: you just have to do it right. The preceding paragraph provides a clue: don't just generate words at random and look them up; instead, analyze the dictionary first and exploit its structure.

One way represents the words in the dictionary as a tree. The tree is rooted at the empty symbol and branches on each letter all the way down; its leaves are (of course) the words themselves. However, we can also insert all nontrivial permutations of every word into the tree, too (up to $k!-1$ of them for each word). This can be done efficiently because one does not have to store all those permutations; only the edges in the tree need to be added. The leaves remain the same. In fact, this can be simplified further by insisting that the tree be followed in alphabetical order.

In other words, to determine whether a multiset of $k$ characters is in the dictionary, first arrange the elements into sorted order, then look for this sorted "word" in a tree constructed from the sorted representatives of the words in the original dictionary. This will actually be smaller than the original tree because it merges all sets of words that are sort-equivalent, such as {stop, post, pots, opts, spot}. In fact, in an English dictionary this class of words would never be reached anyway because "so" would be found first. Let's see this in action. The sorted multiset is "opst"; the "o" would branch to all words containing only the letters {o, p, ..., z}, the "p" would branch to all words containing only {o, p, ..., z} and at most one "o", and finally the "s" would branch to the leaf "so"! (I have assumed that none of the plausible candidates "o", "op", "po", "ops", or "pos" are in the dictionary.)

A modification is needed to handle wildcards: I'll let the programmer types among you think about that. It won't increase the dictionary size (it should decrease it, in fact); it will slightly slow down the tree traversal, but without changing it in any fundamental way. In any dictionary that contains a single-letter word, like English ("a", "i"), there is no complication: the presence of a wildcard means you can form a word! (This hints that the original question might not be as interesting as it sounds.)

The upshot is that a single dictionary lookup requires (a) sorting a $k$-letter multiset and (b) traversing no more than $k$ edges of a tree. The running time is $O(k \log(k))$. If you cleverly generate random multisets in sorted order (I can think of several efficient ways to do this), the running time reduces to $O(k)$. Multiply this by the number of iterations to get the total running time.

I bet you could conduct this study with a real Scrabble set and a million iterations in a matter of seconds.

-
@whuber The tree is a neat idea (upvote for that idea) but would it not require lot of memory? I guess it depends on how diverse the dictionary is but I am guessing a reasonably diverse dictionary would require many trees For example, the 'b' tree would start with the letter 'b' instead of 'a' for all those words which do not have 'a' in them. Similarly, the 'c' tree would start with the letter 'c' for those words which do not have 'a' and 'b' but have 'c'. My proposed direct approach seems simpler as it requires a one-time traversal of all the words in the dictionary, no? –  user28 Oct 20 '10 at 15:49
@Srikant: The tree would likely require far less RAM than caching the entire dictionary to begin with. Are you really concerned about a few megabytes of RAM, anyway? BTW, there's only one tree, not many: they are all rooted at the empty word. Your approach, as I have understood it, requires multiple searches of the dictionary (up to 7! of them) on every iteration, making it impracticable as @shabbychef fears. It would help if you could elaborate on the algorithm you have in mind where you write "see if you can form a word": that hides a lot of important details! –  whuber Oct 20 '10 at 16:09
@whuber: I realized the fact that there is only one tree after I posted my comment. Reg my approach- I agree that my monte carlo proposal is fuzzy and your answer fleshes out how one can actually implement monte carlo in this setting. I actually meant that the direct approach (see my answer) may actually be simpler as that approach requires a one-time operation on the dictionary unlike a monte carlo which requires several thousands of iterations on the tree. Just wondering on the relative merits of the approaches. –  user28 Oct 20 '10 at 16:15
@Srikant I refrained from commenting on your direct approach because it I suspect it gets the wrong answers. It does not appear to account for the dictionary structure: that is, the subset relationships among words. For instance, would your formula get the correct answer of zero for all dictionaries that contain all the possible one-letter words? –  whuber Oct 20 '10 at 16:23
@whuber hmmm good point. Perhaps, I am answering the wrong question! –  user28 Oct 20 '10 at 16:30

Monte Carlo Approach

The quick and dirty approach is to do a monte carlo study. Draw $k$ tiles $m$ times and for each draw of $k$ tiles see if you can form a word. Denote the number of times you could form a word by $m_w$. The desired probability would be:

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

Direct Approach

Let the number of words in the dictionary be given by $S$. Let $t_s$ be the number of ways in which we can form the $s^\mbox{th}$ word. Let the number of letters needed by the $s^\mbox{th}$ word be denoted by ${m_a, m_b, ..., m_z}$ (i.e., the $s^\mbox{th}$ word needs $m_a$ number of 'a' letters etc). Denote the number of words we can form with all tiles by $N$.

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

and

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

(Including the impact of wildcard tiles is a bit trickier. I will defer that issue for now.)

Thus, the desired probability is:

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

-
The quick and dirty approach may not be so quick! The dictionary may contain 100,000 words, and the search for a match of the given tiles could be a coding disaster. –  shabbychef Oct 20 '10 at 4:26
@shabbychef This is something well done to suit spell checkers. See for instance n3labs.com/pdf/lexicon-squeeze.pdf –  mbq Oct 20 '10 at 7:06
@shabbychef Reg monte-carlo- if the dictionary is sorted a match should be fairly quick no? In any case, the direct approach that I outlined earlier was flawed. I fixed it. The problem in my earlier solution was that the same word can be formed multiple ways (e.g., 'bat', 'b*t' etc). –  user28 Oct 20 '10 at 9:14
@shabbychef On further reflection, I agree with you that the monte carlo approach will not work. One issue is that you need to figure out which words you can actually form with the k tiles and the second one is that you can form multiple words with the k tiles. Calculating these combinations from k tiles is probably not that easy. –  user28 Oct 20 '10 at 9:49
@Srikant Thanks. Your formula seems to assume you have to use all k letters to form the word, but I don't think that's what the OP is asking. (That's not how Scrabble is played, anyway.) With that implicit assumption, you're on the right track but you need to modify the algorithm: you mustn't repeat the calculation for words in the dictionary that are permutations of each other. For example, you mustn't subtract both t_{stop} and t_{post} in your formula. (This is an easy modification to implement.) –  whuber Oct 20 '10 at 16:35