<s>[INST] 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?
 [/INST] 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$.
</s>