Split $6$ apples and $7$ oranges between $4$ people with conditions using generating functions

combinationscombinatoricsgenerating-functions

We want to find the number of ways to split $6$ apples and $7$ oranges between $4$ people so that in each case each of the persons gets:

  1. at least $1$ apple
  2. at most $2$ oranges
  3. at least $1$ apple and at most $2$ oranges

I tried direct counting in $1$ as follows: we give each person an apple sto we have $2$ apples and $7$ oranges left. Then using stars and bars (combinations with repetition) we want to find all ways of distributing $2$ apples to $4$ people which I found to be
$$
\newcommand\mchoose[2]{
\left(\!\!\left(#1\atop #2\right)\!\!\right)}
\mchoose{2+1}4=\binom{3+4-1}{4}=15$$ and in the same manner we calculate $$\mchoose{7+1}4=\binom{7+4-1}{4}=330$$ and multiplying (by the product rule, since the choices are independent) we get $4950$ possible ways.

On the other hand I tried using generating functions, but I am not sure they work that way:

For each person we can have $1,2$ or $3$ apples (since if somebody gets $4$ there are not enough for everyone to get at least $1$) and $0$ to $7$ oranges. Then the generating function for a person is $$(x+x^2+x^3)(1+x+x^2+x^3+…+x^7)$$ so then I tried raising this to the $4$th power (since we have 4 people) and calculating the coefficient of $x^{13}$ (since we have $13$ objects) which appeared to be a lot less, and more precisely, $1296$. I have a few doubts, since I am not sure whether I should use ordinary generating functions or exponential ones and, moreover, I am not sure if I'm counting impossible scenarios (such as everyone getting e.g. $7$ oranges, which I do not take into consideration sicne we are only interested in coefficients $\leq 13$).

I would like to understand the general idea behind this kind of problems and how to solve the questions in this specific one, since they seem natural and tend to appear a lot in combinatorics so far. Thanks in advance!

Best Answer

The generating function $\sum_{n\geq 0} a_nx^n$ where $a_n$ is the number of distributing $n$ apples between 1 person in such a way that he has at least one apple is $$ \sum_{n\geq 0}a_nx^n=x+x^2+x^3+\dots=\frac{x}{1-x}. $$

Hence for 4 people the generating function is $(x/(1-x))^4$. Since we have $6$ apples we are looking for $[x^6](x/(1-x))^4=10$.

Similarly, for oranges the generating function for one person is just $\frac 1{1-y}$. Hence for 4 people the generating function is $(1-y)^{-4}$ and the answer we are after is $$ [y^7](1-y)^{-4}=120. $$

To summarize the answer to this question is $$ [x^6y^7]\frac{x^4}{(1-x)^4(1-y)^4}=1200. $$

2.

The generating function of apples now is $1/(1-x)$ and that for oranges $1+y+y^2$ so that we are looking for $$ [x^6y^7]\left(\frac{1+y+y^2}{1-x}\right)^4=336. $$

3.

Similarly, the answer is $$ [x^6y^7]\left(\frac{x(1+y+y^2)}{1-x}\right)^4=40. $$

Related Question