0
$\begingroup$

I am studying basic statistics for fun. I have been reading about simple combinatorics as the first step. I am trying to solve the following problems

8 identical items are distributed for 4 people. In how many different ways the items may be distributed?

So it could be that any of the four persons receives all of the items, or one of them receive all but one and someone else receives the final one, etc.

I think I cannot solve this with simple consideration of permutations, variations, or combinations. What should I do?

$\endgroup$
1
  • $\begingroup$ Could you elaborate on what a "distribution" of items is? Is it the sequence of assignments of items to people? The (unordered) set of assignments? The configuration of which items end up with which people? (All these have different counts.) How exactly do you want to interpret the assertion that these items are "identical"? $\endgroup$
    – whuber
    Nov 9, 2015 at 14:25

2 Answers 2

2
$\begingroup$

I believe you can find more information about this type of problems if you search about putting n balls (items in you problem) in k boxes (people). A graphical aid to solve it is given by the bars and stripes formulation.

If you allow for the possibility than a person does not gen any of the items then the solution is

$$ {n+k-1 \choose n} = {8+4-1 \choose 8} = {11 \choose 8} = 165 $$

$\endgroup$
0
$\begingroup$

First of all whuber is right, there are some precisions that you should have specified.

Here are the assumptions on which I based my answer:

  1. The persons are distinguishable
  2. The order in which you assign the items is irrelevant

Let's call $F(n, k)$ then number of different ways in which you can assign k items to n people.

First thing to establish is that $$\begin{equation} \begin{split}F(n, k+1) &= \sum_{i=0}^{n}number\:of\:cases\:if \:last\:box\:has\:i\:elements \\ &= \sum_{i=0}^{n}number\:of\:cases\:if \:first\:k\:\:boxes\:have\:n-i\:elements\\ &= \sum_{i=0}^{n}F(n-i, k)\\ &=\sum_{i=0}^{n}F(i, k)\end{split} \end{equation}$$

Second set of facts to establish is that: $$\forall{k}\:F(0,k) = 1$$ $$\forall{k}\:F(n,1) = 1$$ Note that based on the 3 formulas above, you can calculate F(n, k) for every n and k by recursion, and that means that the function F that verifies those 3 equations is unique

Now, let's demonstrate that $$F(n,k)=\dbinom{n+k-1}{n}$$ Let's call $$P(n,k)=\dbinom{n+k-1}{n}$$ Given the theorem $$\dbinom{n + 1}{k + 1} =\sum_{i=k}^{n}\dbinom{i}{k}$$

That means that $$\begin{equation} \begin{split} P(n,k+1) &=\dbinom{n + (k + 1)- 1}{n } \\ &=\dbinom{n + k}{k } \\ &=\sum_{i=k - 1}^{n+k -1}\dbinom{i}{k - 1} \:\:(Given\:the\:theorem\:above)\\ &=\sum_{i=0}^{n}\dbinom{i + k -1}{k - 1}\\ &=\sum_{i=0}^{n}\dbinom{i + k -1}{i}\\ &=\sum_{i=0}^{n}P(i,k)\end{split} \end{equation}$$

Also we have: $$\forall{k}\:P(0,k) = 1$$ $$\forall{k}\:P(n,1) = 1$$ That means that F = P

Conclusion: the number of unordered ways in which you can distribute n undistinguisable (identical) items on k distinguishable persons is $\dbinom{n+k-1}{n}$

P.S: I have a strong feeling there is a much simpler and intuitive demonstration for this theorem but I have never been able to find it. If somebody else can chip in that would be awesome!

$\endgroup$

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.