# number of combinations of ordered sequences of N integers

suppose a N-tuple of N integers, such that every element in the tuple is bigger than or equal to the last one and each element in the sequence ranges from 1 to K. Is there any closed formula for the number of combinations possible?

For those who think this is trivial, try to think about it for one minute. I have done so:

let $a_i \in \{1, 2, ..., K\}, i \in \{1..N\}$. We want to count the number of N-tuples $(a_1, a_2, ..., a_N)$ such that $a_i>=a_{i-1}$.

I know how to solve for $N=2$:

given $a_1 \in \{1, 2, ... K\}$, the number of possibilities for $a_2>=a_1$ is $K-a_1+1$. Thefore, the number of pairs $(a_1,a_2)$ is: $U=K+(K-1)+(K-2)+...+1$ which is easy to compute since it equals $K(K+1)/2$.

Now, how to generalize for N-tuples?

Line up $N$ balls. Then insert $K-1$ dividers. Let the number of balls to the left of the first divider be the number of $1$'s in your sequence. Let the number of balls between the first and second divider be the number of $2$'s in your sequence, and so on.
For example, with $N = 4$ and $K = 5$ "$\bullet |\bullet | | \bullet \bullet|$" represents one $1$, one $2$, no $3$'s two $4$'s, and no $5$'s i.e. the sequence $(1,2,4,4)$.
Each arrangement of $N$ balls and $K-1$ dividers yields a distinct sequence since the sequence is non-decreasing. Also, every such sequence can be formed this way. Therefore, by the rearrangement formula, there are $\dbinom{N+K-1}{N}$ such sequences.
Let $F(n,k)$ be the number of combinations of $n$ integers $\leq k$. Suppose the first number is $i$. The remaining numbers form an increasing sequence of integers in $[i,k]$, shifting we find that the number of possible chains equals $F(n-1,k-i+1)$. Hence $$F(n,k)=\sum_{i=1}^kF(n-1, k-i+1).$$ Such a recursion need not have a closed answer, so either one checks whether whatever one is trying to prove can be deduced from the recursion, or one starts guessing an answer. In this case computing $F(n,k)$ for small $n$ is easy, and the first values $k$, $\frac{k(k+1)}{2}$, $\frac{k(k+1)(k+2)}{6}$ as well as the obvious asymptotics $F(n,k)\sim\frac{k^n}{n!}$, valid for $n$ fixed and $k\rightarrow\infty$ lead you directly to binomial coefficients.