Problem 369: Badugi

Detailed mathematical approach

Problem Summary

A standard deck holds \(52\) cards, one for every pair of a rank and a suit, with \(13\) ranks and \(4\) suits. A set of \(4\) cards is a Badugi if it has no pair — no two cards of one rank — and no two cards of one suit. Let \(f(n)\) be the number of ways to choose \(n\) cards of which some \(4\)-card subset is a Badugi. The statement notes that \(514800\) of the \(\binom{52}{5}=2598960\) five-card choices qualify, so \(f(5)=514800\), and asks for ^[1]

$$\sum_{n=4}^{13} f(n).$$

The whole solution in one sentence: read a hand as a bipartite graph joining ranks to suits, in which a Badugi is exactly a matching that uses all four suits, and count hands rank by rank while remembering nothing but which sets of suits the ranks seen so far can already match.

Mathematical Approach

1. A hand is a bipartite graph

Let \(S\) be the set of \(4\) suits. The deck holds one card per rank-and-suit pair, so a hand can be drawn as a bipartite graph: its vertices are the \(13\) ranks and the \(4\) suits, its edges the chosen cards. A Badugi is then a set of four edges no two of which share a vertex — a matching of size \(4\) — and with only four suits it touches every suit once. The question becomes: a hand contains a Badugi exactly when its graph has a matching covering all four suits. ^[2]

2. The smallest case

Fewer than four cards can never contain a Badugi, so \(f(n)=0\) for \(n\lt4\). A hand of exactly four cards contains one precisely when it is one: choose its four ranks in \(\binom{13}{4}=715\) ways, then match the four suits to them in \(4!=24\) ways, and no hand arises twice. Hence

$$f(4)=\binom{13}{4}\cdot 4!=715\cdot 24=17160.$$

3. Hall's condition

For \(A\subseteq S\) let \(N(A)\) be the set of ranks in which some suit of \(A\) holds a card. Hall's marriage theorem says a bipartite graph has a matching covering a whole side exactly when every subset \(A\) of it satisfies \(|N(A)|\ge|A|\). ^[3] Its negation gives a test we can run by hand: a hand contains no Badugi exactly when some set of suits has cards in fewer ranks than it has suits. For \(|A|=1,2,3,4\) that means one of these holds:

• some suit holds no card at all;
• the cards of some two suits occupy at most one rank;
• the cards of some three suits occupy at most two ranks;
• all four suits together occupy at most three ranks.

4. Worked example: \(f(5)\) by hand

Let a five-card hand contain a Badugi. Every suit holds a card by the first case, and the suit sizes add to \(5\), so they are \(2,1,1,1\) in some order: one suit \(X\) holds two cards, of ranks \(p\ne q\), the other three one card each, of ranks \(a\), \(b\), \(c\). The other cases become conditions on \(a,b,c\).

• Two suits in one rank: a pair containing \(X\) already reaches \(p\) and \(q\), so only two single-card suits can offend, and forbidding that makes \(a,b,c\) different.
• Three suits in two ranks: for the three single-card suits this asks \(|\{a,b,c\}|\ge3\), already true; for \(X\) with two of them it forbids \(\{a,b\}=\{p,q\}\) and its two analogues, so no two of \(a,b,c\) form the rank pair of \(X\).
• All four suits in three ranks: we need \(|\{p,q,a,b,c\}|\ge4\). Were \(p\) and \(q\) both among \(a,b,c\), two of those would form \(\{p,q\}\), just forbidden; so the union is large enough automatically.

So: \(4\) choices of \(X\), then \(\binom{13}{2}=78\) for \(\{p,q\}\), then an ordered triple \((a,b,c)\) of different ranks no two of which form \(\{p,q\}\). Of the \(13\cdot12\cdot11=1716\) such triples, a bad one is fixed by which of the \(3\) position pairs carries \(\{p,q\}\), in which of the \(2\) orders, and which of the \(11\) other ranks fills the last place; none is bad twice, as coinciding pairs would force equal entries. That leaves \(1716-66=1650\), so

$$f(5)=4\cdot 78\cdot 1650=514800,$$

the value in the statement. It also shows why the obvious shortcut fails: picking a Badugi and adding a fifth card gives \(17160\cdot48=823680\), counting a hand once per Badugi inside it, and inclusion–exclusion over overlapping Badugis grows unmanageable long before \(n=13\).

