3
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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)
$\endgroup$
2
$\begingroup$

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)$$

$\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.