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?
Best Answer
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.