Solution

Answer: 11044580082199135512

Problem statement

Project Euler Problem 987, “Straight Eight”:

In Poker a straight is exactly five cards of sequential rank NOT all of the same suit. In this problem an ace can rank either high as in A-K-Q-J-10 or low as in 5-4-3-2-A, but cannot simultaneously rank both high and low, so Q-K-A-2-3 is not allowed.

There are $10200$ ways of choosing a straight from a normal $52$ card deck.

There are $31832952$ ways of choosing two disjoint straights from a single $52$ card deck.

Find the number of ways of choosing eight disjoint straights from a single $52$ card deck.

In this the order of choosing the straights does not matter.

Mathematical analysis

There are exactly 10 possible rank-patterns for a straight:

$$A2345,\ 23456,\ 34567,\ \dots,\ TJQKA$$

Call these windows $W_0,\dots,W_9$.

A straight is obtained by choosing one suit for each of the 5 ranks, with the restriction that the 5 cards are not all the same suit.

So for a single straight:

$$4^5 - 4 = 1024 - 4 = 1020$$

and

$$10 \cdot 1020 = 10200$$

matching the statement.

Step 1 — Multiplicity vectors

Suppose among the 8 straights:

$p_0$ use $A2345$,
$p_1$ use $23456$,
…
$p_9$ use $TJQKA$.

Then:

$$p_0+p_1+\cdots+p_9=8$$

For every rank, at most 4 cards exist (one per suit), so the total number of straights using a given rank cannot exceed 4.

This heavily restricts the valid vectors $p$.

For a fixed multiplicity vector:

the number of ordered assignments of the 8 labeled straights to the windows is

$$\frac{8!}{\prod p_i!}$$

Step 2 — Counting suit assignments

For a fixed ordered configuration of windows:

every straight needs one suit per rank,
cards cannot repeat,
no straight may be a straight flush.

The clean way to enforce “not all same suit” is inclusion–exclusion.

Inclusion–exclusion

Let a subset $T$ of straights be forced to be straight flushes.

If a straight is monochromatic, then all its ranks use the same suit.

Now examine a single rank $r$.

Suppose:

$c_r$ total straights use rank $r$,
$k_r$ of those belong to $T$.

The $k_r$ monochromatic straights already consume $k_r$ distinct suits at that rank.

The remaining $c_r-k_r$ straights may use any injective assignment among the remaining suits:

$$P(4-k_r,\ c_r-k_r) = \frac{(4-k_r)!}{(4-c_r)!}$$

Multiplying over all 13 ranks gives the number of completions for that subset $T$.

The only remaining task is counting valid colorings of the monochromatic straights.

Two monochromatic straights that overlap in rank cannot share the same suit.

Thus we obtain a graph-coloring problem on an interval-overlap graph.

Since there are only 8 straights total, brute force over all subsets $T\subseteq{1,\dots,8}$ is completely feasible.

Python implementation

from functools import lru_cache
from math import factorial

# ------------------------------------------------------------
# Build the 10 straight windows
# ------------------------------------------------------------

windows = []

# A2345
windows.append([12, 0, 1, 2, 3])

# 23456 ... TJQKA
for s in range(1, 10):
    windows.append(list(range(s - 1, s + 4)))

# ------------------------------------------------------------
# Overlap graph between straight windows
# ------------------------------------------------------------

overlap = [[False] * 10 for _ in range(10)]

for i in range(10):
    for j in range(10):
        overlap[i][j] = bool(set(windows[i]) & set(windows[j]))

# ------------------------------------------------------------
# Generate all valid multiplicity vectors p
# satisfying:
#
#   sum p_i = 8
#   every rank used at most 4 times
# ------------------------------------------------------------

vectors = []

def gen(i, rem, p, rank_count):
    if i == 10:
        if rem == 0:
            vectors.append(tuple(p))
        return

    for x in range(rem + 1):

        new_count = rank_count[:]
        ok = True

        for r in windows[i]:
            new_count[r] += x
            if new_count[r] > 4:
                ok = False
                break

        if ok:
            p.append(x)
            gen(i + 1, rem - x, p, new_count)
            p.pop()

gen(0, 8, [], [0] * 13)

# ------------------------------------------------------------
# Count suit assignments for a fixed multiplicity vector
# using inclusion-exclusion
# ------------------------------------------------------------

@lru_cache(None)
def count_vector(p):

    p = list(p)

    # Expand into individual labeled straights
    copies = []

    for w, cnt in enumerate(p):
        copies += [w] * cnt

    m = len(copies)

    # Total usage count of each rank
    total_rank_use = [0] * 13

    for w in copies:
        for r in windows[w]:
            total_rank_use[r] += 1

    answer = 0

    # Inclusion-exclusion over monochromatic straights
    for mask in range(1 << m):

        chosen = [i for i in range(m) if (mask >> i) & 1]

        # k_r
        mono_use = [0] * 13

        for i in chosen:
            for r in windows[copies[i]]:
                mono_use[r] += 1

        # Count remaining injective assignments
        ways = 1
        ok = True

        for r in range(13):

            a = 4 - mono_use[r]
            b = total_rank_use[r] - mono_use[r]

            if b > a:
                ok = False
                break

            # falling factorial P(a,b)
            for t in range(a - b + 1, a + 1):
                ways *= t

        if not ok:
            continue

        # Count proper colorings of monochromatic straights
        color_count = 0
        colors = {}

        order = chosen

        def dfs(idx):
            nonlocal color_count

            if idx == len(order):
                color_count += 1
                return

            i = order[idx]

            forbidden = set()

            for j, c in colors.items():
                if overlap[copies[i]][copies[j]]:
                    forbidden.add(c)

            for c in range(4):
                if c not in forbidden:
                    colors[i] = c
                    dfs(idx + 1)
                    del colors[i]

        dfs(0)

        answer += ((-1) ** len(chosen)) * ways * color_count

    return answer

# ------------------------------------------------------------
# Total count
# ------------------------------------------------------------

total = 0

for p in vectors:

    mult = factorial(8)

    for x in p:
        mult //= factorial(x)

    total += count_vector(p) * mult

# unordered straights
total //= factorial(8)

print(total)

Code walkthrough

Window construction

We encode the 10 legal straight rank-patterns.

Example:

[12,0,1,2,3]

represents $A2345$.

Multiplicity vectors

The recursion gen(...) enumerates all vectors

$$(p_0,\dots,p_9)$$

with:

$$\sum p_i = 8$$

while enforcing the rank-capacity condition:

$$c_r \le 4$$

for every rank.

Only 1599 valid vectors survive.

Inclusion–exclusion

For each subset of straights forced monochromatic:

for mask in range(1 << m):

we compute:

suit usage already forced,
remaining injective suit assignments rank-by-rank,
valid colorings of the monochromatic overlap graph.

Then inclusion–exclusion alternates signs.

Verification

The program reproduces the two values given in the statement:

1 straight:

$$10200$$

2 disjoint straights:

$$31832952$$

So the counting model is correct.

Running the full computation for 8 straights gives:

$$11044580082199135512$$

Answer: 11044580082199135512