5. Reading a hand rank by rank

For each rank \(r\) let \(T_r\subseteq S\) collect the suits in which the hand holds the card of rank \(r\). A rank owns one card per suit, so \(T_r\) fixes that rank's cards completely, hands correspond one to one with sequences \((T_1,\dots,T_{13})\), and a hand's size is \(n=\sum_r|T_r|\). We walk through the ranks one at a time.

Knowing which suits have appeared is not enough: if the first rank gives cards in two suits we can match either but not both, as they share a rank, while a second rank in one of those suits makes the pair matchable. What must be carried forward is which sets of suits can be matched at once.

6. What has to be remembered

Call \(M\subseteq S\) matchable after \(r\) ranks when we can pick \(|M|\) cards from different ranks among the first \(r\) whose suits are exactly \(M\), and let \(\mathcal R_r\) be the family of all such \(M\).

It is small. There are only \(2^4=16\) subsets of \(S\), so \(\mathcal R_r\) fits in a \(16\)-bit mask rmask: number the subsets \(0,\dots,15\) by their suit bits and set bit \(j\) when subset \(j\) is matchable. At first only the empty set is, so \(\mathcal R_0=\{\varnothing\}\) and rmask \({}=1\).

It is enough. Suppose the hand holds a matching \(F\) covering all four suits, and split it at rank \(r\). Its cards of ranks \(\le r\) form a matching among the first \(r\) ranks, so their suit set \(M\) lies in \(\mathcal R_r\), and the rest matches \(S\setminus M\) using later ranks only. Conversely any \(M\in\mathcal R_r\) whose complement is matchable later gives a Badugi, as the halves use different ranks and suits. So the first \(r\) ranks reach the future only through \(\mathcal R_r\). Note too that \(\mathcal R_r\) is closed downwards, as deleting cards from a matching leaves a matching.

7. The transition for one new rank

Let the next rank contribute \(T\); the hand grows by \(|T|\) cards, but a matching takes at most one of them. If \(M\) is matchable using the first \(r+1\) ranks, either its matching avoids the new rank, so \(M\in\mathcal R_r\), or it uses one card of suit \(b\in T\), and dropping that card leaves \(M\setminus\{b\}\in\mathcal R_r\). Both steps reverse, so

$$\begin{aligned}\mathcal R_{r+1}&=\mathcal R_r\cup\mathcal E,\\ \mathcal E&=\bigl\{\,M\cup\{b\}\,\bigr\},\end{aligned}$$

where \(\mathcal E\) holds every set of that form, for \(M\in\mathcal R_r\) and \(b\in T\setminus M\). The family only grows, and downward closure survives: a subset of \(M\cup\{b\}\) is either a subset of \(M\), hence in \(\mathcal R_r\), or \(M'\cup\{b\}\) with \(M'\subseteq M\), and then \(M'\in\mathcal R_r\) and \(b\in T\setminus M'\), putting it in \(\mathcal E\).

8. The test at the end

By Section 6 a hand contains a Badugi exactly when \(S\in\mathcal R_{13}\), that is when bit \(15\) of rmask, the bit of all four suits, is set. Downward closure sharpens this: if the full set is matchable so is every subset, so all sixteen bits are set and rmask \({}=65535\). So exactly one mask that can occur means success. Of all \(2^{16}\) \(16\)-bit values, \(2^{15}\) carry that bit, but most of those encode no downward-closed family.

9. Why only \(68\) masks ever occur

Section 7 establishes only downward closure, which alone would allow \(168\) families, one per antichain of maximal members: the Dedekind number \(M(4)=168\), a total that even counts the empty family. ^[6] The recurrence restricts matters much further. The matchable sets on one side of a bipartite graph are exactly the independent sets of a transversal matroid, ^[4] so every \(\mathcal R_r\) obeys the matroid axioms, and four elements carry only \(68\) matroids. ^[5] Applying the \(16\) transitions from \(\mathcal R_0\) until no new mask appears reaches exactly those \(68\) — which the programs do not exploit, but which explains why they finish instantly.

10. Assembling the answer

