I have 6 apples. These apples are the same, they do not differ. I have 3 persons.
Now I want to distribute the 6 apples to the 3 persons, under the assumption that
a) All the apples have to be given away
b) assumption a is not necessary, so I can give for example. 1 apple to Person A and no apples to Person B and C. I do not have to give away an apple to a person and I can also hand out completely none.
c) assumption a is not necessary, but each person has to get at least one apple.
For assumption a) I thought I draw it in a table:
Now first of all I am not sure if I did it right. I end up with 28 possible different ways to distribute the apples.
Question1: Is this right?
But more important:
Question2: What is the name of this kind of problem?
For solving it I only found the stars and bars method and the theorem 2. According to this my n is 6 and k is 3, which gives me
And indeed I get 28. But I am not sure.
Question3: How would the assumption sound like (how would one formulate it), if it would be stars and bars theorem 1?
For assumption b)
I am also not sure, specifically because there are too much possibilites to draw it. I think it should be $n!/k!=6!/3!=6*5*4=120$.
Question4: Is this really correct?
Question5: What is the correct name for this problem?
I think it is "repetition not allowed, order does matter".
Question6: How would the binomial coefficient be properly explained here?
So $6!/3!=n!/k!$ is not equal to $\binom{n}{k}$. I am not sure but I think it should be $\binom{n}{n-k}=6!/3!$
Question7: Suppose it would be a "repetition not allowed, order does not matter" problem. I have troubles to imagine this. How would this look like in this example?
So I think it would be that I completely ignore the persons. I just ask myself, how many possibilites are there to distribute the apples in total. And I can distribute all of them (6), 5, 4, 3, 2, 1, or none. So I have 7 possibilites. This would be I can take 6 apples (or none) and I have one repetition. So
I am not sure about the binomical coefficient in this case. The intention would be to say I have 6 apples and I have one repetition. However, this leads to only 6 possibilities, using the formula and binomial coefficient for this "repetition not allowed and without order" problem:
Or am I wrong an "repetition not allowed and without order" here in this case means how many possibilites do I have to distribute the apples, but I have to give at least one apple. So to translate it to an urn model this means I have 6 apples in a box which are not the same. So 6 apples with different color and with one repetition and I pull once. So I have 6 different possibilites, but not the possibilty to grab no apple.
For assumption c)
Question8: This would be Stirling numbers of the second kind?
Question9: How would this look like in this case? So how does the formula look like, which OEIS is it and what is the result?
Thanks for any help!
Best Answer
Let $x_i$ be the number of apples person $i$ receives. Then $$x_1 + x_2 + x_3 = 6 \tag{1}$$ is an equation in the nonnegative integers. The number of solutions of equation 1 in the nonnegative integers is the number of ways the six apples (which we treat as indistinguishable objects) can be distributed to three persons.
A particular solution of this problem corresponds to the placement of two addition signs in a row of six ones. For instance, $$1 1 1 + 1 1 + 1$$ corresponds to the solution $x_1 = 3, x_2 = 2, x_3 = 1$, while $$1 1 + 1 1 1 1 +$$ corresponds to the solution $x_1 = 2, x_2 = 4, x_3 = 0$. The number of such solutions is $$\binom{6 + 3 - 1}{3 - 1} = \binom{8}{2} = 28$$ as you found since we must select which two of the eight positions required for six ones and two addition signs will be filled with addition signs.
In general, if we wish to distribute $k$ indistinguishable objects to $n$ distinct boxes, we must find the number of solutions of the equation $$x_1 + x_2 + \cdots + x_n = k \tag{2}$$ in the nonnegative integers. Equation 2 has $$\binom{n + k - 1}{n - 1}$$ solutions since we must choose which $n - 1$ of the $n + k - 1$ positions required for $k$ ones and $n - 1$ addition signs will be filled with addition signs.
The dual problem of selecting $k$ objects from $n$ types of objects, of which at least $k$ of each type are available, also leads to equation 2 and has the same number of solutions. That type of problem is called a combination with repetition.
Since fewer than six apples may be distributed, $$x_1 + x_2 + x_3 \leq 6 \tag{3}$$ is an inequality in the nonnegative integers. One way to solve this would be to find the number of solutions of the equation $$x_1 + x_2 + x_3 = k$$ for each integer $0 \leq k \leq 6$. Doing so yields $$\sum_{k = 0}^{6} \binom{k + 3 - 1}{3 - 1} = \sum_{k = 0}^6 \binom{k + 2}{2} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} + \binom{6}{2} + \binom{7}{2} + \binom{8}{2} = 84$$ Another approach is to introduce the slack variable $$s = 6 - x_1 + x_2 + x_3$$ Then $$x_1 + x_2 + x_3 + s = 6 \tag{4}$$ is an equation in the nonnegative integers with the same number of solutions as inequality 3. Using the formula stated above with $k = 6$ and $n = 4$, we obtain $$\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3} = 84$$ as above.
Again, we are distributing indistinguishable objects (the apples) to distinct boxes (the persons).
The two methods by which I solved this problem are related by the hockey-stick identity, which states that $$\sum_{i = r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1}$$ You can find a proof of the identity on the linked page.
First, give each person an apple. That leaves us with up to three apples to distribute to three persons, so we seek the number of solutions of the inequality $$x_1 + x_2 + x_3 \leq 3 \tag{5}$$ in the nonnegative integers, where $x_i$ this time represents the number of additional apples we give to each person.
We introduce the slack variable $$s = 3 - x_1 - x_2 - x_3$$ to transform the inequality into the equation $$x_1 + x_2 + x_3 + s = 3 \tag{6}$$ which is an equation in the nonnegative integers. Using the formula above, we obtain $$\binom{3 + 4 - 1}{4 - 1} = \binom{6}{3} = 20$$ possible distributions.
These are not Stirling numbers of the second kind since the apples are indistinguishable and the people are distinct. Stirling numbers of the second kind count the number of ways of distributing $n$ distinct objects to $k$ indistinguishable boxes so that no box is left empty.