Detailed mathematical approach

Problem Summary

For Problem 964, the quantity attached to \(k\) is evaluated at the special size

$n=\frac{k(k-1)}{2}+1.$

For the required instance \(k=7\), this gives \(n=22\). The three implementations all compute the same normalized combinatorial quantity: first they build an inclusion-exclusion total over a reduced universe of \(n-1\) relative chair positions, and only at the end do they divide by \(n!\).

The important point is that the problem is not attacked by enumerating chair arrangements directly. Instead, the mathematics tracks which relative chair positions can survive simultaneously through \(k\) successive stages. Once that common-survivor question is written correctly, the whole computation collapses to a short alternating sum with binomial coefficients.

Mathematical Approach

Let \(\mathcal{U}\) be the reduced set of relative chair positions, with \(|\mathcal{U}|=n-1\). The implementations can be read as working with stage sets

$A_i\subseteq \mathcal{U}\qquad (1\le i\le k),$

where \(A_i\) records the positions still compatible with surviving stage \(i\), and where the only data that matters is the cardinality

$|A_i|=n-i.$

The Triangular Size and the Reduced State Space

The value \(n=\frac{k(k-1)}2+1\) is the natural size parameter of the problem. In the final target case \(k=7\), the reduced universe has \(n-1=21\) positions. The code never tries to list all chair configurations. It uses only the fact that every stage \(i\) leaves a uniformly distributed subset of size \(n-i\) inside the same ambient set \(\mathcal{U}\).

This immediately creates a useful invariant: for a fixed integer \(r\), every \(r\)-element subset \(R\subseteq \mathcal{U}\) behaves identically. The contribution depends only on \(r\), never on the actual labels of the chairs inside \(R\).

Inclusion-Exclusion on Common Survivors

Define \(Q_k\) to be the raw inclusion-exclusion total before the final factorial normalization. We want to count the configurations in which no relative chair position survives all \(k\) stages at once. For each \(x\in\mathcal{U}\), let \(E_x\) be the event that \(x\) belongs to every stage set \(A_1,\dots,A_k\). Then

$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$

Applying inclusion-exclusion over subsets \(R\subseteq\mathcal{U}\) gives

$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$

Because all subsets of the same size are equivalent, we can group terms by \(r=|R|\).

The Survival Factor for a Fixed \(r\)-Set

Fix an \(r\)-element subset \(R\subseteq\mathcal{U}\). For one stage \(i\), the probability that all elements of \(R\) survive that stage is the fraction of size-\((n-i)\) subsets containing \(R\):

$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$

The implementations multiply these stage factors across \(i=1,\dots,k\), which is exactly why the core term in the code is a product of \(k\) binomial ratios. The factor for \(i=1\) equals 1, since \(|A_1|=n-1\), but it is left inside the product so that every stage is treated uniformly.

The Closed Form Used by the Implementations

There are \(\binom{n-1}{r}\) possible sets \(R\) of size \(r\), so the grouped inclusion-exclusion sum becomes

$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$

This is the exact formula evaluated in C++, Python, and Java. A useful simplification is that \(\binom{n-i}{r}=0\) whenever \(r>n-i\). In particular, once \(r>n-k\), the whole term vanishes automatically. So although the loop is written up to \(n-1\), only the first \(n-k+1\) terms can contribute.

The final Project Euler quantity is then

$\boxed{P_k=\frac{Q_k}{n!}.}$

That last division by \(n!\) is not a numerical trick; it is part of the problem's definition, and the three implementations all perform it only after the alternating sum has been accumulated at high precision.

Worked Example: \(k=3\)

For \(k=3\), we get \(n=\frac{3\cdot2}{2}+1=4\), so \(|\mathcal{U}|=3\) and the stage sizes are \(3,2,1\). The formula becomes

$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$

The \(r=0\) term is \(1\). For \(r=1\), we subtract

$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$

All terms with \(r\ge2\) vanish, because the last stage leaves only one surviving position. Therefore

$Q_3=1-\frac23=\frac13,$

and after the factorial normalization,

$P_3=\frac{1/3}{4!}=\frac1{72}.$

This matches the validation constant used by the implementations, so the inclusion-exclusion derivation is exactly the one the code is evaluating.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They first set a high-precision decimal environment, compute \(n=\frac{k(k-1)}2+1\), and then sweep through the alternating sum over \(r=0,1,\dots,n-1\). For each \(r\), they evaluate the exact binomial coefficient \(\binom{n-1}{r}\), then multiply the \(k\) stage ratios \(\binom{n-i}{r}/\binom{n-1}{r}\).

After the product is formed, the implementation restores the outer factor \(\binom{n-1}{r}\), applies the sign \((-1)^r\), and adds the result to the running total. Nothing symbolic is cached, because for the target case \(k=7\) the numbers are tiny enough that direct exact binomial evaluation is already sufficient.

Once the alternating sum \(Q_k\) is complete, the code divides by \(n!\) using the same high-precision arithmetic. Finally, it checks the known values for \(k=2\), \(k=3\), and \(k=4\), and prints the answer for \(k=7\) in scientific notation.

Complexity Analysis

If binomial coefficients are regarded as available in \(O(1)\) time, the mathematical core is just the outer \(r\)-sum with \(k\) multiplicative factors per term, so the complexity is \(O(nk)\). Since \(n=\Theta(k^2)\), that is \(O(k^3)\) for the closed-form summation itself.

The literal C++ and Java implementations recompute each binomial coefficient by a short multiplicative loop, so their raw arithmetic count is closer to \(O(kn^2)\). For the actual target \(k=7\), however, \(n=22\), so both viewpoints are tiny in practice. Memory usage is \(O(1)\) apart from the high-precision numeric objects used for the accumulation and the final factorial.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=964
2. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
3. Binomial coefficient: Wikipedia - Binomial coefficient
4. Factorial: Wikipedia - Factorial
5. Hypergeometric distribution: Wikipedia - Hypergeometric distribution
6. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic