Some Lottery Problems

In [1], the following lottery problem is discussed: Randomly choose $r$ (e.g. $r=6$) numbers from 1 to $n$ (e.g. $n = 44$), figure out the cardinality of the sample space (i.e. the total number of all possible outcomes). “The devil is in the details!” Depending on order and replacement, there are four cases:

	Without Replacement	With Replacement
Ordered	$ { n \choose r } r! $	$ n^r $
Unordered	$ { n \choose r } $	$ { n+r-1 \choose r} $

Here I am most interested in the unordered-with replacement case. The key idea is that: to choose $r$ numbers (duplication is allowed) is to put $r$ “markers” into boxes numbered from 1 to $n$. Let me further explain with an example. Suppose $ n=4 $ and $r=3$. So, $ (3, 0, 0, 0) $—three markers in box 1, none markers in the other boxes—gives the ticket number “111”; $ (2, 1, 0, 0) $—two markers in box 1, one marker in box 2 and none markers in the other boxes—gives the ticket number “112”; $ (0, 1, 1, 1) $—0 marker in box 1 and each of the other boxes has one marker—gives the ticket number “234”. With the above key idea in mind, using the generating function approach, it is easy to know the solution is the coefficient of $x^r$ in

\begin{align} g(x) &= (1+x+\ldots+x^r)^n\\ &= \left( \frac{1-x^{r+1}}{1-x} \right) ^n\\ &= (1-x^{r+1})^n (1-x)^{-n}, \end{align}

which is equal to

$$ {n+r-1 \choose r}. $$

Last, for teaching purpose, we may want to see the sample space in the case of given small $n$ and $r$. Here is the R code:

n <- 4
r <- 3

my_list <- vector(mode = "list")
s <- 0

for(i in 0:r)
  for(j in 0:r)
    for(k in 0:r)
      for(m in 0:r) {
        if(i + j + k + m == r) {
          s <-  s + 1
          my_list[[s]] <- paste0(rep(1:n, times = c(i, j, k, m)), collapse = "")
        }
      }
sort(do.call(rbind, my_list))

##  [1] "111" "112" "113" "114" "122" "123" "124" "133" "134" "144" "222" "223"
## [13] "224" "233" "234" "244" "333" "334" "344" "444"

References

[1] Casella, G. and Berger, R. (2002). Statistical Inference.