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.
 A: 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.
A: 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}$$
A: 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)), ")")

A: 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.
