1
$\begingroup$

Say I have a subset of the standard scrabble tiles $B$ that contains no blank tiles s.t. $|B|=n$

Also consider I have a target set of letters $L$ s.t. $|L|=k$. These are a set of letters not tiles, so there may be multiple subsets of tiles from $B$ that correspond to $L$.

Say I draw $m$ tiles from $B$ (call it $D\subset B$). What is the probability that $D$ contains tiles corresponding to every letter in $L$ at least once?

Clearly the denominator for this probability will be ${{n}\choose{m}}$, that is the number of possible combinations of tiles $D$ that can be drawn without replacement from $B$.

What I'm missing is the numerator. That is, how many of these possible $D$s contain tiles corresponding to $L$.

$\endgroup$
  • $\begingroup$ Your model is a bit confusing. If $L \subset B$ and $B$ are tiles, then $L$ must be tiles... $\endgroup$ – copper.hat Feb 28 '13 at 17:41
  • $\begingroup$ Good point, I'll try to clarify. $\endgroup$ – CodeFusionMobile Feb 28 '13 at 17:48
  • $\begingroup$ Since you ask what what the probability $D$ contains tiles corresponding to to every letter in $L$ at least once, I assume $B$ isn't a standard mathematical set, rather its a multiset. So what's the distribution of $B$, or are we supposed to generalize to all possible distributions of $B$? $\endgroup$ – DPenner1 Feb 28 '13 at 18:49
  • $\begingroup$ I suppose that would be correct. I'm not sure of the exact terminology, but the question is similar to asking the odds of drawing a Spade from a Deck of cards. A deck is a set of 52 unique cards, but multiple cards can have a given property. $\endgroup$ – CodeFusionMobile Feb 28 '13 at 19:04
1
$\begingroup$

The probability will depend on how many tiles there are in $B$ with the particular letters you want. If, for each $i=1$, $\dots$, $k$, $B$ contains exactly $v_i$ tiles corresponding to the $i$th letter in $L$, then the number of possible draws which exclude letters #$j_1$, $\dots$, #$j_q$ is $$\binom{n-v_{j_1}-\cdots-v_{j_q}}{m}.$$ So, by the inclusion-exclusion principle, the probability of drawing each of your $k$ selected letters at least once is $$ 1-\binom{n}{m}^{-1} \left(\sum_{1\le q\le k} (-1)^{q-1} \sum_{1\le j_1<\cdots<j_q\le k}\binom{n-v_{j_1}-\cdots-v_{j_q}}{m}\right). $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.