1
$\begingroup$

I have some probability notions but now I face a problem merging combinatorial and probability.

Suppose one has $k$ objects and $n$ containers with infinite capacity, $k$ and $n$ being natural integers. $k$ can be smaller, equal or greater than $n$.
The question is:

What is the probability $P(x)$ of distributing the $k$ objects within exactly $x$ containers, $x\geq0$.

Each of the $k$ objects has the same probability of falling in any of the $n$ containers, i.e., $p_0 = \frac{1}{n}$.
I do not interest myself to the number of objects in one specific container, just the distribution of the number of objects in the containers. I understand that $\sum_{x=0}^{n} P(x) = 1$ and that $P(1)$ or $P(n)$ is ridiculously small as $k$ and $n$ increase.
I also understand how to calculate the number of different combinations using the $C_k^n = \frac{(n+k-1)!}{k!(n-1)!}$.

By the way I am not convinced that the distribution $P(x)$ could be approached with a normal distribution as $P(x)$ will always be bounded by $x = \frac{k}{n}$ for $k>>n$.

I have been looking for a while in the different posts and two ideas came out:

In all the cases, I haven't found (understood) the answer to my problem in the sources I present.

May one of you help me to solve it? Many thanks in advance for the time taken to read me and for the help you could provide.

Protra

$\endgroup$
3
  • $\begingroup$ By the way, I am pretty bad at English. If anybody desires to edit the post to gain in clearness, you are welcome! In addition, I try to edit my post to add Hello at the beginning, but it doesn't want to be edited ... Protra $\endgroup$
    – Protra
    Aug 15 '16 at 12:16
  • $\begingroup$ First, you must understand and clarify all the limitations of the problem. Do you mean what is $P(x)$ if the objects distributed uniformly (i.e every object has the same probability of being in every container)? Are the objects unique or the number of objects in each container is what matters? $\endgroup$
    – Snufsan
    Aug 15 '16 at 13:41
  • $\begingroup$ Hi Snufsan! I edited the post in accordance with your remark. The objects have the same probability of being in ever container. Then, I don't interest myself to the number of object in the various containers, just to the distribution. If we take the example of 2 objects and 3 (let's label containers $1,2$ and $3$) , I can distribute the objects like the following: $11$, $12$, $13$, $21$, $22$, $23$, $31$, $32$, $33$ and I am interested in the probability of occupying one container (cases $11$, $22$ and $33$) and occupying 2 containers (the rest of the cases), and 3 containers (none). Thanks! $\endgroup$
    – Protra
    Aug 15 '16 at 14:25
1
$\begingroup$

To avoid trivial cases we assume the number $k$ of objects we want to place in $x$ out of $n$ containers is greater than or equal to $x$, otherwise the probability let's denote it with $P_{n,k}(x)$ is zero.

According to OPs description we assume the $k$ objects are indistinguishable, while the $n$ containers are distinguishable.

In order to find $P_{n,k}(x)$ giving the probability that precisely $x$ containers are not empty, we calculate the number of favorable outcomes divided by the number of possible outcomes.

We start with the easy one. The number of all possible outcomes is given by the number of multisets

$$\left(\binom{n}{k}\right)=\binom{n+k-1}{k}$$

which is the number of placing $k$ objects in $n$ containers.

And now the favorable outcomes: We want to place $k$ objects in exactly $x$ containers. There are

$$\binom{n}{x}$$

possibilities to choose $x$ containers out of the total of $n$ containers.

Each of the $x$ containers has to contain at least one object. So we put into each of these containers one out of the $k$ objects, leaving $k-x$ objects. These $k-x$ objects can be placed among the $x$ containers, giving $$\left(\binom{x}{k-x}\right)=\binom{k-1}{k-x}$$ possibilities.

$$ $$

We conclude: The probability $P_{n,k}(x)$ of placing $k\geq 1$ objects in exactly $x$ out of $n$ containers, with $1\leq x \leq n$ is \begin{align*} P_{n,k}(x)=\frac{\binom{n}{x}\binom{k-1}{k-x}}{\binom{n+k-1}{k}}\qquad\qquad k\geq x\tag{1} \end{align*} and zero otherwise.