This is dynamic programming: partial hands with the same card count and matchable family are pooled, as later ranks treat them alike. ^[9] Let \(D_r(n,m)\) count the sequences \((T_1,\dots,T_r)\) with \(\sum|T_i|=n\) whose family is the mask \(m\), and \(U(m,T)\) be the transition of Section 7. Then \(D_0(0,1)=1\), and each pass adds \(D_r(n,m)\) into

$$D_{r+1}\bigl(n+|T|,\,U(m,T)\bigr)$$

for all \(16\) subsets \(T\subseteq S\). Each \(T\) fixes the new rank's cards uniquely, so every partial hand is counted once however many Badugis it holds. States with \(n\gt13\) are dropped at once, as later ranks only add cards. After thirteen passes Section 8 gives \(f(n)=D_{13}(n,65535)\), and we sum these for \(4\le n\le13\). The first values, each confirmed twice below, are \(f(4)=17160\), \(f(5)=514800\), \(f(6)=7464600\) and \(f(7)=70579080\).

How the Code Works

All three programs implement the transition of Section 7 and the passes of Section 10. C++ and Java precompute the whole transition table and count in dense layers; Python memoises transitions as needed and keeps sparse ones. Only the C++ file, the reference implementation, has checkpoint and binomial helpers. ^[7]

The transition table. build_updates() in C++ and buildUpdates() in Java tabulate update[rmask][t] for all \(65536\) masks and \(16\) suit sets: Section 7 in code. Each entry starts as rmask itself, the branch that leaves the new rank out of every matching; the loop over matched then visits each subset in the mask, forms available = t & ~matched, and walks its bits with __builtin_ctz (Java: Integer.numberOfTrailingZeros), setting the bit of matched | (1 << suit_bit) for each available suit — exactly \(\mathcal E\). Python evaluates get_update(rmask, t) on demand, cached in update_memo under (rmask << 4) | t; only \(1088\) keys are ever asked for, so the million-entry table is never built.

The passes. compute_f_values in C++ and solve in Java keep two dense layers curr and next, each a \(14\times65536\) array of \(64\)-bit counters indexed by size and mask, with curr[0][1] = 1 for \(\mathcal R_0\). Each pass clears next, skips zero cells, adds every count into next[n + popcount[t]][update[rmask][t]] for all \(16\) suit sets t, dropping the move when \(n+|T|\gt13\), then swaps the layers. Python's solve keeps curr as fourteen dictionaries keyed by mask, so only live states exist, and takes popcounts from int.bit_count. ^[8]

Harvesting and checking. compute_f_values scans the last layer for every \(n=0,\dots,13\), adding the cells whose mask has bit \(15\) set, and returns the array \(f(n)\); main sums its entries for \(n=4,\dots,13\). Java and Python do both steps inside solve, for those ten sizes only. By Section 8 just \(65535\) can contribute, so each size has one term. C++ run_checkpoints() verifies \(f(5)=514800\), \(f(4)=17160\) and \(f(n)\le\binom{52}{n}\); --skip-checkpoints suppresses it. One detail costs real time: it calls compute_f_values() itself and main calls it again, so table and passes are built twice when the checkpoints run.

Integer widths. Each counter counts hands of one size, so none exceeds \(\binom{52}{13}=635013559600\), the largest being \(f(13)=601979379716\), and the accumulated total is bounded by the \(922205345845\) hands of sizes \(4\) to \(13\); both are below \(2^{40}\), so std::uint64_t and Java long suffice and Python's integers are unbounded anyway. ^[8] comb_u64 needs more care: its numerator for \(\binom{52}{13}\) reaches about \(4\cdot10^{21}\), past \(64\) bits, hence its \(128\)-bit intermediates. Java keeps the table in short[][] and writes (short) nextMask, negative from \(32768\) up, so each read repairs it with & 0xFFFF; C++ uses std::uint16_t.

Complexity and Verification

Every size is fixed by the deck, so the cost is a constant and only its magnitude matters. Building the C++ or Java table tests \(65536\cdot16\cdot16=16777216\) subset bits and makes \(8388608\) one-suit extensions; its entries hold \(2097152\) bytes and the two counting layers \(14680064\), stored numbers only, without array or allocator overhead. Were no cell empty, the passes would consider \(13\cdot14\cdot65536\cdot16=190840832\) transitions.

