Distinct Orders to Break Stacked Targets
A sniper is shooting at targets arranged in $r$ columns. Column $i$ (for $1 \leq i \leq r$) has $n_i$ targets stacked vertically. On each turn, the sniper selects a column that still has unbroken targets and shoots the lowest remaining target in that column. Once a column is empty, it can no longer be selected.
In how many distinct orders can the sniper break all the targets?
Solve this for $r = 5$ with $n_i = i$ (i.e., column 1 has 1 target, column 2 has 2, ..., column 5 has 5).
Hints
- Think about what information fully determines a shooting sequence. Within a single column, is there any choice?
- Represent the sequence of shots as a string of length $n_1 + \cdots + n_r$, where each position records which column was shot. How many times does each symbol appear?
- You are counting anagrams of a word with $n_1$ copies of letter 1, $n_2$ copies of letter 2, etc. The multinomial coefficient $\frac{N!}{n_1! \cdots n_r!}$ gives the count.
Worked Solution
How to Think About It: The constraint that the sniper must always shoot the *lowest* remaining target in a column is the key. Within any single column, the order is forced -- bottom to top. So the only freedom is in choosing which column to shoot at each turn. This means the entire sequence of $n_1 + n_2 + \cdots + n_r$ shots is determined by the order in which columns appear. Thought of differently: write down a string of length $N = n_1 + \cdots + n_r$, where position $k$ records which column was shot on turn $k$. Column $i$ must appear exactly $n_i$ times. So the question reduces to: how many distinct strings (anagrams) of this form exist?
Quick Estimate: For $r = 5$ and $n_i = i$, the total number of shots is $N = 1 + 2 + 3 + 4 + 5 = 15$. If all 15 shots were distinguishable, there would be $15!$ orderings. But within each column the shots are identical (forced order), so we divide by $n_i!$ for each column. A rough sense of magnitude: $15! \approx 1.3 \times 10^{12}$, and $1! \cdot 2! \cdot 3! \cdot 4! \cdot 5! = 1 \cdot 2 \cdot 6 \cdot 24 \cdot 120 = 34{,}560$. So the answer should be on the order of $10^{12} / 10^{4.5} \approx 10^{7.6}$, i.e., tens of millions.
Approach: Use the multinomial coefficient formula for counting anagrams.
Formal Solution:
Label each shot with the column number it belongs to. A valid shooting sequence is a string of length $N = n_1 + n_2 + \cdots + n_r$ over the alphabet $\{1, 2, \ldots, r\}$, where symbol $i$ appears exactly $n_i$ times. The within-column ordering constraint (always shoot the lowest remaining target) is automatically satisfied: no matter where the $n_i$ copies of symbol $i$ land in the string, they correspond to shooting the targets in column $i$ from bottom to top.
The number of such strings is the multinomial coefficient:
$$\binom{N}{n_1, n_2, \ldots, n_r} = \frac{N!}{n_1! \cdot n_2! \cdots n_r!}$$
For $r = 5$ and $n_i = i$:
$$\frac{15!}{1! \cdot 2! \cdot 3! \cdot 4! \cdot 5!} = \frac{1{,}307{,}674{,}368{,}000}{34{,}560} = 37{,}837{,}800$$
Answer: The number of distinct orders is $\dfrac{(n_1 + \cdots + n_r)!}{n_1! \cdots n_r!}$. For $r = 5$ with $n_i = i$, this equals $37{,}837{,}800$.
Intuition
The core insight is recognizing that a constrained ordering problem can often be recast as a simpler counting problem by identifying what choices are actually free. Here, the within-column order is completely forced, so the only degree of freedom is the interleaving of columns -- which reduces to counting anagrams (multinomial permutations). This is the same structure that appears whenever you merge $r$ pre-sorted sequences into one: the number of valid interleavings is a multinomial coefficient.
This type of reduction shows up frequently in combinatorics and probability on quant interviews. Whenever you see a problem with partial ordering constraints (some events must happen before others, but not all), ask yourself: what is the group of symmetries that the constraints remove? Here, permutations within each column are removed, giving the $n_i!$ terms in the denominator. The pattern generalizes to lattice path counting, ballot problems, and scheduling problems -- all of which boil down to multinomials or their relatives.