Detailed mathematical approach

Problem Summary

We throw \(k\) defects independently and uniformly onto \(n\) chips. Each defect is placed separately, so there are exactly \(n^k\) equally likely outcomes. The goal is to find the probability that at least one chip receives three or more defects.

Mathematical Approach

1) Work with the complement

Let \(E\) be the event that some chip receives at least three defects. It is much easier to count the complementary event

$E^c=\{\text{every chip receives at most two defects}\}.$

Then

$\Pr(E)=1-\Pr(E^c).$

So the real task is to count all placements in which occupancies are only \(0\), \(1\), or \(2\).

2) Classify by the number of double-occupied chips

Suppose exactly \(i\) chips receive two defects. Then exactly \(k-2i\) chips receive one defect, and the remaining \(n-(k-i)\) chips receive none. The parameter \(i\) can range only over

$0 \le i \le \left\lfloor \frac{k}{2}\right\rfloor.$

3) Counting a fixed \(i\)-layer

We count placements with exactly \(i\) double chips in two steps.

Step A: choose how the \(k\) labeled defects are grouped into \(i\) unordered pairs and \(k-2i\) singles. The number of such groupings is

$\frac{k!}{2^i\,i!\,(k-2i)!}.$

The factor \(2^i\) removes the order inside each pair, and \(i!\) removes the order among the pairs themselves.

Step B: send these \(k-i\) groups to distinct chips. Since the groups are effectively ordered as “\(i\) pair-slots followed by \(k-2i\) single-slots”, the number of injective chip assignments is the falling factorial

$n_{(k-i)}=n(n-1)\cdots(n-k+i+1).$

Therefore the number of valid placements in the \(i\)-th layer is

$\frac{k!}{2^i\,i!\,(k-2i)!}\,n_{(k-i)}.$

4) Probability of one layer

Since the total number of equally likely placements is \(n^k\), the probability of the \(i\)-th layer is

$P_i=\frac{k!}{2^i\,i!\,(k-2i)!}\cdot\frac{n_{(k-i)}}{n^k}.$

Summing over all admissible \(i\) gives the complement:

$\Pr(E^c)=\sum_{i=0}^{\lfloor k/2\rfloor} P_i,$

hence

$\Pr(E)=1-\sum_{i=0}^{\lfloor k/2\rfloor} P_i.$

5) Worked example: \(p(3,7)\)

The source code checks the small case \(k=3\), \(n=7\).

If one chip gets three defects, then all three labeled defects must land on the same chip. There are exactly \(7\) such placements, one for each chip, out of

$7^3=343$

total placements. So

$p(3,7)=\frac{7}{343}=\frac{1}{49}=0.0204081632653\ldots$

This is exactly the checkpoint used by the C++ solution.

6) Ratio between consecutive layers

Evaluating every \(P_i\) from scratch is possible, but the Python and Java solutions use a more efficient recurrence. Divide \(P_i\) by \(P_{i-1}\):

$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2i}\cdot\frac{1}{n-k+i}.$

Equivalently, in the exact form used in the code,

$\frac{P_i}{P_{i-1}}=\frac{(k-2i+2)(k-2i+1)}{2ni}\cdot \frac{1}{1-(k-i)/n}.$

So once \(P_0\) is known, each next term can be updated in constant time.

7) Why logarithms are used

For the real parameters \((k,n)=(20000,10^6)\), the raw factorials and products are astronomically large or tiny. Direct floating-point multiplication would overflow or underflow long before the final answer is reached. The implementations therefore work with

$\log P_i$

sum the logarithms of multiplicative factors, and only then recover \(P_i\) with exp.

How the Code Works

1) Base layer. For \(i=0\), no chip has two defects, so all \(k\) defects land on distinct chips. The code computes

$P_0=\frac{n_{(k)}}{n^k}=\prod_{j=0}^{k-1}\left(1-\frac{j}{n}\right)$

in log form.

2) Incremental update. Python and Java keep a running variable logp for \(\log P_i\) and update it using the ratio above, rather than recomputing the whole expression each time.

3) Accumulating the complement. The variable answer starts at \(1\), then subtracts each \(P_i\). After the loop, what remains is exactly \(\Pr(E)\).

4) Two implementation styles. The C++ version shows the formula more literally and recomputes the two logarithmic sums for each \(i\), which is simpler but slower. The Python and Java versions use the recurrence, which is the intended efficient idea.

Complexity Analysis

The direct layer-by-layer recomputation costs about \(O(k^2)\). The optimized recurrence used by the Python and Java solutions reduces this to \(O(k)\) time, because each new layer is obtained from the previous one in constant work. Extra memory is \(O(1)\).

Further Reading

1. Problem page: https://projecteuler.net/problem=307
2. Occupancy problems: https://en.wikipedia.org/wiki/Occupancy_problem
3. Falling factorial: https://en.wikipedia.org/wiki/Falling_and_rising_factorials