The truth is far smaller. Only \(68\) masks occur, the fullest layer holds \(495\) non-empty cells of \(917504\), and the passes consider just \(65328\) cell-and-suit-set pairs, about \(2921\) times fewer, of which \(58570\) pass the size limit and add. The zero test cannot avoid the sweep itself: a run still visits \(13\cdot14\cdot65536=11927552\) cells and clears as many counters. Python, iterating over stored states only, is accordingly the quickest, though such figures depend on machine and build: best of five whole-process runs on one machine, C++ built by clang++ -O2, gave Python \(0.027\) s, C++ \(0.051\) s and \(0.098\) s without and with the checkpoints, and Java \(0.089\) s.

The C++ program itself checks \(f(4)=17160\), \(f(5)=514800\) and \(f(n)\le\binom{52}{n}\) for \(n\le13\). The following were done for this article and are not in the published sources.

• The three programs print identical output, --skip-checkpoints changes nothing, and Sections 2 and 4 give \(f(4)\) and \(f(5)\) with no program at all.
• Brute force over every hand of a reduced deck — all \(65536\) hands on four ranks and all \(1048576\) on five — testing each \(4\)-card subset directly, reproduces this method cut down to that many ranks, at every size.
• Over those \(1048576\) hands, "contains no Badugi", "some \(A\subseteq S\) occupies fewer than \(|A|\) ranks" and the four configurations of Section 3 coincide.
• A second method uses no masks: with \(c_T\) the number of ranks carrying exactly the non-empty suit set \(T\), the \(166783\) profiles with \(\sum_T|T|c_T\le13\) each stand for \(13!/(c_0!\prod_Tc_T!)\) assignments to named ranks, \(c_0\) counting unused ones, and keeping those satisfying Hall's condition reproduces every \(f(n)\), \(n\le13\).
• On \(4000\) random rank systems the transition of Section 7 agrees with a brute-force matching search and with Hall's condition applied directly.
• A sweep over all \(65536\) masks gives the \(168\) downward-closed families and \(68\) matroids of Section 9, with \(65535\) the only family holding all four suits; a closure search gives those same \(68\) as the reachable ones.

Footnotes and References

The references supply the background facts used above; the rank-by-rank state, its sufficiency and transition, and the reachable state count are derived here.

1. Project Euler 369 — Badugi. The official statement calls a set of 4 cards from a 52-card deck a Badugi when it has no pairs and no two cards of one suit, defines f(n) as the number of n-card choices containing such a subset, notes that 514800 of the 2598960 five-card choices qualify, and asks for the sum over 4 ≤ n ≤ 13.
2. Wikipedia — Badugi. The article on the draw-poker variant states that a four-card hand whose cards differ in both rank and suit is called a badugi.
3. Wikipedia — Hall's marriage theorem. For a finite bipartite graph on parts X and Y there is a matching covering every vertex of X if and only if |W| ≤ |N(W)| for every W ⊆ X, with N(W) the vertices of Y adjacent to some vertex of W. Section 3 applies this with X the four suits.
4. Wikipedia — Transversal matroid. For a bipartite graph with parts U and V, the transversal matroid has ground set U and takes as independent exactly the subsets of U that are endpoints of some matching — the family of Section 6.
5. OEIS A058673 — number of matroids on n labeled points. The sequence runs 1, 2, 5, 16, 68, 406, 3807, 75164 from n = 0, so four distinguishable elements carry 68 matroids, as Section 9 uses.
6. Wikipedia — Dedekind number. M(n) counts the antichains of subsets of an n-element set, equivalently the monotone Boolean functions of n variables: 2, 3, 6, 20, 168 for n = 0 to 4. A downward-closed family is fixed by its maximal members, so M(4) = 168 counts them on four suits.
7. C++ — Euler369.cpp. The linked immutable C++ revision contains build_updates, compute_f_values, comb_u64 and the checkpoints described above. It is the implementation record for this article.
8. Python — int.bit_count returns an integer's population count, from Python 3.10 onwards, and the same page records that Python integers have unlimited precision. Java — Integer documents bitCount and numberOfTrailingZeros, used by the Java port.
9. MIT OpenCourseWare — Dynamic Programming I. Lecture 19 of 6.006 Introduction to Algorithms (Fall 2011) presents dynamic programming through Fibonacci numbers and shortest paths, teaching memoisation and the reuse of subproblem solutions, the principle Section 10 applies.