How many ways can we get a number by addition if each part of the addition has to be smaller or equal to a set value? For example, if we need to get 5 with the largest number we can use being 3, we can use:


*

*3 + 2

*3 + 1 + 1

*2 + 2 + 1

*2 + 1 + 1 + 1

*1 + 1 + 1 + 1 + 1


Is there any way to find out the solution with any two numbers without calculating every one of them?

We can calculate  the number of ways with the help of generating functions. We encode the usage of 


*

*zero or more $1$s as $1+x+x^2+x^3+\cdots=\frac{1}{1-x}$

*zero or more $2$s as $1+x^2+x^4+x^6+\cdots=\frac{1}{1-x^2}$

*zero of more $3$s as $1+x^3+x^6+x^9+\cdots=\frac{1}{1-x^3}$
and we look for the coefficient of $x^5$ denoted with $[x^5]$ of the product $\frac{1}{(1-x)(1-x^2)(1-x^5)}$.
This needs a little algebra, but we can keep it simple since we can skip powers greater than $5$ when multiplying out.

We obtain
  \begin{align*}
\color{blue}{[x^5]}&\color{blue}{\frac{1}{(1-x)(1-x^2)(1-x^3)}}\\
&=[x^5]\left(1+x+x^2+x^3+x^4+x^5\right)\left(1+x^2+x^4\right)\left(1+x^3\right)\tag{1}\\
&=[x^5]\left(1+x+x^2+x^3+x^4+x^5\right)\left(1+x^2+x^3+x^4+x^5\right)\tag{2}\\
&=[x^5]\left(1\cdot x^5+x\cdot x^4+x^2\cdot x^3+x^4\cdot x+x^5\cdot 1\right)\tag{3}\\
&=[x^5]5x^5\\
&\,\,\color{blue}{=5}
\end{align*}

Comment:


*

*In (1) we  expand $\frac{1}{1-x}$, $\frac{1}{1-x^2}$ and  $\frac{1}{1-x^3}$  but only up to powers raised to $x^5$ since higher powers do not contribute to $[x^5]$.

*In (2) we multiply out the two right-most terms again skipping powers greater than $5$.

*In (3) we multiply out skipping all factors which do not give $x^5$.
