Lesson 13

The generating function for choosing apples is as follows: \[\mathcal{A}(x)=1+x^{2}+x^{4}+\dotsb=\frac{1}{1-x^2}\ .\] Indeed, there is one way to take zero apples, one way to take two apples, and so on. For bananas, it is similar: \[\mathcal{B}(x)=1+x^{5}+x^{10}+\dotsb=\frac{1}{1-x^5}\ .\] The generating functions for oranges and pears turn out to be polynomials since they cannot be taken in amounts greater than a certain limit: \[\begin{align*}\mathcal{O}(x)&=1+x+x^{2}+x^{3}+x^{4}=\frac{1-x^5}{1-x}\ ,\\ \mathcal{P}(x)&=1+x \ .\end{align*}\]

The generating function for our problem will then be the product of all four found generating functions: \[\begin{align*}\mathcal{A}(x)\mathcal{B}(x)\mathcal{O}(x)\mathcal{P}(x)&= \frac{1}{1-x^2}\frac{1}{1-x^5}\frac{1-x^5}{1-x}(1+x)=\\&=\frac{1}{(1-x)^2}=\\&=1+2x+3x^{2}+4x^{3}+\dotsb\end{align*}\] Miraculously, everything simplifies to the generating function \[\mathcal{N}(x)=\frac{1}{(1-x)^2},\] whose expansion we already know: \[[x^{n}]\left(\frac{1}{(1-x)^2}\right) = n + 1.\] Thus, the answer will be \((n+1)\).