Richard Pavlicek's combinatorial problem

Question

In the game of bridge, a standard deck is dealt to four players, 13 cards each. That gives a total of $\binom{52}{13,13,13,13}$ distinct deals.

How many distinct deals can be dealt if all spot cards - $2$ through $9$ - are considered equal in rank (but retain their suits.)

This question originates on Richard Pavlicek's bridge site.

He asks a combinatorial question. I am also interested in a solution but unfortunately, I have no plan how the formula can be constructed.

Can anyone help ?

Answer 1

This problem can be solved by the Polya Enumeration Theorem. Ignore the no spot cards for the moment as they only contribute trivial symmetries. The setup here is that we have $8\times 4$ slots into which we distribute assignments to players $A,B,C$ and $D.$ We have the symmetric group $S_8$ acting on each block of spot cards from the same suit. This gives the cycle index $$Z(Q) =Z(S_8)^4.$$

It follows that the number of deals where player $A$ receives $a$ spot cards, player $B$ receives $b$ spot cards and so on is given by $$[A^a B^b C^c D^d] Z(S_8)^4(A+B+C+D).$$

If all four degrees are at most thirteen we can combine such an assignment with an assigment of the no spot cards of the remaining cards, which is given by a simple multinomial coefficient, for a contribution of $${20\choose 13-a,13-b,13-c,13-d} [A^a B^b C^c D^d] Z(S_8)^4(A+B+C+D).$$ It remains to sum these terms from $Z(Q)$ to get the answer, which is $$800827437699287808.$$

Observe that all of these terms have $a+b+c+d=32.$ Note also that the multinomial corresponds to multiplying $Z(Q)$ by $a_1^{20},$ representing twenty fixed points for the no spot cards which are not being permuted.

Here the computation features the recurrence by Lovasz for the cycle index $Z(S_n)$, which is $$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}) \quad\text{where}\quad Z(S_0) = 1.$$

This was the Maple code that I used.

with(combinat);
with(numtheory);


pet_cycleind_symm :=
proc(n)
local p, s;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_cycleind_idspots := pet_cycleind_symm(8)^4;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;

count :=
proc()
option remember;
    local sind, res, term, Ad, Bd, Cd, Dd;

    sind := pet_varinto_cind(A+B+C+D, pet_cycleind_idspots);
    res := 0;

    for term in expand(sind) do
        Ad := degree(term, A);
        Bd := degree(term, B);
        Cd := degree(term, C);
        Dd := degree(term, D);

        if Ad<=13 and Bd<=13 and Cd<=13 and Dd<= 13 then
            res := res + term/A^Ad/B^Bd/C^Cd/D^Dd*
            20!/(13-Ad)!/(13-Bd)!/(13-Cd)!/(13-Dd)!;
        fi;
    od;

    res;
end;

The output of the Maple program is as follows. The timing here was less than one tenth of a second.

> count();
memory used=37195.2MB, alloc=8.3MB, time=436.90
memory used=37197.7MB, alloc=8.3MB, time=436.94
                                  800827437699287808

This matches the value presented at the linked web site.

A somewhat more advanced computation involving suits being distributed is at this MSE link.

Answer 2

Yes, it can be helped, and the name is Bruijn (1964),

$P_H({\partial\over\partial z_1},{\partial\over\partial z_2}, {\partial\over\partial z_3},...) P_G (z_1, 2z_2,3z_3,...)$

the terminology saying the incomplete delabeling.

Following Bruijn, $P_H$ and $P_G$ are cycles indexes.

I will show the minimal example, by supposing that bridge is a game of two players, North and South, played with Aces, 9's and 8's of two colors, spade and heart.

Then $P_G$ is the cycle index of the species $Ens_3.Ens_3$ or the action of $S_6$ over hands (triplets of cards)

$P_G = {1\over 3!} (z_1^3 + 3z_1z_2 + 2z_3) . {1\over 3!} (z_1^3 + 3z_1z_2 + 2z_3)$

$P_H$ describes the system of labels to be applied in this one-to-one mapping context. AS (the ace of spade) and AH are fixed. 9S and 8S can swapped and also 9H and 8H. Then

$P_H = z_1^2{z_1^2+z_2 \over 2!}{z_1^2+z_2 \over 2!}$

After differentiation by Bruijn formula, the result is $10$, the number of patterns within respect with the original terminology.

Here are the ten hands

AS, AH, h

AS, AH, s

AS, h, h

AS, h, s

AS, s, s

AH, h, h

AH, h, s

AH, s, s

h, h, s

s, s, h