1

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 "ice falling" 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:

  1. the total ways it can fill the area, and
  2. 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.

Kraigolas
  • 1,549
  • 6
  • 19
user2418426
  • 13
  • So you're drawing $k$ numbers, with replacement, from the numbers $1$ to $k$, and you want the probability that all of the numbers from $1$ to $n$ are drawn? – saulspatz Jul 15 '20 at 19:50
  • @saulspatz I'm drawing k with replacement, from numbers 1 to n, and the probability that all numbers are drawn yes. Alternatively, I know how many duplicates there must be, so if I know how to calculate number of ways with x duplicates it would work too. – user2418426 Jul 15 '20 at 19:54
  • Your example says $k=3,n=2$ and you seem to be drawing $k$ numbers from $1$ to $n$. I can't reconcile that with your last comment. – saulspatz Jul 15 '20 at 19:59
  • @saulspatz Uh I edited my comment the moment I posted it, not sure if you saw the old one instead. I am indeed drawing $k$ numbers from 1 to $n$ with replacement. – user2418426 Jul 15 '20 at 20:03

1 Answers1

-1

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

saulspatz
  • 53,131
  • Oh that is another way of looking at it! I never thought of using permutations. Interesting, I'll move forward in this direction and see what I come up with! Thanks! – user2418426 Jul 15 '20 at 20:17
  • So I've been working on understanding this, but something I don't understand is why use permutations instead of combinations? I thought that the ordering does not matter in this question? I ask because using permutations give me a 75% probability of success. This is clearly different from my initial example, and I'm trying to understand which one is the right one. Furthermore, I believe the equation above is supposed to be $n^k - n(n-1)^k $, since we have $n$ choices each draw for $k$ draws. – user2418426 Jul 16 '20 at 20:02
  • @user2418426 Yeah, I probably have $k$ and $n$ reversed. I've been confused about which was which. It doesn't matter if you use permutations or combinations in probability problems, and long as you do the same thing in the numerator and denominator. I'll take a look at your example. – saulspatz Jul 16 '20 at 20:06
  • @user2418426 You seem to have used the expression above to compute the probability in your example, even though my answer explicitly states that it is only a beginning. The formula is not complete as it stands. Follow the link to the article on the principle of inclusion and exclusion, and see how to complete the computation. – saulspatz Jul 16 '20 at 20:11
  • Using $k = 3, n =2$, I manually mapped out 8 permutations, and ${111,222}$ would not work, so the probability would be $6/8$. Edit: Just saw your reply, but no I did not use the equation above to find a number. I have a tree with all the permutations mapped out and manually saw through it all. The permutations are ${111, 211,121,221,112,212,122,222}$. – user2418426 Jul 16 '20 at 20:12
  • @user2418426 Since $n=2$, there is no way for two numbers to be omitted, so the formula gives the correct probability in this case. However, for $k>2$ you need to use inclusion-exclusion. – saulspatz Jul 16 '20 at 20:17
  • Well I'm trying to figure out why the probabilities are different when I'm using combination compared to using permutations. I know that its not supposed to, and I assumed the difference would be in the inclusion-exclusion, but that is not what the tree that I drew out is showing. My current understanding is to imagine $k^n$ as a venn-diagram circle, and inside that circle there is another circle which holds permutations with at least one of every number from 1 to $k$. Outside that would be what we are excluding in the equation. Thus $211,121,221,112,212,122$ would all be valid. – user2418426 Jul 16 '20 at 20:29