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.


The solutions using balls is very nice, however, it is not a solution one can come up without some experience in combinatorial counting. If you have that experience, then "Look for a bijection to something nicer" is a standard approach. If you lack experience, or don't find the bijection you want, quite often recursions work pretty well.

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.

Then you prove your conjectured formula by induction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.