Since the number $x$ of containers may vary from $1$ to $n$, we obtain from (1) the formula \begin{align*} \sum_{x=1}^{n}\binom{n}{x}\binom{k-1}{k-x}=\binom{n+k-1}{k}\tag{2} \end{align*}


[Add-on]: Let's prove formula (2) with algebraic methods to complement and verify the combinatorial proof above.

It is convenient to use the coefficient of operator $[u^x]$ to denote the coefficient of $u^x$ in a series. This way we can write e.g. \begin{align*} [u^x](1+u)^n=\binom{n}{x} \end{align*}

We obtain \begin{align*} \sum_{x=1}^n\binom{n}{x}\binom{k-1}{k-x} &=\sum_{x=0}^\infty[u^x](1+u)^n[z^{k-x}](1+z)^{k-1}\tag{1}\\ &=[z^k](1+z)^{k-1}\sum_{x=0}^\infty z^x[u^x](1+u)^n\tag{2}\\ &=[z^k](1+z)^{k-1}(1+z)^n\tag{3}\\ &=[z^k](1+z)^{n+k-1}\tag{4}\\ &=\binom{n+k-1}{k} \end{align*} and the claim follows.

Comment:

  • In (1) we apply the coefficient of operator twice. We extend the range of $x$ from $0$ to $\infty$ without changing anything since we add only zeros.

  • In (2) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [z^{k-x}]A(z)=[z^k]z^xA(z) \end{align*}

  • In (3) we use the substitution rule of the coeffcient of operator \begin{align*} A(z)=\sum_{x=0}^\infty a_x z^x=\sum_{x=0}^\infty z^x [u^x]A(u) \end{align*} and substitute $u$ in $A(u)=(1+u)^n$ with $z$.

  • In (4) we simplify the expression to $(1+z)^{n+k-1}$ and select the coefficient of $z^k$ in the last step.

$\endgroup$
8
  • $\begingroup$ Hi Markus, I understand the answer, and it is quite well explained. But I am facing a problem. In the case that $k>n$, thus $x>n$ but $x<=k$, the solution does not work, no? I tough that in this case one should replace $k$ by $k' = \frac{k}{n}$ and $x' = \frac{x}{n}$, normalized variables, and then use $k'$ and $x'$ with your solution (using the Gamma function instead of the factorial)? The fact is that, for example $n=3$ and $k=12$, there is no reason to not have in average 4 objects per container ($x=4$ here). May I misunderstood something, please let me know. I greatly appreciate your help! $\endgroup$
    – Protra
    Aug 18 '16 at 7:03
  • $\begingroup$ @Protra: Hi Protra! The range $x\leq k \leq n$ was unnecessarily restrictive. I've corrected it accordingly. Thanks! Since $x$ is the number of containers we can take from $n$ available containers, we always have $1\leq x\leq n$. Feel free to ask if there are some more questions. $\endgroup$
    – epi163sqrt
    Aug 18 '16 at 8:14
  • $\begingroup$ Yes, you are totally right!! In addition, comparing your solution to my "on paper" examples permit to realise that I was not correcting to the number of permutations of one specific configuration. Many thanks for your answer which is really clear! To come back to the problem, for big numbers, computers cannot calculate (the factorial) in floating point. Is there a way to get pretty good approximation of the probabilities? I will try to do the calculus myself, I just want to get hints. At the end I would to calculate the mean and the $\alpha%$ confidence interval around the mean $\endgroup$
    – Protra
    Aug 18 '16 at 9:33
  • $\begingroup$ @Protra: You're welcome! You could use Stirlings approximation: $n!\sim\left(\frac{n}{e}\right)^n\sqrt{2\pi n}$ $\endgroup$
    – epi163sqrt
    Aug 18 '16 at 9:47
  • $\begingroup$ Hello Markus. I would like to address an issue. Is there a way to consider $k$ in the problem above as a random variable with a probability distribution instead of a fixed number? Is my question valid, firstly? In addition, is there a place where we can discuss? Or comments are made for this purpose? $\endgroup$
    – Protra
    Aug 24 '16 at 12:32

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.