A combinations problem.

Question

Given a number $N$ and $M$, how to find the possible combinations for

 a+b+... = N where a,b... <= M.

Ex:

N = 3 and M = 3

So the combinations would be

(3,[1+1+1],[1+2],[2+1]) which is 4.

Answer 1

Hint let $r=\min\{M,N\}$.You need to find all possible combination from the set $\{1, 2, \cdots, r\}$ that sum up to $N$. You have three cases (two cases in fact but I separate the 1st and the 2nd):

• $N=M$: the combination is $2^{N-1}$. Because you are looking for a combination in the set $\{1, \cdots, N\}$ that sum up to $N$.
• $N=\min\{M,N\}$: the combination is $2^{N-1}$. Same reason as first bullet.
• $M=\min\{M,N\}$: the combination is $2^{M}-1$. Here you are looking for a combination in the set $\{1, \cdots, M\}$ that sum up to $N$. You have to be careful here because I think you have to study the difference $N-M$. At the first time, I supposed that $N-M=1$ to get $2^M-1$ but the more general formula in this case I think is: $2^M-2+\sum_{i=1}^{N-M}i=2^M-2+\dfrac{(N-M)(N-M+1)}{2}$.

If I did understand the question. I hope it helps.

Answer 2

Do you want to count $(1,2)$ and $(2,1)$ as being distinct? If not, then the number of combinations is just the coefficient of $x^N$ in $\prod_{k = 1}^M \frac{1}{1-x^k}$.

Answer 3

A partition of a positive integer $n$, is a way of writing $n$ as a sum of positive integers.

Two sums that differ only in the order of their summands are considered the same partition.

If the order does matter, then each sum becomes a composition.

For example, $4$ can be partitioned in five distinct ways:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

And it can be composed in eight distinct ways:

4
3 + 1
1 + 3
2 + 2
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
1 + 1 + 1 + 1

---

Function $p(n)$ represents the number of possible partitions of a natural number $n$:

• The generating function for $p(n)$ is given by $\displaystyle \sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right)$

• An asymptotic expression for $p(n)$ is given by $\displaystyle p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right)$

Function $c(n)$ represents the number of possible compositions of a natural number $n$:

• It is given by $\displaystyle c(n) = 2^{n-1}$

---

See here for more information on partitions.

See here for more information on compositions.

Answer 4

Let $S_a = S_b = S_c = ... = S_N = 1+x+x^2+...+x^M$. Now consider the product $P=S_aS_bS_c...S_N$. In this product the coefficient of $x^N$ is what we require.

$$ P = \left(\sum _{i=0}^M x^i\right)^N = \left(\frac{1-x^{M+1}}{1-x}\right)^N$$