Main     Article 7Z74 by Richard Pavlicek    

A Combinatorial Problem

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.

TopMain

All Spots Created Equal

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.)

DistributionCombinationsPermutationsTotal
5-0-0-0144
4-1-0-051260
3-2-0-01012120
3-1-1-02012240
2-2-1-03012360
2-1-1-1604240
Totals:116561024

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.

PatternComb.PatternComb.PatternComb.
4-3-3-39756-5-1-13528-4-1-0111
4-4-3-29006-5-2-01928-5-0-032
4-4-4-16456-6-1-01129-2-1-1266
5-3-3-28867-2-2-27069-2-2-0141
5-4-2-28117-3-2-15369-3-1-0101
5-4-3-16317-3-3-02219-4-0-031
5-4-4-02417-4-1-135110-1-1-1136
5-5-2-15527-4-2-019110-2-1-071
5-5-3-02327-5-1-011210-3-0-026
6-3-2-27967-6-0-03211-1-1-031
6-3-3-16168-2-2-145611-2-0-016
6-4-2-15518-3-1-133612-1-0-06
6-4-3-02318-3-2-018113-0-0-01

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.

TopMain

Generalized Case

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.

UniqueSuit MakeupNumber of Deals
0xxxxxxxxxxxxx37478624
1Axxxxxxxxxxxx4997094488
2AKxxxxxxxxxxx630343600320
3AKQxxxxxxxxxx74424657938928
4AKQJxxxxxxxxx8110864720503360
5AKQJTxxxxxxxx800827437699287808
6AKQJT9xxxxxxx69848690581204198656
7AKQJT98xxxxxx5197480921767366548160
8AKQJT987xxxxx314174475847313213527680
9AKQJT9876xxxx14369217850047151709620800
10AKQJT98765xxx445905120201773774566940160
11AKQJT987654xx7811544503918790990995915520
12AKQJT9876543x53644737765488792839237440000
13AKQJT9876543253644737765488792839237440000

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.

TopMain

© 2003 Richard Pavlicek