0
$\begingroup$

There is a card game that I have been playing lately which can be played with a deck of only $15$ cards. There are exactly $3$ of each type of card, so there are $5$ types of cards. Cards of the same type should be considered completely indistinguishable from eachother (ie, any notion of 'suit' or the like is not relevant if the deck were to utilize normal playing cards).

If believe that this means that the number of ways that the deck can be initially shuffled therefore is $$ \frac{15!}{{3!}^5} $$ This works out to be $168,168,000$ ways that the deck can be shuffled.

I am wondering, however, how many different ways this game could be initially dealt for a given number of players. Each player is dealt only $2$ cards, and the number of players is limited to $5$, so there will always be left over cards where the order of them does not contribute to the initial deal. Further, the order of the two cards in each player's initial deal does not matter either.

How would I go about calculating the number of possible initial deals for $n$ players?

$\endgroup$
  • $\begingroup$ Are the players distinguished from each other? For instance, is Player 1 getting A and B, and Player 2 getting C and D, to be distinguished from Player 1 getting C and D, and Player 2 getting A and B? $\endgroup$ – Brian Tung Sep 26 '15 at 1:41
  • $\begingroup$ Although once the game starts, the order of the players matters with respect to the cards each person has, it's not really relevant during the initial deal. So for the time being, assume not. $\endgroup$ – Mark Sep 26 '15 at 2:50
  • $\begingroup$ I assume that the order of the cards within a hand doesn't matter (i.e. getting A then B is the same as getting B then A.) So the group ${\Mathbb{Z}_2}^n$ acts on the sequence of cards dealt, and we want to count orbits, so we probably want to use Burnside's lemma. $\endgroup$ – Tad Sep 26 '15 at 12:48
  • $\begingroup$ You are right that the order of the cards within a hand does not matter, and I ask that you please excuse my ignorance here, but I am afraid that the remainder of your comment reads like greek to me. $\endgroup$ – Mark Sep 26 '15 at 18:19
1
$\begingroup$

A fairly practical solution can be derived using generating functions. Suppose we have $m$ types of cards, with $k$ cards of each type. We have $p$ players; each player gets $c$ cards in her hand.

We start by identifying all ways the players could receive cards of the first type. If player $i$ gets $a_i$ cards of that type, we have $\sum_i a_i \le k$ and $\max a_i \le c$, and any such vector can arise. So define $$g(x_1,\ldots,x_p) = \sum x_1^{a_1} x_2^{a_2}\cdots x_p^{a_p}$$ where the sum ranges over nonnegative $(a_1,\ldots,a_p)$ with $\sum a_i\le k$ and $\max a_i\le c$. For example, with $k=3$ cards per type, $c=2$ cards per hand, and $p=2$ players, we have $$g(x_1,x_2)=x_2 x_1{}^2+x_1{}^2+x_2{}^2 x_1+x_2 x_1+x_1+x_2{}^2+x_2+1.$$

The same count applies to each type, so the coefficient of $x_1^{a_1}\cdots x_p^{a_p}$ in $g^m$ counts the number of ways to distribute cards from the deck so that player $i$ gets $a_i$ cards total. Thus the desired count is the coefficient of $x_1^c\cdots x_p^c$ in $g^m$.

For $m=5$ types, $k=3$ cards per type, and $c=2$ cards per hand, we get the following values:

\begin{array}{rc} p & \textrm{Number of deals}\\ \hline 1 & 15 \\ 2 & 220 \\ 3 & 2920 \\ 4 & 32490 \\ 5 & 273510 \\ 6 & 1469700 \\ 7 & 3429300 \\ \ge8 & 0 \end{array}

Here is Mathematica code:

Needs["Combinatorica`"];
g[k_, p_, c_] := 
  With[{X = x /@ Range[p]}, 
   Plus @@ (Times @@ (X^#) & /@ 
      Select[Join @@ (Compositions[#, p] & /@ Range[0, k]), 
       Max[#] <= c &])];
f[m_, k_, p_, c_] := With[{X = x /@ Range[p]},
  Coefficient[Expand[g[k, p, c]^m], Times @@ X^c]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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