How to count different card combinations with isomorphism?

Question

Let's consider a standard deck of cards and say that two sets of cards are isomorphic if there exists permutation of colors that makes one set into another.

For example: A♡ K♡ K♧ is isomorphic with A♤ K♤ K♡, but not than A♢ K♤ K♧

Now we can count that there are 1326 different pair of cards, but when considering the color isomorphisms there are only 169 of them.

Is there a generic formula or approach to calculate it for any problem size (number of ranks(AKQ..), colors(♢♡♧♤...), and set size?

Answer 1

We have a set of colors $C$ and a set of numbers $N$. We act on $C \times N$ by the symmetric group $\mathrm{Sym}(C)$, with $(c,n) \overset{\alpha}{\mapsto} (\alpha(c),n)$ for all $\alpha \in \mathrm{Sym}(C)$ and $(c,n) \in C \times N$. This induces an action on the set of $k$-subsets of $C \times N$.

The number of isomorphism classes is given by Burnside's Lemma. In this case, if $\alpha,\beta \in \mathrm{Sym}(C)$ have the same cycle structure, then $\alpha$ and $\beta$ stabilize the same number of elements in $C \times N$.

So the number or isomorphism classes is $$\frac{1}{|C|!} \sum_{\text{partitions $P$ of |C|}} \text{nr permutations with cycle structure } P \times |\mathrm{Stab}(\rho)|$$ where $\rho$ denotes a representative permutation with cycle structure $P$. Here $\mathrm{Stab}(\rho)$ is the set of $k$-subsets of $C \times N$ which are fixed by acting on them with $\rho$.

The number of permutations with a given cycle structure is $$\frac{|C|!}{\prod_{i \geq 1} s(i)!\ i^{s(i)} }$$ where $s(i)$ is the number of $i$-cycles in the cycle structure.

Calculating $|\mathrm{Stab}(\rho)|$ is trickier. It might be that any formula for $|\mathrm{Stab}(\rho)|$ is essentially "compute $|\mathrm{Stab}(\rho)|$" in disguise. If the color $b$ belongs to a $t$-cycle in $\rho$, then we either have all of $(b,n),(\rho(b),n),\ldots,(\rho^{t-1}(b),n)$ in the $k$-subset, or we have none of these.

In the $C=\{1,2,3,4\}$, $N=\{1,2,\ldots,13\}$, and $k=2$ case, we have these representative permutations:

• $\mathrm{id}$: This fixes everything, so $|\mathrm{Stab}(\mathrm{id})|=\binom{4 \times 13}{2}=1326$.
• $(12)$: We fix any subset that doesn't have the color $1$ or $2$, of which there are $\binom{2 \times 13}{2}=325$, and if the subset has $(c,n)$ where $c \in \{1,2\}$ then it has both $(1,n)$ and $(2,n)$, giving $13$ more possibilities. So $|\mathrm{Stab}(12)|=338$.
• $(12)(34)$: Similar the above case, we either have $\{(1,n),(2,n)\}$ or $\{(3,n),(4,n)\}$, so we have $|\mathrm{Stab}(12)(34)|=26$.
• $(123)$: We can't use the colors $1$, $2$ or $3$, otherwise $(1,n)$, $(2,n)$, and $(3,n)$ would be in our $2$-subset, giving a contradiction, so the subset is $\{(4,n),(4,n')\}$ for two distinct $n,n' \in N$. So $|\mathrm{Stab}(12)|=\binom{13}{2}=78$.
• $(1234)$: Similar to the above case, we have $|\mathrm{Stab}(1234)|=0$.

Hence the number of isomorphism classes is $$\frac{1}{4!}(1 \times 1326+6 \times 338+3 \times 26+8 \times 78+6 \times 0)=169.$$

