In how many ways we can have some natural numbers that their sum is equal to $n$ and none of them is greater than $k$, for given $n$ and $k$?
NOTE: We don't know the number of the elements.
Can anyone help me with this problem? I can't find anything on the internet. For example, for $n = 5$ and $k = 2$ the answer is $8$:
2 + 2 + 1, 2 + 1 + 2, 1 + 2 + 2, 1 + 1 + 1 + 2, 1 + 1 + 2 + 1
1 + 2 + 1 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1
On
This problem is very closely related to the number of partitions of n (https://en.wikipedia.org/wiki/Partition_(number_theory)). So for k = n, the number of ways in which it can be done will approximately be $$\frac{1}{4n \sqrt{3}}exp(\pi \sqrt{\frac{2n}{3}})$$ Refering to the restricted partitions section may give further insight into the problem Edit : I found a problem which is a special case of this problem, which has a solution Number of partitions of $2n$ with no element greater than $n$
How about using generating functions? The number of ways to add $m$ positive integers each of which is less than or equal to $k$ so that their sum is $n$ is the coefficient of $x^n$ in $(x+x^2+\ldots+x^k)^m$. So the coefficient of $x^5$ in $\sum_{m=1}^{5} (x+x^2)^m$ is the answer for your example, which is 8.