6
$\begingroup$

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: $\frac{48!}{12!12!12!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^{24}$. 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 $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?

$\endgroup$
5
  • 2
    $\begingroup$ OK, I see the problem, it's not an especially easy question. But it's not research-level and too localized, I doubt it will stay open. My guess is that you'll have better luck in one of the other sites mentioned in the FAQ. $\endgroup$ Feb 17, 2011 at 16:44
  • 3
    $\begingroup$ This sounds like a Polya necklace type of problem. You have 24 independent copies of $Z/2Z$ acting on your deck, so you first pretend all the cards are distinct, count as if that's the case, and then divvy up some different cases and divide out by the stabilizers of the different cases under the $(Z/2Z)^{24}$ action. In other words, as you said, sometimes you have to divide by 2 and sometimes you don't. $\endgroup$
    – aaron
    Feb 17, 2011 at 19:35
  • 1
    $\begingroup$ Pólya's enumeration theorem applies, but then you are left with $25$ enumeration problems. $\endgroup$ Feb 17, 2011 at 23:34
  • 1
    $\begingroup$ By the way, "is there a closed formula" is not at issue here. The real question is more: how simple can you get it to be? $\endgroup$ Feb 18, 2011 at 16:27
  • 2
    $\begingroup$ See also mathoverflow.net/questions/26788/… $\endgroup$
    – Charles
    Feb 18, 2011 at 18:36

4 Answers 4

10
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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
$\endgroup$
3
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ So, who's game to calculate this sum to see if you get the same number Ira Gessel got in his answer? $\endgroup$ Feb 18, 2011 at 21:46
  • $\begingroup$ OK, I might give this beast a try tomorrow when I sober up. However, it does seem to me that the number in Ira Gessel's answer is of the wrong order of magnitude. As noted, the actual number should be at least $48!/(4 \times 12! \times 2^{24}) \geq 3.86 \times 10^{44} >> 2248575441654260591964.$ $\endgroup$
    – Tony Huynh
    Feb 19, 2011 at 1:31
  • 2
    $\begingroup$ The lower bound should be $48!/(12!^4\cdot 2^{24})\approx 1.41\cdot10^{19}$ which is just a little less than my answer, which is $2.25\cdot10^{21} $. In fact, the lower bound is the term in the scalar product involving only $p_1$, $\langle (p_1^2/2)^{24}, (p_1^{12}/12!)^4\rangle$. $\endgroup$
    – Ira Gessel
    Feb 19, 2011 at 16:26
  • $\begingroup$ @Ira. You are right. Silly mistake by me. $\endgroup$
    – Tony Huynh
    Feb 19, 2011 at 17:10
  • $\begingroup$ Even rewriting the expression to eliminate a, f, and d or e is more than I am willing to do at present. That is where I would start, though. Gerhard "Ask Me About System Design" Paseman, 2011.02.20 $\endgroup$ Feb 20, 2011 at 18:01
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.