(I don't think this number "comes from" $13 \times 13$ though.)

Answer 2

In this post we will show how to compute the number of non-isomorphic $k$-subsets for all $k$ where $0\le k\le 52.$ What we have here is a Power Group Enumeration problem (in the sense of the term as described by Harary in Graphical Enumeration and also by Fripertinger in Enumeration in Musical Theory), with the group acting on the slots where the cards are placed being the symmetric group $S_N$ on $N$ elements and the group acting on the cards being the permutation group $Q$ with $24$ elements obtained by permuting suits / colors.

For the cycle index $Z(Q)$ observe that since suit permutation never changes the values of the cards we have that cards with the same value replicate the cycle structure of the cycles from $Z(S_4)$ that act on the four suits. This means the cycles from the latter are repeated $13$ times, once for each face value, and we get

$$Z(Q) = \left.Z(S_4)\right|_{a_1=a_1^{13}, a_2=a_2^{13}, a_3=a_3^{13}, a_4=a_4^{13}}$$

which is $$Z(Q) = 1/24\,{a_{{1}}}^{52}+1/4\,{a_{{1}}}^{26}{a_{{2}}}^{13} +1/3\,{a_{{1}}}^{13}{a_{{3}}}^{13} +1/8\,{a_{{2}}}^{26}+1/4\,{a_{{4}}}^{13}.$$

We can compute the number of configurations / subsets by Burnside's lemma which says to average the number of assignments fixed by the elements of the power group, which has $4!\times |S_N|$ elements and $|S_N|=N!$. But this number is easy to compute. Suppose we have a permutation $\alpha$ from $S_N$ and a permutation $\beta$ from $Q$. If we place the appropriate number of complete, directed and consecutive copies of a cycle from $\beta$ on a cycle from $\alpha$ then this assignment is fixed under the power group action, and this is possible iff the length of the cycle from $\beta$ divides the length of the cycle from $\alpha$ and there are as many assignments as the length of the cycle from $\beta$. There is an important observation to make here, however. We are only interested in sets and not in multisets. That means we cannot place multiple copies of a cycle from $\beta$ on a cycle from $\alpha$ as we would be repeating elements. Therefore the problem for pairs $(\alpha, \beta)$ reduces to computing the number of subsets of cycles from $\beta$ that we can place in their entirety on the cycles of $\alpha$ to cover all of $\alpha.$ Hence the multiset of cycle lengths of $\beta$ must be a superset of the cycle lengths from $\alpha$, containing at least as many cycles of length $k$ as $\alpha$ plus possibly some other cycles. It is therefore sufficient to iterate over the variables that appear in $\alpha,$ checking that they are present in $\beta$ with the same or higher degree and choosing cycles from the latter to cover the former. There is a multiplicative factor to account for the fact that the number of ways of covering a cycle is given by the length of the cycle that does the covering.

Now the Burnside computation is best done with a CAS, here is the Maple code. Note that it suffices to work with the cycle indices of the two groups which is lower complexity than iterating over all $N!$ permutations of $S_N.$

with(combinat);
with(numtheory);

pet_cycleind_symm :=
proc(n)
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_cards :=
proc()
    option remember;
    subs([seq(a[q]=a[q]^13, q=1..4)],
         pet_cycleind_symm(4));
end;

q :=
proc(N)
option remember;
local idx_slots, idx_cards, res, term_a, term_b,
    v_a, inst_a, inst_b, len_a, p;

    if N = 0 then return 1 fi;

    if N = 1 then
        idx_slots := [a[1]];
    else
        idx_slots := pet_cycleind_symm(N);
    fi;

    idx_cards := pet_cycleind_cards();

    res := 0;

    for term_a in idx_slots do
        for term_b in idx_cards do
            p := 1;

            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);
                inst_b := degree(term_b, v_a);

                if inst_b >= inst_a then
                    p := p*binomial(inst_b, inst_a)
                    *inst_a!*len_a^inst_a;
                else
                    p := 0;
                    break;
                fi;
            od;

            res := res +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    res;
end;

The above yields the complete list of the nonisomorphic subset count for the standard deck which is (observe that these can definitely not be computed by brute force and note the symmetry as well): $$1,13,169,1755,16432,134459,962988,6009159,32819436,\\ 157702259,671225412,2546958349,8668626707,26607292908,\\ 74002375408,187274148048,432761029519,915980606957,\\ 1780453974039,3185285527359,5254786194372,8006264748053,\\ 11280519244644,14712774203725,17777183437949,19909964116172,\\ 20675571474936,19909964116172,17777183437949,14712774203725,\\ 11280519244644,8006264748053,5254786194372,3185285527359,\\ 1780453974039,915980606957,432761029519,187274148048,\\ 74002375408,26607292908,8668626707,2546958349,671225412,\\ 157702259,32819436,6009159,962988,134459,16432,1755,169,13,1.$$

Answer 3

Once we have the Z(Q) we can apply the differential operator

$$ \frac {1} {2} \frac{\partial ^2 Z}{\partial a_1^2} + \frac{\partial Z}{\partial a_2}$$

and the resulting $Z^{x,x}(Q)$ is the cycle index of the combinatorial species obtained after the removal of a pair of cards among the 52.

$$Z^{x,x}(Q) = {221 \over 4} a_1^{50} + {325 \over 4} a_1^{24} a_2^{13} + {13 \over 4} a_1^{26} a_2^{12} + 26 . a_1^{11} a_3^{13} + {13 \over 4} a_2^{25} $$

The number of types is given by the sum of coefficients above,

$$169 = {221 \over 4} + {325 \over 4} + {13 \over 4} + 26 + {13 \over 4} $$

I found mentions of differential operators as far as N.G. de Bruijn, 1964, Applied Combinatorial Mathematics, editor Edwin Beckenbach, multiple authors.

How comes that a two dimensional situation given by the two sorts of ranks and suits is transformed in a "monosort" formula ? There is an article Maya/Mendez on the "arithmetic product of species" that touches the two-dimension context. Eventually, at the cycles level one has

$$a_m \times a_n = a_{gcd(m,n)}^{lcm(m,n)}$$