How to count different card combinations with isomorphism?
Solution 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.)
Solution 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.$$