## Saturday, November 10, 2007

### 4D combinations

Ok. You see the number plate flashes by, and the gambler in you immediately wonders how many permutations of 4D can you buy with that 6 digit combinations - 378953.

Easy. It's 6P4 ( order matters here), and then to account for the double occurence of 3, we divide by 2. 6P4 being 360, the answer is 180.

Right? Wrong. Though the actual answer, 192, is close, the thought process is more tedious than is first suspected. What's more, should any of the 12 more numbers which you miss out strike top prize, you will be left cursing your high school math teacher.

Let's examine what happens with 6P4. It's fundamentally similar to 6C4 (where ordering does not count), and then multiply by 4! ways of reordering the 4 numbers you choose.

6C4 = 15. Let's list down all 15 cases.
Since there are 2 occurence of 3, I shall denote them by 3 and 3.

7895
3789
3895
3795
3785
3789
3895
3795
3785
3378
3379
3375
3389
3385
3395

Let's denote the 15 occurences into 3 groups:
Group 1: No occurence of 3.
Only 7895 here.
4C4 x 4! = 1 x 24 = 24 ways

Group 2: 1 occurence of 3.
8 groups here, but since 3 and 3 are similar, we shall deal only with 4 groups.
4 groups, in which there are 4! ways to order each group:
4C3 x 4! = 4 x 24 = 96 ways

*why 4C3? Since 3 is already selected, we have 4 more numbers 7,8,9,5 vying for 3 places.

Group 3: 2 occurence of 3.
6 groups here.
Since the 3 and 3 are similar, it is no longer 4! to order with each group.
(Remember, 3378 and 3378 are exactly similar.) We do 4!/2! = 12 ways.
4C2 x 4!/2! = 6 x 12 = 72 ways.

*Why 4C2? Since 33 is already selected, we have 4 more numbers 7,8,9,5 vying for 2 places.

Total number of ways = 24 + 96 + 72 = 192 ways.

What if now the 6 sets of numbers is changed to 337789?

We have to split our tasks into 9 groups:(think of trinary system 3^2).
Luckily for us, some groups are mathematically impossible.

Total number of ways = 78 ways.

Imagine if you had used 6P4, and then divide by 2(to account for 3 presumably) and then divide by 2 again (to account for 7), ending up with 360/2/2 = 90. With more careful math, you can actually save yourself from buying 12 repeat combinations!