Counting card distributions when cards are duplicated - MathOverflow

Counting card distributions when cards are duplicated

2011-02-17T16:27:59Z

If we have a deck of 48 different cards and 4 players each get 12 cards, it is well known how to calculate the number of possible distributions: take fac(48) and divide 4 times by fac(12).

In a german card came (Doppelkopf) there are 24 different card types, but 2 copies of each type, that is 48 cards at all.

How many distributions when there are 4 players? My first approach was to assume there are 48 different cards, and then to divide by 2 and by 2 (... 24 times). But this underestimates the real number of distributions. Because: Say player 1 has both spade kings. This has been ruled out already by dividing by fak(12). But if player 1 and player 2 both have a spade king, then we must divide by 2.

How to calculate the number of different distibutions?

Is there a closed formula as in the single card deck case?

Answer by Tony Huynh for Counting card distributions when cards are duplicated

2011-02-18T16:40:13Z

Label the players as 1,2,3, and 4. We first count the total possible number of hands that 1 can be dealt. Let $a$ be the number of singletons 1 has and let $b$ be the number of duplicates 1 has. This yields a total number of

$$\sum \binom{24}{a} \binom{24-a}{b}$$ possibilities, where the sum ranges over all $a$ and $b$ such that $a+2b=12$.

We now count the total number of possibilities for 1 and 2 (by conditioning on what 1 has first). We let $c$ denote the number of singletons that both 1 and 2 have. We let $d$ denote the number of singletons that 2 has but 1 does not have. Finally we let $e$ denote the number of duplicates that 2 has. Then the total number of possibilites for $1$ and $2$ is

$$\sum \binom{24}{a} \binom{24-a}{b} \binom{a}{c} \binom{24-a-b}{d} \binom{24-a-b-d}{e}$$

possibilities, where the sum ranges over all $a, b,c,d, e$ such that $a+2b=12$, $c \leq a$, and $c+d+2e=12$.

We end by computing the total number of possibilities for 1,2, and 3. This actually gives all possibilities since then the hand for player 4 is determined. Let $f$ and $g$ denote the number of singletons and duplicates for 3 respectively. The total answer is then

$$\sum \binom{24}{a} \binom{24-a}{b} \binom{a}{c} \binom{24-a-b}{d} \binom{24-a-b-d}{e} \binom{24-a-b-d-e}{g}\binom{24-b-c-e-g}{f}$$

where the sum ranges over all $a, b,c,d, e, f$ and $g$ such that $a+2b=12$, $c \leq a$, $c+d+2e=12$, and $f+2g=12$.

Answer by Ira Gessel for Counting card distributions when cards are duplicated

2011-02-18T17:40:33Z

The problem may be described as counted ordered partitions of the multiset ${1^2, \dots, 24^2}$ into 4 blocks, with 12 elements in each block. Equivalently, it's the problem of counting 4 by 24 nonnegative integer matrices in which every row sum is 12 and every column sum is 2.

One way to solve this problem is using symmetric functions. The complete symmetric function $h_n$ is defined to be $\sum_{i_1\le i_2\le \dots \le i_n} x_{i_1}x_{i_2}\dots x_{i_n}$. It's not hard to see that what we want is the coefficient of $x_1^2 x_2^2\cdots x_{24}^2$ in $h_{12}^4$: if we weight card $i$ by $x_i$ then $h_{12}^4$ counts all ways of giving 12 cards to each of 4 players, with unrestricted repetitions; extracting the coefficient of $x_1^2 x_2^2\cdots x_{24}^2$ gives those distribution in which each card appears twice.

Using basic facts about symmetric functions (see, for example, Macdonald's Symmetric Functions and Hall Polynomials or Stanley's Enumerative Combinatorics, Vol. 2, Chapter 7) we can express this coefficient as the scalar product $\langle h_2^{24}, h_{12}^{4}\rangle$. The easiest way to do the calculation is by using John Stembridge's SF package for Maple (http://www.math.lsa.umich.edu/~jrs/maple.html), which gives the answer 2248575441654260591964. (The calculation is much quicker if we first express $h_{12}$ in terms of power sums and then delete all terms containing $p_i$ for $i>2$.)

Here's another way to describe this calculation without using scalar products of symmetric functions. We first express $h_{12}$ in terms of the power sum symmetric functions $p_m = \sum_i x_i^m$, using a well-known formula. Since the terms we want have no powers of any variable higher than the second, we can ignore all $p_m$ with $m>2$, so the relevant part of $h_{12}$ is $$\sum_{j=0}^6 \frac{p_1^{12-2j}p_2^j}{2^j j! (12-2j)!}.$$ We expand the fourth power of this sum and then extract the coefficient of $x_1^2 x_2^2\cdots x_{24}^2$, using the fact that the coefficient of $x_1^2\cdots x_m^2$ in $p_1^{2i} p_2^j$, where $i+j=m$, is $m! {(2i)!}/(2^i i!)$.

Answer by Zsbán Ambrus for Counting card distributions when cards are duplicated

2011-02-20T10:55:10Z

While you've already got a good answer, let me offer a worse one.

Take a random deal of the cards (12 to each player), and let X be the number of card faces whose two cards go to different players. The expected value of $ (48!/12!^4)\cdot2^{-X} $ is then equal to the number of different deals. You can thus use a Monte-Carlo method to estimate this number: you just generate lots of random deals and take the average of that random variable.

I've tried to run a quick and dirty simulation, and got $ 2.25\cdot10^{21} $ as the result, but I didn't verify the code, so the result could be completely wrong (but at least it agrees with Ira Gessel's figure above).

Answer by Douglas Zare for Counting card distributions when cards are duplicated

2011-02-20T23:58:15Z

Here is an elementary approach which works. It is based on Tony Huynh's method of dealing out the hands one at a time, but using transition matrices/dynamic programming instead of sums.

Let the state of the deck be $(p,s)$ where $p$ is the number of pairs it contains and $s$ is the number of singletons. Dealing out a hand changes the state of the deck, e.g., from the starting deck $(24,0)$ we can go to $7$ possible states: $(18,0),$ $(17,2)$, ..., $(12,12)$.

The number of ways to go from $(p_1,s_1)$ to $(p_2,s_2)$ by dealing one hand only depends on the labels, and is a single sum over the number of pairs $r$ in the new hand: $\sum_r {p_1 \choose r,p_2,p_1-r-p_2}{s_1 \choose 12-r-p_1+p_2}.$

This gives us transition matrices which are $1\times 7$, $7\times 13$, $13 \times 7$, and $7 \times 1$, whose product in the proper order, as a scalar, is the number of distinct deals, $2248575441654260591964$.

Here is some Mathematica code which implements this:

transitions[p1_, s1_, p2_, s2_] := 
   Sum[Multinomial[r, p2, p1-p2-r] Binomial[s1, 12+p2-r-p1], {r,0, p1-p2}]
M1 = Table[transitions[24-i, 2i, 18-j, 2j], {i, 0, 0}, {j, 0, 6}]
M2 = Table[transitions[18-i, 2i, 12-j, 2j], {i, 0, 6}, {j, 0, 12}] 
M3 = Table[transitions[12-i, 2i, 6-j, 2j], {i, 0, 12}, {j, 0, 6}]
M4 = Table[transitions[6-i, 2i, 0-j, 2j], {i, 0, 6}, {j, 0, 0}] 
(M1.M2.M3.M4)[[1, 1]]

Final output:

2248575441654260591964