Article 7Z74 Main |
| by Richard Pavlicek |

Combinatorial analysis is sometimes easy with the standard formulas available. For example, the number of permutations of N items is simply N! (N factorial). If any of the items (S) are the same, you simply divide by S! to get the answer without grief. Similarly, the number of combinations (selections without regard to order) of N items taken R at a time is easily found with N!/R!(N-R)!.

Unfortunately, it ceases to be easy when you consider combinations where some items are alike, or partitioning items into groups. Formulas do exist for many situations, but sometimes they are too complicated to be useful. In other words, it would often be quicker to solve the problem directly by computer than try to set up and solve the formulas. At least that’s my take on it, having a good knowledge of practical math but generally lost in areas like calculus.

Article 7Z74 Main | Top A Combinatorial Problem |

Consider the following problem:

If the spot cards (9-2) in each suit are considered equal, how many different deals exist? |

In other words, in each suit only the honors (A-10) are unique, and the eight lower ranks are like ‘x’ cards. The obvious answer is, “Who cares?” but the problem is intriguing. It is easy to determine the number of deals when all cards are unique: 52!/(13!)4, but now it becomes a daunting task with no available formula, or at least none that I could devise. To find the answer, I took advantage of one of my previous silly ventures — counting dealprints — and a little brute force by computer.

First, consider the problem of partitioning the five honors of one suit into four hands. The following table shows the ways this can be done. (The total can be verified by formula as the number of ways to distribute five items into four groups = 4^{5} = 1024.)

Distribution | Combinations | Permutations | Total |
---|---|---|---|

5-0-0-0 | 1 | 4 | 4 |

4-1-0-0 | 5 | 12 | 60 |

3-2-0-0 | 10 | 12 | 120 |

3-1-1-0 | 20 | 12 | 240 |

2-2-1-0 | 30 | 12 | 360 |

2-1-1-1 | 60 | 4 | 240 |

Totals: | 116 | 56 | 1024 |

To explain the calculations, consider the case when the honors are distributed 3-1-1-0. The three honors can be chosen in 10 ways (5c3), the next honor can be chosen in 2 ways (2c1), then the last honor is forced. This means there are 10 × 2 = 20 combinations for each specific distribution. Since the pattern 3-1-1-0 has 12 permutations, there are 20 × 12 = 240 total combinations. The other cases are determined similarly.

The next step is to determine how many of the above 1024 combinations will fit into each of the 39 generic suit distributions. For instance, if a suit is divided 4-4-3-2, it is obvious that none of the 5-0-0-0 combinations are possible since you can’t put five cards in one hand. Further, it is necessary to check each permutation separately since a suit divided, say, 5-4-3-1 will accept only half of the 4-1-0-0 combinations. This produced the following table.

Pattern | Comb. | Pattern | Comb. | Pattern | Comb. |
---|---|---|---|---|---|

4-3-3-3 | 975 | 6-5-1-1 | 352 | 8-4-1-0 | 111 |

4-4-3-2 | 900 | 6-5-2-0 | 192 | 8-5-0-0 | 32 |

4-4-4-1 | 645 | 6-6-1-0 | 112 | 9-2-1-1 | 266 |

5-3-3-2 | 886 | 7-2-2-2 | 706 | 9-2-2-0 | 141 |

5-4-2-2 | 811 | 7-3-2-1 | 536 | 9-3-1-0 | 101 |

5-4-3-1 | 631 | 7-3-3-0 | 221 | 9-4-0-0 | 31 |

5-4-4-0 | 241 | 7-4-1-1 | 351 | 10-1-1-1 | 136 |

5-5-2-1 | 552 | 7-4-2-0 | 191 | 10-2-1-0 | 71 |

5-5-3-0 | 232 | 7-5-1-0 | 112 | 10-3-0-0 | 26 |

6-3-2-2 | 796 | 7-6-0-0 | 32 | 11-1-1-0 | 31 |

6-3-3-1 | 616 | 8-2-2-1 | 456 | 11-2-0-0 | 16 |

6-4-2-1 | 551 | 8-3-1-1 | 336 | 12-1-0-0 | 6 |

6-4-3-0 | 231 | 8-3-2-0 | 181 | 13-0-0-0 | 1 |

What the above table shows is the number of ways the five honors can be distributed for each suit distribution. For example, for every 4-4-3-2 suit pattern, there are 900 ways to distribute the honor cards. The eight spot cards would simply fill the remaining spaces, but these are indistinguishable per the conditions of the problem.

All that remains is, for each specific dealprint, to look up the four suit patterns in the above table and multiply the corresponding factors to determine the number of possible deals for that dealprint; then add the totals for all the dealprints. Considering there are 37,478,624 specific dealprints, this still represents a formidable task. Fortunately, it’s a piece of cake for a computer. It took a few hours to write and debug the program, but once run it returned the answer in about 15 seconds:

800,827,437,699,287,808

So, there are over 800 quadrillion different deals if the spot cards (2-9) in each suit are considered equal. This may seem like a lot, and it certainly is, but it’s minuscule in comparison to the 53+ octillion possible bridge deals.

Article 7Z74 Main | Top A Combinatorial Problem |

This problem can be generalized for any number of unique cards in each suit, as summarized by the following table. The “Suit Makeup” shows the appearance of each suit, assuming the unique cards are designated from the top.

Unique | Suit Makeup | Number of Deals |
---|---|---|

0 | xxxxxxxxxxxxx | 37,478,624 |

1 | Axxxxxxxxxxxx | 4,997,094,488 |

2 | AKxxxxxxxxxxx | 630,343,600,320 |

3 | AKQxxxxxxxxxx | 74,424,657,938,928 |

4 | AKQJxxxxxxxxx | 8,110,864,720,503,360 |

5 | AKQJTxxxxxxxx | 800,827,437,699,287,808 |

6 | AKQJT9xxxxxxx | 69,848,690,581,204,198,656 |

7 | AKQJT98xxxxxx | 5,197,480,921,767,366,548,160 |

8 | AKQJT987xxxxx | 314,174,475,847,313,213,527,680 |

9 | AKQJT9876xxxx | 14,369,217,850,047,151,709,620,800 |

10 | AKQJT98765xxx | 445,905,120,201,773,774,566,940,160 |

11 | AKQJT987654xx | 7,811,544,503,918,790,990,995,915,520 |

12 | AKQJT9876543x | 53,644,737,765,488,792,839,237,440,000 |

13 | AKQJT98,765,432 | 53,644,737,765,488,792,839,237,440,000 |

Observe that with no unique cards (top row), the number of deals is equal to the number of specific dealprints. Also note that there is no difference between 12 and 13 unique cards; in either case it produces the full amount of deals. This is obvious if you think about it, since with only one ‘x’ card, all cards are effectively unique.

Now, if someone can show me a formula where I can plug in, say, 7 as the number of unique cards (and other appropriate values like 52, 13 and 4) to produce the answer 5197480921767366548160, I’ll really be impressed.

Article 7Z74 Main | Top A Combinatorial Problem |

© 2003 Richard Pavlicek