# In the game of roulette there are 36 numbers that the ball may land on, other than the Zero.

In the game of roulette, there are a few known (and playable) number pairs of 18 numbers each. The black/red, the even/odd, and the high/low numbers are known. But how many combinations of 18 different number sets are there? (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,and 18 would be the same as 18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2 and 1 because the opposite set would be composed of 19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35 and 36.). How would one go about to actually make the list, after the number of sets are known?

-
Perhaps your textbook has a discussion of "combinations". Or, if this is not a course question, look for that on-line. – GEdgar Jan 7 '13 at 14:54
There are ${36\choose 18}=9,075,135,300$ subsets of size $18$. A simple backtracking can be used to enumerate them all. – Hagen von Eitzen Jan 7 '13 at 14:57

You'll need lots of paper; there are more than 4½ billion such partitions.

Once you've stocked up on pen and paper, decide that the first of the two sets will always be the one that contains 1. First write down all combinations where 2 is in the first set; then write down all combinations where 2 is in the second set; then you're done.

The first part of this can again be split into the ones where 3 is in the first set (with 1 and 2), and ones where 3 is in the second set. Continue by divide-and-conquer.

The base case of the recursion is when you have already decided on 18 numbers to go in one set or the other. Then there's only one way to place the remaining number, and the sublist you're writing has length 1.

The first few sets generated become

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 21
...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 36
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 21
...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 36
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 19 20
...
1 2 20 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
1 2 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
...

-

You have to choose 18 numbers out of a set of 36; the number of ways to do so is $\binom{36}{18}$, or 36 choose 18. This is equal to $\frac{36!}{18!18!}$, which is equal to 9075135300. If odd/even is considered the same as even/odd, we divide by 2 to get 4537567650.

-