Q:

calculating lottery odds for non-descending order

This is part of a TopCoder.com algorithm practice question and I cannot wrap my head around it. I am given a lottery format and I need to calculate the odds. One particular format is that the numbers must be in non-descending order. The numbers do not have to be unique, so I can repeat the same number.
Example:
The "PICK TWO FROM TEN IN ORDER" game means that the first number cannot be greater than the second number. This eliminates 45 possible tickets, leaving us with 55 valid ones. The odds of winning are 1/55.
How do I calculate this?

A:

Since each unordered pair of different numbers can be ordered in two different ways, the number of eliminated tickets is half the number of ordered pairs of different numbers. To count the ordered pairs of different numbers, note that to form such a pair you can first choose one of $n$ numbers, then you can choose one of the remaining $n-1$ numbers. Thus there are $n(n-1)$ such pairs, and half as many eliminated tickets, $n(n-1)/2$.
[Edit:]
That answer only applies to the case of two numbers. For $k$ non-decreasing numbers out of $n$, think of the numbers as making $n-1$ upward steps from $1$ to $n$. You want to combine these $n-1$ small steps into $k+1$ big steps, one before the first number, $k-1$ from one number to the next and one after the last number. The number of ways to distribute $n-1$ small steps over $k+1$ big steps is
$$\binom{(n-1)+(k+1)-1}{(k+1) - 1}=\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!(n-1)!}=\frac{n(n+1)\cdots(n+k-1)}{1\cdot2\cdots(k-1)k}\;.$$

