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?

Question

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?

Answer 1

It is a simple function call. In Mathematica, for example:

IntegerPartitions[5, {1, 5}, {1, 2, 3}]

(* {{3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}} *)

If you merely seek the number of such partitions:

Length@IntegerPartitions[5, {1, 5}, {1, 2, 3}]

(* 5 *)

[This function asks for all integer partitions of the number 5, of length 1 through 5, using only the numbers 1, 2 and 3. Then take the "length" of this list, i.e., the number of partitions.]

Another example:

IntegerPartitions[10, {1, 10}, {1, 2, 3}]

(* {{3, 3, 3, 1}, {3, 3, 2, 2}, {3, 3, 2, 1, 1}, {3, 3, 1, 1, 1, 1}, {3, 2, 2, 2, 1}, {3, 2, 2, 1, 1, 1}, {3, 2, 1, 1, 1, 1, 1}, {3, 1, 1, 1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {2, 2, 2, 2, 1, 1}, {2, 2, 2, 1, 1, 1, 1}, {2, 2, 1, 1, 1, 1, 1, 1}, {2, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}} *)

Length@IntegerPartitions[10, {1, 10}, {1, 2, 3}]

(* 14 *)

Answer 2

If you wish to find the number of ways to express a positive integer $n$ as the sum of $m$ positive integers ($m\le n$) and each of the positive integers must be less than or equal to a certain value $\alpha$ then the number of such integers will be the number of positive integral solutions to these equations:

$x_1+x_2=n$

$x_1+x_2+x_3=n$

$x_1+x_2+x_3+\cdots+x_m=n$

such that $1\le x_i \le \alpha$

for the equation $x_1+x_2=n$

the number of positive integral solutions is the same as the coefficient of $x^n$ in the expansion $(x+x^2+x^3+\cdots+x^\alpha)^2$

for the equation $x_1+x_2+x_3=n$

the number of positive integral solutions is the same as the coefficient of $x^n$ in the expansion $(x+x^2+x^3+\cdots+x^\alpha)^3$

for the equation $x_1+x_2+x_3+\cdots+x_m=n$

the number of positive integral solutions is the same as the coefficient of $x^n$ in the expansion $(x+x^2+x^3+\cdots+x^\alpha)^m$

So the total number of the solutions of all of these equations is the desired number.

This method of finding the coefficient in the expansion works because the term $x^n$ is formed only if in the multiplication, the powers of some terms get added to give the specified $n$.

For example in your question, $5$ has to be expressed as the sum of positive integers not greater than $3$

$x_1+x_2=5$

Coefficient of $x^5$ in the expansion of $(x+x^2+x^3)^2$

$=(x+x^2+x^3)(x+x^2+x^3)$ $=x^2+2x^3+3x^4+2x^5+x^6$

Thus,$[x^5]=2$ Hence, 5 can be expressed in 2 ways as the sum of 2 positive integers lesser than or equal 3, which are $(2,3)$ and $(3,2)$ ( yes, this method gives us the ordered pairs) You can do the same for rest of the equations.

In general as well, if you allow integers from a certain interval (not only positive) say, $ \alpha \le x_i \le \beta$ then the number of ways to express $n$ as sum of integers (order is considered) is ($[x^n]$ is the coefficient of $x^n$) $$\sum_{m=2}^n [x^n] (x^ \alpha+x^{\alpha+1}+x^{\alpha+2}+\cdots+x^ \beta)^m$$

Answer 3

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$.