Find the number of ways to select $1,2,3,4,5,6,7,8,9,10$ fruits from a pile (using generating functions)

Question

Find the number of ways to select $1,2,3,4,5,6,7,8,9,10$ fruits from a pile of $3$ apples, $5$ oranges and $2$ bananas. (Use generating functions.)

Any tips?

Answer 1

We encode zero up to

• three apples as: $\ \quad1+x+x^2+x^3=\frac{1-x^4}{1-x}$

• five oranges as: $\ \quad1+x+x^2+x^3+x^4+x^5=\frac{1-x^6}{1-x}$

• two bananas as: $\quad 1+x+x^2=\frac{1-x^3}{1-x}$

Denoting with $[x^k]$ the coefficient of $x^k$ of a series, we are looking for \begin{align*} \color{blue}{[x^k]\frac{(1-x^4)(1-x^6)(1-x^3)}{(1-x)^3}}\qquad \qquad 1\leq k\leq 10 \end{align*}

We obtain \begin{align*} [x^k]&\frac{(1-x^4)(1-x^6)(1-x^3)}{(1-x)^3}\\ &=[x^k](1-x^4)(1-x^6)(1-x^3)\sum_{j=0}^\infty\binom{-3}{j}(-x)^j\tag{1}\\ &=[x^k](1-x^3-x^4-x^6+x^7+x^9+x^{10})\sum_{j=0}^\infty\binom{j+2}{2}x^j\tag{2}\\ \end{align*}

Comment:

• In (1) we apply the binomial series expansion.

• In (2) we expand the factors up to powers of $x^{10}$ since higher powers do not contribute to $[x^k]$ for $1\leq k\leq 10$. We also apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

Example: We calculate from (2) the coefficient of $x^k$ for $k=7$. \begin{align*} \color{blue}{[x^7]}&\color{blue}{(1-x^3-x^4-x^6+x^7+x^9+x^{10})\sum_{j=0}^\infty\binom{j+2}{2}x^j}\\ &=\left([x^7]-[x^4]-[x^3]-[x^1]+[x^0]\right)\sum_{j=0}^\infty\binom{j+2}{2}x^j\\ &=\binom{9}{2}-\binom{6}{2}-\binom{5}{2}-\binom{3}{2}+\binom{2}{2}\\ &=36-15-10-3+1\\ &\,\,\color{blue}{=9} \end{align*}

The $9$ solutions of seven fruits are $$ \begin{array}{c|c|c} \text{apples}&\text{oranges}&\text{bananas}\\ \hline 3&4&0\\ 3&3&1\\ 3&2&2\\ 2&5&1\\ 2&4&1\\ 2&3&2\\ 1&5&1\\ 1&4&2\\ 0&5&2\\ \end{array} $$

Answer 2

I am guessing, you consider choosing different fruits of same variety as identical choice, otherwise question will become straightforward.

So, suppose you have to pick $n$ fruits, where $n =1,2,3,...10$

You can seek no. of solution of equation $x_1 +x_2 +x_3 = n$, for different values of $n$, where $x_1,x_2,x_3$ represent no. of apples, oranges and bananas.

By, generating function, you know it is $\binom {2+n}n$

For different values of $n$, it becomes $\sum_{n=1}^{10}\binom {2+n}n= \sum_{n=1}^{10}\binom {2+n}2 = \sum_{n=3}^{12}\binom {n}2 = \frac12 [ \sum_{n=3}^{12} n^2- \sum_{n=3}^{12}n] =285 $