0
$\begingroup$

Let $n$ be a positive integer. Determine the number of solutions to $x_1 + \cdots + x_k \leq n$ with nonnegative integer solutions. Determine the number of solutions with positive integer solutions.

I understand why every positive solution of $x_1 + · · · + x_k = m$ corresponds to an ordered partition of $m$. However, I do not understand why the number of positive solutions of $x_1 + \cdots + x_k \leq n$ is

$$\sum_{m=k}^{n}\binom{m-1}{k-1}.$$

Similarly, I do not understand how using multisets we obtain $\binom{n+k}{k}$ for the nonnegative integer solutions. Can someone explain this?

$\endgroup$
3
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Stars_and_bars_(combinatorics). Just add another non-negative variable to make it into an equality. $\endgroup$
    – Rushabh Mehta
    Commented Feb 13, 2021 at 16:45
  • $\begingroup$ Do you understand why the number of positive solutions to $x_1 + \cdots + x_k = m$ is $$\binom{m-1}{k-1}?$$ $\endgroup$
    – user
    Commented Feb 13, 2021 at 17:21
  • $\begingroup$ @user Yes, the number of ordered $k$-partitions of $n$ equals $\binom{n-1}{k-1}$. $\endgroup$
    – Alexis Sandoval
    Commented Feb 13, 2021 at 18:07

1 Answer 1

Reset to default
2
$\begingroup$

Consider some positive solution of the inequality $$x_1+\cdots+x_k\le n\tag1.$$ It is necessarily a solution of an equation $$x_1+\cdots+x_k=m\tag2$$ for some $m:\ k\le m\le n$. Therefore the number of solutions of the inequality (1) is the sum of the numbers of solutions of the equations (2) for all $m:\ k\le m\le n$: $$\sum_{m=k}^n\binom{m-1}{k-1}=\binom{n}k. $$ The last expression can be obtained also in a direct though somewhat tricky way.

The same formula work for the number of non-negative solutions as well. Just replace $n(m)$ with $n(m)+k$.

$\endgroup$
3
  • 2
    $\begingroup$ Your last (unnumbered) equation is called the Hockey-stick identity. $\endgroup$
    – robjohn ♦
    Commented Feb 14, 2021 at 8:09
  • $\begingroup$ Hello @user , sorry but I don't understan very well the non-negative part. Can you explain that? I try to use multisets but I am not getting it. $\endgroup$
    – Alexis Sandoval
    Commented Feb 26, 2021 at 6:47
  • 1
    $\begingroup$ @AlexisSandoval The number of the compositions of a number $n $ into $k $ non-negative parts is equal to the number of the compositions of a number $n+k$ into $k $ positive parts. Think about subtracting 1 from the every part of the latter. $\endgroup$
    – user
    Commented Feb 26, 2021 at 8:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .