Article 7Z74   Main

A Combinatorial Problem

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

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⁵ = 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

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.

Unique	Suit Makeup	Number of Deals
0	xxxxxxxxxxxxx	37478624
1	Axxxxxxxxxxxx	4997094488
2	AKxxxxxxxxxxx	630343600320
3	AKQxxxxxxxxxx	74424657938928
4	AKQJxxxxxxxxx	8110864720503360
5	AKQJTxxxxxxxx	800827437699287808
6	AKQJT9xxxxxxx	69848690581204198656
7	AKQJT98xxxxxx	5197480921767366548160
8	AKQJT987xxxxx	314174475847313213527680
9	AKQJT9876xxxx	14369217850047151709620800
10	AKQJT98765xxx	445905120201773774566940160
11	AKQJT987654xx	7811544503918790990995915520
12	AKQJT9876543x	53644737765488792839237440000
13	AKQJT98765432	53644737765488792839237440000

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