How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

Solution 1:

We have $k$ people lined up in a row, and $n$ identical candies. We will give away some or all of the candies to the people, perhaps giving no candies to some of them, or maybe even all of them. And we will eat any candies that are left over. Think of our representative as being at the end of the row; so (s)he is the $(k+1)$-th person.

Let $j_1$ be the number of candies given to the first person, $j_2$ the number of candies given to the first two people, $j_3$ the number of candies given to the first three people, and so on up to $j_k$. Then any sequence $j_1 \le j_2\le \cdots\le j_k\le n$ identifies uniquely a candy giveaway scheme, and conversely any candy giveaway scheme produces a sequence of the type we are interested in.

So we ask: how many ways are there to give away $n$ candies to $k+1$ people?

There is a standard argument for this, often called Stars and Bars. It is easier to visualize giving away $n+k+1$ candies to $k+1$ people, at least one to each, and then taking away a candy from everyone. So there are just as many ways to distribute $n$ candies among $k+1$ people, with some possibly getting nothing, as there are ways to distribute $n+k+1$ candies among $k+1$ people, with everybody getting at least $1$.

Line up the $n+k+1$ candies, with a little gap between successive candies. There are $n+k$ such gaps. Put $k$ separators between the candies, and give all the candies up to the first separator to the first person, then all the candies between the first separator and the next one to the second person, and so on. There are $$\binom{n+k}{k}$$ ways to choose where the separators will go.

Solution 2:

Consider

$y_i = j_i + i$.

Show that the $y_i$ are distinct and in the range $1$ to $n+k$.

How many ways can you choose the $y$?

Solution 3:

Aryabhata’s already suggested an approach that uses the hint. I think that a somewhat different approach is simpler.

Let $d_0=j_1$, for $i=1,\dots,k-1$ let $d_i=j_{i+1}-j_i$, and let $d_k=n-j_k$. The numbers $d_0,\dots,d_k$ are non-negative, and $d_0+d_1+\dots+d_k=n$.

Conversely, if $\langle d_0,\dots,d_k\rangle$ is any $(k+1)$-tuple of non-negative integers whose sum is $n$, we can define $j_1=d_0$ and $j_{i+1}=d_i+j_i$ for $i=1,\dots,k-1$, and the $k$-tuple $\langle j_1,\dots,j_k\rangle$ clearly satisfies the condition $$0\le j_1\le j_2\le \dots\le j_k\le n\;.$$

Thus, you need only count the $(k+1)$-tuples $\langle d_0,\dots,d_k\rangle$ of non-negative integers such that $$\sum_{i=0}^kd_i=n\;,$$ which is a standard problem.

Solution 4:

Consider paths from $(0,0)$ to $(k,n)$ that increase one of the two components on each step, so they make $n+k$ steps, among which $k$ horizontal (increasing $i$ in $(i,j)$) and $n$ vertical (increasing $j$).

There are $\binom{n+k}k$ such paths.

Let the first point with first coordinate $i$ be $(i,j_i)$ for $i=1,\ldots,k$, then clearly $0\leq j_1\leq\cdots\leq j_k\leq n$. Moreover all such sequences of values are allowed, and they determine the path: the horizontal steps are precisely those from $(i-1,j_i)$ to $(i,j_i)$ for $i=1,\ldots,k$.

Other points of view. If you take $y_i$ to be the index of the horizontal step to $(i,j_i)$ among all steps (which are numbered from $1$ to $n+k$), you'll get your $0<y_1<\cdots<y_k\leq n+k$. If you put a candy (star) at each point $(i,j)$ of the path and think of each horizontal step as a separation (bar), you'll have split your $n+k+1$ candies into $k+1$ vertical groups (for $i=0,1,\ldots,k$) the last group $i=k$ being the left-overs. But actually you want each group to have as many candies as it has vertical steps, not points, so you remove one from each group to correct this fencepost error, leaving groups of vertical steps of sizes $d_0,d_1,\ldots,d_k$ (each $d_i\geq0$), with $d_0+\cdots+d_k=n$. In the end you might just as well take $n+k$ steps, choose $k$ of them to be horizontal (bars) and the remaining $n$ to be vertical (stars). But I think I already said something similar at the beginning.