Number of k-tuples such that $1 \le i_1 \le i_2 \le ... \le i_k \le N$ How many k-tuples $(i_1, \ i_2, \ \dots,\  i_k)$ exist such that $1 \le i_1 \le i_2 \le \dots \le i_k \le N$ where $N$ is a constant in $\mathbb{N}$ and $i_j \in \mathbb{N} \ \ \forall j \in [1,k]$
 A: Notice that the number of $k$-tuples $(i_1,i_2,\dots,i_k)$ satisfying $1\leq i_a\leq i_b\leq N$ for all $a\leq b$ are in direct bijection with lattice paths from $(1,1)$ to $(k+1,N)$ using only ups and rights as available movements.
The natural bijection being, $i_j = \max(n~:~(j,n)\in P)_n$ for each $j$ where $P$ is the path in question.
How many such lattice paths exist?
Hint:

There will be a total of $k$ rights and a total of $N-1$ ups used.  Pick when the ups occur.

Answer:

 $\binom{N+k-1}{N-1}$


Alternately, consider the related $k+1$-tuple, $(d_1,d_2,d_3,\dots,d_{k+1})$, where $d_j:=\begin{cases}i_1-1&\text{if}~j=1\\N-i_{k}&\text{if}~j=k+1\\
i_j-i_{j-1}&\text{otherwise}\end{cases}$
Notice that $0\leq d_j\in\mathbb{Z}$ for each $j$ and that $d_1+d_2+\dots+d_{k+1}=N-1$.
Notice further that these $(k+1)$-tuples are in direct bijection with the $k$-tuples in the original wording of the question.
Find the number of non-negative integral solutions to the above system.

This is a known problem format, with answer $\binom{k+1-1+N-1}{N-1} = \binom{N+k-1}{N-1}$, same as before.

A: It comes to the same as finding $k$-tuples $\langle j_1,\dots,j_k\rangle$ with $1\leq j_1<\cdots<j_k\leq N+k-1$. 
This under the correspondence $j_m=i_m+m-1$ for $m=1,\dots,k$.
These tuples on their turn correspond with subsets $\{j_1,\dots,j_k\}\subseteq\{1,\dots,N+k-1\}$.
So to be found is the number of subsets of $\{1,\dots,N+k-1\}$ that have cardinality $k$.
Can you do that yourself?
A: Let $x_j$ be the number of times digit $j$ is selected, for $1\le j\le N$.
Since the order of the digits is determined by the digits selected,
the number of such sequences is given by the number of solutions in nonnegative integers of 
$\;\;\;x_1+\cdots +x_N=k,\;\;$ which is $\dbinom{N-1+k}{k}$.
A: An alternate way to look at this problem: Finding out the number of required k-tuples is as good as finding out the number of k-multisets of [$n$] (e.g. $\{1,1,2,2,2,3\}$ is a 6-multiset of [$3$]). This is the Dot-Bar problem of arranging $n$ dots and $k$ bars, where the $i^{th}$ bar represents the $i^{th}$ component of the k-multiset and number of dots appearing before that bar represents the value assigned to that component. For instance, $\{1,1,2,2,2,3\}$ is represented as $.||.|||.|$ So as to always get a positive component in the required k-multiset, we exclude the left most dot and then arrange the remaining $n-1$ dots and $k$ bars. And the number of ways to do so is $\frac{(n+k-1)!}{k!(n-1)!}$ which is precisely ${n+k-1 \choose k}$.
