How many ways to fill the bag with fruits?

Any filling of the bag can be described uniquely by three non-negative integers,

• $x$ = total number of apples + cantaloupes,

• $y$ = total number of bananas + durians,

• $z$ = total number of raspberries.

Note that each value of $x$ gives a unique number of apples and cantaloupes ( $x = 41a + c$ ), and similarly $y$ gives a unique number of bananas and durians ( $y = 2b + d$ ).

The constraint $x + y + z = 2018$ can be viewed as placing 2018 "stars" in a line and separating them anywhere with 2 "bars". Thus we must choose two out of $2018 + 2$ possible locations for the bars; the number of possibilities is $\binom{2018+2}2 = \tfrac12\cdot 2020\cdot 2019 = 1010\cdot 2019 = 2\,019\,000 + 20\,190 = \boxed{2\,039\,190}.$ (No calculators were touched in the process.)

The generating functions for...

• ... the number of ways to choose $n$ apples is $1 + x^{41} + x^{82} + \cdots = \dfrac{1}{1-x^{41}}$
• ... the number of ways to choose $n$ bananas is $1 + x^2 + x^4 + \cdots = \dfrac{1}{1-x^2}$
• ... the number of ways to choose $n$ cantaloupes is $1 + x + x^2 + \cdots + x^{40} = \dfrac{1-x^{41}}{1-x}$
• ... the number of ways to choose $n$ durians is $1+x$
• ... the number of ways to choose $n$ raspberries is $1 + x + x^2 + \cdots = \dfrac{1}{1-x}$

It follows that the generating function for the number of ways to choose $n$ pieces of fruit is the product $\left(\frac{1}{1-x^{41}}\right)\left(\frac{1}{1-x^2}\right)\left(\frac{1-x^{41}}{1-x}\right)\left(1+x\right)\left(\frac{1}{1-x}\right) = \frac{1}{(1-x)^3} = \sum_{n=0}^\infty \binom{n+2}{2}x^n$ so the number of ways to fill the bag with $2018$ pieces of fruit is $\binom{2018+2}{2} = \boxed{2039190}$

Notes :

• For those who haven't seen it before, I have used the identity $\frac{1}{(1-x)^{k+1}} = \sum_{n=0}^\infty \binom{n+k}{k} x^n$ which can be shown by induction by starting with $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$ and taking $k$ th-order derivatives.
• One way to avoid generating functions is to note that we can have any number of apples+canteloupes, and for each number there is precisely one way to do it using these two fruits. Similarly, we can have any number of bananas+durians, and for each number there is precisely one way to do it. Then the problem becomes equivalent to the one where we have three fruit types and no restrictions. That is, we would just need to find the number of non-negative integer solutions to $a+b+c = 2018,$ which in turn can be counted with stars and bars to be $\binom{2018+3-1}{3-1}$

Let us create a generating function for each restriction.

apples: (1+x^41+x^82+...)=1/(1-x^41) bananas: (1+x^2+x^4+...)=1/(1-x^2) cantaloupes: 1+x+x^2+...x^41= (x^41-1)/(x-1) durian: (1+x) raspberries: 1+x+x^2+...=1/(1-x)

When we multiply these, we obtain -1/(x-1)^3.

We want the coefficient of x^2018, which we can obtain by the negative binomial theorem:

• 2018+3-1 choose 2018= 2039190.