Here is a more specific question:
Find the number of ways of giving $10$ identical gift boxes to 6 people : $A$, $B$, $C$, $D$, $E$, $F$ in such a way that total number of boxes given to $A$ and $B$ together does not exceed $4$.
I am currently learning about problems which are related to Combinations with Repetitions, for the most part of it I am able to solve the basic questions, but this one stumped me.
Can you suggest how to approach this problem?
On
Redefine the questions as $U = \{\text{gift in A or B}\}$ and $V$ the complement. Going over to probability we can see that $N=\{\text{fraction}\, U=n\} \in Bin(1/3,10)$ and we are taskt to evaluate
$$ P(N <= 4) = q^10 + 10*p*q^9 + \frac{10*9}{2}p^2q^8 + \frac{10*9*8}{2*3}p^3q^7 + \frac{10*9*8*7}{2*3*4}p^4q^6, $$ with $p=1/3,q=2/3$. Now multiply by $6^{10}$ and you get the number of combinations.
On
Assume for the moment that we have an unlimited supply of boxes to be distributed to $6$ individuals, whereby the first two together may obtain no more than $4$ boxes. In a generating functions approach the combined allocations to A and B then are counted as $$1+2x+3x^2+4x^3+5x^4={1-6x^5+5x^6\over(1-x)^2}\ ,$$ and the allocations to the remaining four people as $$(1+x+x^2+x^3+\ldots)^4={1\over(1-x)^4}\ .$$ The generating function for the full problem then becomes $$\eqalign{F(x)&={1-6x^5+5x^6\over(1-x)^6}=(1-6x^5+5x^6)\sum_{k\geq 0}{-6\choose k}(-x)^k\cr &=(1-6x^5+5x^6)\sum_{k\geq0}{5+k\choose k}x^k\ .\cr}$$ We now have to extract the coefficient of $x^{10}$ in this expansion: $$N={15\choose10}-6{10\choose5}+5{9\choose4}=2121\ .$$
On
The problem may be rephrased by asking each people to have at least one gift. The new number of gifts would be 16 and the A+B condition, 6.
Let's place the 16 gifts in a row. There are 15 spaces between them in which we have to place 5 delimiters. In general, g gifts may be distributed to p people in $\binom {g-1} {p-1}$ ways.
The A+B condition means that the second delimiter has to be in the 2-nd, 3-rd, 4-th, 5-th or the 6-th space. The rest of four delimiters may be placed as follows :
$\binom{1}{1}\binom{13}{3} + \binom{2}{1}\binom{12}{3} + \binom{3}{1}\binom{11}{3} + \binom{4}{1} \binom{10}{3} +\binom{5}{1}\binom{9}{3} = 2121$
On
Of the $10$ boxes, suppose $r$ boxes are given to $A$ and $b$ together. Then $0\leq r \leq 4$. The number of ways of giving $r$ boxes to $A$ and $B$ is $$ {2+r-1\choose r} = {r+1\choose r} = r+1.$$
The number of ways in which the remaining $(10-r)$ boxes can be given to $C, D, E, F$ is $$ {4+(10-r)-1\choose 10-r} = {13-r \choose 10-r} = {13-r \choose 3}$$
Consequently, the number of ways in which $r$ boxes can be given o $A$ and $B$ and $(10-r)$ boxes to $C, D, E, F$ is, by product rule, $$(r+1) \times {13-r \choose 3}$$
Since $0 \leq r \leq 4$, the total number of ways in which the boxes may be given is, by the sum rule, $${\sum_{r=0}^{4} (r+1) \times {13-r \choose 3} }$$
Let $x_A$, $x_B$, $x_C$, $x_D$, $x_E$, and $x_F$ represent the number of gift boxes given to persons $A$, $B$, $C$, $D$, $E$, and $F$, respectively. Since a total of ten boxes are distributed to these six people, $$x_A + x_B + x_C + x_D + x_E + x_F = 10 \tag{1}$$ Since $A$ and $B$ together receive at most four of these gifts, we must solve equation 1 in the nonnegative integers subject to the restriction that $x_A + x_B \leq 4$.
This can be solved by casework. If $$x_A + x_B = k \tag{2}$$ then for equation 1 to be satisfied, we must have $$x_C + x_D + x_E + x_F = 10 - k \tag{3}$$ for $0 \leq k \leq 4$.
A particular solution of the equation $$x_1 + x_2 + \cdots + x_n = m \tag{4}$$ in the nonnegative integers corresponds to the placement of $n - 1$ addition signs in a row of $m$ ones. For instance, if $m = 10$ and $n = 5$, $$1 + + 1 1 1 + 1 1 + 1 1 1 1$$ corresponds to the solution $x_1 = 1$, $x_2 = 0$, $x_3 = 3$, $x_4 = 2$, $x_5 = 4$. Consequently, the number of solutions of equation 4 in the nonnegative integers is $$\binom{m + n - 1}{n - 1}$$ since we must choose which $n - 1$ of the $m + n - 1$ positions required for $m$ ones and $n - 1$ addition signs will be filled with addition signs.
Thus, equation 2 has $$\binom{k + 2 - 1}{2 - 1} = \binom{k + 1}{1} = k + 1$$ solutions and equation 3 has $$\binom{10 - k + 4 - 1}{4 - 1} = \binom{13 - k}{3}$$ solutions in the nonnegative integers. Thus, when $x_A + x_B = k$ and $x_C + x_D + x_E + x_F = 10 - k$, the number of solutions of equation 1 is $$(k + 1)\binom{13 - k}{3}$$
Since $0 \leq k \leq 4$, the number of ways of distributing ten gifts to persons $A$, $B$, $C$, $D$, $E$, and $F$ so that $A$ and $B$ together receive at most $4$ of those gifts is $$\sum_{k = 0}^{4} (k + 1)\binom{13 - k}{3} = \binom{13}{3} + 2\binom{12}{3} + 3\binom{11}{3} + 4\binom{10}{3} + 5\binom{9}{3}$$