# Number of possible Scrabble draws

I would like to compute the number of Scrabble draws, when starting a game. Translated to mathematics, this asks for the number of sub-multisets of a multiset.

Lets say we have a multiset $$M$$ over a set $$N=\{1,...,n\}$$. This means there are numbers $$m_1,..m_n$$, which indicate the multiplicity of the numbers $$1$$ to $$n$$. For $$k \leq m := m_1+...+m_n$$ we now want to draw a $$k-$$multiset from $$M$$, in other words numbers $$k_1,...,k_n$$ with the property $$k_1+...+k_n=k$$ and $$0 \leq k_i \leq m_i$$.

My Ansatz was drawing a number of $$1$$'s, this is $$k_1$$. In order to do so, we have $$\min(m_1, 1+k)$$ many possibilities.

Then we draw $$k_2$$, the number of $$2$$'s. For this, we have $$\min(m_2, 1+k - k_1)$$ many possibilities.

...

Finally, for $$k_n$$, there are $$\min(m_n, 1+k- (k_1 + ... +k_{n-1}))$$ many possibilities.

The problem is the obviously the self referentiality, i.e the number of possibilities for $$k_i$$ depending on $$k_j$$ for $$j < i$$. I'm sure there is a very clean way to do it via binomial coefficients or so but I'm not sure how to do it that way. Any help is appreciated. :-)

EDIT: bump

I don't know any tricks to make this easier.

I got the number of tiles of each letter and the blanks (2) from here and then counted the number of ways with the R program below. For example, you can draw 0 "A"s and 7 tiles from the remainder, or 1 "A" and 6 tiles from the remainder, or 2 "A"s and 5 tiles from the remainder,... The total can be counted recursively. I got a total of 3,199,724 different ways.
This is related.

x=sort(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))

f=function(x,k) {
if (sum(x)<k) cnt=0 else if (sum(x)==k | (length(x)==1)) cnt=1 else {
cnt=0
for (i in 0:min(x[1],k)) cnt=cnt+f(x[-1],k-i)
}
return(cnt)
}
f(x,7)


For a general case, without specific values for $$m_1, \ldots m_n$$, see here and/or here, whereas, if we have $$m_1=m_2=\ldots=m_n$$ there are simpler formulas here or here ($$k_i=0$$ not allowed there).

If we have specific numeric values for $$m_1, \ldots m_n$$, then we use generating functions more easily to get the number of $$k$$-multisets as the coefficient of $$x^k$$ of the generating function:

$$f(x) = \prod_{i=1}^n (1+x+\ldots+x^{m_i}) = \prod_{i=1}^n \frac{x^{m_i+1}-1}{x-1}$$ which in our case is (using Wikipedia data, the same as @John L's answer):

$$f(x)=\frac{(x^2-1)^5(x^3-1)^{10}(x^4-1)(x^5-1)^4(x^7-1)^3(x^9-1)(x^{10}-1)^2(x^{13}-1)}{(x-1)^{27}}$$

And using Wolfram Alpha get some coefficients, e.g.:

$$[x^7]f(x)=3199724$$

like in @John L answer.

Note also that the total number of multisets of any size is:

$$\prod_{i=1}^n (1+m_i)$$