0
$\begingroup$

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?

  • 0
    See also http://math.stackexchange.com/questions/117835/how-many-sequence-of-integers-j-1-j-2-j-k-are-there-such-that-0.2012-03-15

2 Answers 2

2

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}\;.$

  • 0
    @Herman: No, it gets more complicated for more than two numbers, because "non-decreasing" and "decreasing" are no longer exhaustive possibilities; the numbers can go up and down, which they can't if there are only two of them. The number $n(n-1)\ldots(n-7)/8!$ (with a factorial, as Hurkyl pointed out) is the number of decreasing octuples, but this is not the complement of the number of non-decreasing octuples. I'll edit the answer to treat the general case.2012-03-12
0

If you are counting this over and over, you could do it with dynamic programming. Let $T[k][n] =$ how many times I can pick $k$ numbers in order out of $n$ total. Of course $T[1][n] = n$ and $T[k][k] = 1$. Then to count $T[k][n]$, pick the largest number $m$ and count the rest using $T$, i.e. $T[k][n] = \sum_m T[k-1][m-1]\,.$ If you have to calculate T for different $k$s, you can reuse your computations, and calculating the above formula this way is not that inefficient--the binomials you would need to calculate otherwise are also costly!