Calculating Combinations with Duplicates and Replacements Hi I'm stuck at doing my student project work, and this is my first time doing Combinatorics, so any help would be useful.
I'm attempting to calculate the probability that given $k$ blocks of ice falling and filling $n$ empty blocks on the ground, that all empty blocks are filled.
So I've hit a bit of a snag. The way I'm approaching this is to visualize the &quot;ice falling&quot; as a random bag that are filled with $1 - n$ numbers (denoting the spot the ice would fall in). It is possible for ice to fall on the same spot (meaning with replacement).
So what I've know is that I have to calculate the number of ways ice fall using combinations with replacement (combinations because as long as all holes are filled it does not matter). What I don't know is how to handle the duplication.
Furthermore, I'm also a little lost on how to calculate the numerator. I figure I need to find the excess number of duplicates, and then find the number of ways with only that amount of duplicates.
So given $k = 3$, and $n = 2$, I need to find:

the total ways it can fill the area, and
the number of ways it can fill the area given x duplicates.

I saw this post, and it seems pretty close to what I have to do, but I don't really understand why its doing $(n-2)$ and then $(n-4)$.
Example: Given 3 ice blocks and 2 holes on the ground, there are 4 ways to fill it up:
$$
\newcommand{\set}[1]{\{#1\}}
\set{1,1,1}\\\set{1,1,2}\\\set{2,2,1}\\\set{2,2,2}
$$
and two of these methods would work.
I don't want to post a complete answer, because I'm afraid I'd end up doing your project, but I'll get you started.  There are $n^k$ possible draws you can make.  Let's subtract the ones that don't include every number from $1$ to $n$.  There are $n$ choices for the omitted number, and $(n-1)^k$ ways to make all selections from the other other numbers, so that gives $$n^k-n(n-1)^k$$
The problem with this computation is that draws that miss two numbers are subtracted twice, once for each excluded number.  At this point, you need to look at the principle of inclusion and exclusion.
EDIT
In the case $k=3, n=2$ it is impossible for two numbers to be omitted, as then we wouldn't choose any numbers at all, so the inclusion-exclusion adjustment is not required.  The probability is$$
\frac{n^k-n(n-1)^k}{n^k}=\frac{2^3-2\cdot1^3}{2^3}=\frac{8-2}{8}=\frac68$$
I don't want to post a complete answer, because I'm afraid I'd end up doing your project, but I'll get you started.  There are $n^k$ possible draws you can make.  Let's subtract the ones that don't include every number from $1$ to $n$.  There are $n$ choices for the omitted number, and $(n-1)^k$ ways to make all selections from the other other numbers, so that gives $$n^k-n(n-1)^k$$
The problem with this computation is that draws that miss two numbers are subtracted twice, once for each excluded number.  At this point, you need to look at the principle of inclusion and exclusion.
EDIT
In the case $k=3, n=2$ it is impossible for two numbers to be omitted, as then we wouldn't choose any numbers at all, so the inclusion-exclusion adjustment is not required.  The probability is$$
\frac{n^k-n(n-1)^k}{n^k}=\frac{2^3-2\cdot1^3}{2^3}=\frac{8-2}{8}=\frac68$$