Positive integer solutions to $x_1+...+x_n=k$.

Question

What is the number of strictly positive integer solutions $(x_1,...,x_n)$ to the equation $x_1+...+x_n=k$?

Say $n=3$ and $k=5$, then we have $x_1+x_2+x_3=5$. It's easy to find that the number of solutions to this equation is $6$.

This is a standard placing $5$ people on $3$ chairs problem, with respect to order. So why isn't the answer simply ${5\choose 3}$, or in the general case of placing $k$ people on $n$ chairs ${k\choose n}$? Why do I have to subtract the $1$?

Answer 1

A particular solution of the equation $$x_1 + x_2 + \cdots + x_n = k $$ in the positive integers corresponds to the placement of $n - 1$ addition signs in the $k - 1$ spaces between successive ones in a row of $k$ ones. Thus, the equation has
$$\binom{k - 1}{n - 1}$$ solutions in the positive integers.

Consider your example. If we wish to find the number of solutions of the equation $$x_1 + x_2 + x_3 = 5$$ we must decide which two of the four spaces between successive ones in a row of five ones will be filled with addition signs. $$1 \square 1 \square 1 \square 1 \square 1$$ For instance, if we fill the second and fourth spaces with addition signs, we obtain $$1 1 + 1 1 + 1$$ which corresponds to the solution $x_1 = 2$, $x_2 = 2$, and $x_3 = 1$. Observe that there are $\binom{4}{2} = 6$ such choices, as you found.

Answer 2

Think of it like this, for $x_1,x_2,\dots,x_n\geq 0$. $$x_1+x_2+\dots+x_n=k\tag{1}$$

Means that you have a line of $k$ elements, and you want to divide the line into $n$ sections.

For $x_1+x_2+x_3=5$ it may look like this: $$\times|\times\times|\times\times$$

You have $5+3-1$ empty places, and you need to choose which one of them is are $\times$'s (the rest will be $|$'s). There are $\binom{5+3-1}{5}$ ways to accomplish this. In the general there are $\binom{n+k-1}{k}$ ways.

---

Edit: If you want $x_1,x_2,\dots,x_n> 0$ you can let $x_i=y_i+1$, where $y_i\geq 0$. You can then rewrite equation (1) as:

$$y_1+y_2+\dots+y_n=k-n$$

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

By definition:

\begin{align} \sum_{x_{1} = 1}^{\infty}\cdots\sum_{x_{n} = 1}^{\infty} \bracks{z^{k}}z^{x_{1} + \cdots + x_{n}} & = \bracks{z^{k}}\pars{\sum_{x = 1}^{\infty}z^{x}}^{n} = \bracks{z^{k}}\pars{z \over 1 - z}^{n} = \bracks{z^{k - n}}\pars{1 - z}^{-n} \\[5mm] & = \bracks{k - n \geq 0}{-n \choose k - n}\pars{-1}^{k - n} = \bbx{\bracks{k \geq n}{k - 1 \choose k - n}} \\[5mm] & = \bbx{\bracks{k \geq n}{k - 1 \choose n - 1}} \end{align}

Your example: $\ds{n = 3}$ and $\ds{k = 5}$ yields $\ds{{5 - 1 \choose 3 - 1} = {4 \choose 2} = \color{red}{6}}$.