Unordered sampling with replacement

Question

I have difficulties with understanding of how do we count this.

1. Why can't we just divide number of ways of ordered sample with replacement $n^k$ by $k!$, i.e. to get rid of permutations since we cannot distinguish elements? What so different about that in comparison to the case without replacement?

2. I read the derivation based on counting "walls" between integers representing number of times particular ball was drawn. I do understand how to count number of combinations in this case but I do not understand how we get there, namely, why these numbers (number of combinations of placing "walls" and number of unordered samples with replacement) are the same?

Answer 1

Suppose I throw $k$ balls into $n$ distinguishable boxes. An example is throwing $k$ dice. If I throw a ball into box number $j$ we say the die lands with side $j$ up. Throwing $k=2$ dice, counting order of throws, can be done in $n^k=6^2$ ways. Now how many $unordered$ ways of throwing them are possible? Can I just divide $n^k/k!=18$? Let's see: For the unordered-without-replacement throw case $(i,j), i\ne j,$ then there are $6*5/2!=15$ ways. Plus the $6$ doubles gives $21,$ not $18$ ways. It is the $duplicates$ that prevent us from simply saying each unordered collection of $k$ items can be ordered in $k!$ ways. However, if we are sampling without replacement then we do not have duplicates and life is much simpler. So $6*5/2!$ is OK.

For the "walls" I assume you mean Feller's famous stars-and-bars. That is a simple way to come up with the number $21$ in the example above without having to count. With our dice example we have $n= 6$ boxes and $k=2$ balls. If we want to count the unordered ways directly we notice that throwing a $3$ and a $4$ (in either order) means box $3$ has $1$ ball, box $4$ has $1$ ball and other $4$ boxes are empty. Suppose I draw a diagram of these boxes numbered $1$ to $6$ from left to right: $$|empty|empty|*|*|empty|empty| $$ A star represents a ball and a bar is one side of a box. (Adjacent boxes share a common side.) Or if I roll a double $6$: $$|empty|empty|empty|empty|empty|**| $$

The key idea is there is a $1$ to $1$ correspondence between diagrams with $2$ stars (somewhere) and all results of throwing $2$ balls into $6$ boxes and we do not care in what order the balls got into the boxes. That's because if unordered, all that matters is the number of balls in each of the $n$ cells.

Now, for simplicity, get rid of the word $empty$ in the above diagrams: $$|||*|*||| $$ $$||||||**| $$ How many ways can we move the stars and bars around while keeping the first and last bar fixed (can't have a ball outside all the boxes.)?

By direct count there 15 of the first kind with balls in different boxes and $6$ of the second kind. There's our $21.$ Or, more simply, there are $5+2$ moveable places and $2$ stars are to be located in those places. This gives ${7 \choose 2}=21. $

Answer 2

As regards 1):

Consider n=2, k=2. There are 3 possibilities to count: 00, 01, 11. That is not $2^2/2! = 2$; the "why" of it being that not every permutation of an ordered sampling yields a different ordered sampling. The assumption that there are 2! possible permutations of 01 is correct; but there are not 2! permutations for 00, there is instead only 1. So $\frac{n^k}{k!}$ undercounts the number of outcomes.

As regards 2):

Not exactly sure what you're referring to as "walls between integers", but assuming you mean something like the usual "stars and bars" approach... Given a set $\{a_1, a_2, ..., a_n\}$ that we are sampling from with replacement, each possible unordered sampling with replacement can be thought of as "there are $m_1$ samples that are $a_1$, $m_2$ samples that are $a_2$, ..., $m_n$ samples that are $a_n$" where we know that each $m_i \geq 0$ and $\sum m_i = k$.

But that is the same thing we are looking at when we want to count the number of ways we can distribute $k$ objects into $n$ bins; $m_i$ is the number of samples we have allocated to bin $i$. So the function which counts the former should be identical to the function that counts the latter.