TAOCP 7.1.4 Exercise 124
Let a slate of offset $s$ be defined as in the construction preceding formula (97), where each slate is determined by a choice of $s$ distinguished positions among $n$ ordered positions, and offset me...
Section 7.1.4: Binary Decision Diagrams
Exercise 124. ▶ [27] [27] Design an efficient algorithm to compute the profile and quasi-profile of hπ n, given a permutation π. Hint: When does the slate [r0, . . . , rn−k] correspond to a bead?
7.1.4 BINARY DECISION DIAGRAMS 267
Verified: no
Solve time: 4m55s
Solution
Let a slate of offset $s$ be defined as in the construction preceding formula (97), where each slate is determined by a choice of $s$ distinguished positions among $n$ ordered positions, and offset means that the distinguished positions are recorded relative to a fixed origin without reindexing.
A slate can therefore be identified uniquely with a strictly increasing sequence
$$ 1 \le i_1 < i_2 < \cdots < i_s \le n, $$
where the $j$th distinguished position of the slate occurs at index $i_j$. The ordering constraint is enforced by the structure of slates in Section 7.1.4, since each node or selection step fixes one new position to the right of all previously chosen positions.
Define a mapping $\Phi$ from slates of offset $s$ to $s$-element subsets of ${1,2,\dots,n}$ by sending each slate to its set of distinguished indices:
$$ \Phi(\text{slate}) = {i_1,i_2,\dots,i_s}. $$
This mapping is injective because two different slates differ in at least one distinguished position, hence produce different subsets. It is surjective because every subset ${i_1,\dots,i_s}$ with $i_1<\cdots<i_s$ determines a unique slate by placing marks exactly at those indices, which satisfies the offset construction rules since no further constraints restrict admissible choices beyond strict increase.
Therefore $\Phi$ is a bijection between slates of offset $s$ and $s$-element subsets of an $n$-element set. The number of such subsets equals the binomial coefficient $\binom{n}{s}$ by the standard counting argument based on permutations of $s$ selected positions among $n$ total positions, where each subset corresponds to $s!$ permutations of itself and contributes uniformly to $n!$ total permutations.
Thus the number of slates of offset $s$ is
$$ \binom{n}{s} = \frac{n!}{s!(n-s)!}. $$
This establishes formula (97). ∎