TAOCP 7.2.1.2 Exercise 37

A Sims table used by Algorithms G or H encodes, for each level of a stabilizer chain for $S_n$, a full set of coset representatives for the successive point stabilizers.

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.2.1.2: Generating All Permutations

Exercise 37. ▶ [HM22] [HM22] How many Sims tables can be used with Algorithms G or H? Estimate the logarithm of this number as n →∞.

Verified: no
Solve time: 1m41s

Solution

A Sims table used by Algorithms G or H encodes, for each level of a stabilizer chain for $S_n$, a full set of coset representatives for the successive point stabilizers. For the symmetric group $S_n$ acting on ${1,\dots,n}$ with the standard stabilizer chain

$$ S_n \ge S_{n-1} \ge \cdots \ge S_1, $$

the level corresponding to fixing ${1,\dots,k-1}$ leaves the point $k$ free to move among the remaining $n-k+1$ positions.

At level $k$, a Sims table selects one representative permutation for each element of the orbit of $k$ under the stabilizer of ${1,\dots,k-1}$. The orbit has size $n-k+1$. Once the image of $k$ is fixed, the remaining $n-k$ points can be permuted arbitrarily while preserving the stabilizer constraints, contributing $(n-k)!$ choices for each image. The number of admissible choices at level $k$ is therefore

$$ (n-k+1)\cdot (n-k)! = (n-k+1)!. $$

The choices at different levels are independent, since each level acts on a disjoint refinement of the stabilizer chain. The total number $T_n$ of Sims tables for $S_n$ is thus

$$ T_n = \prod_{k=1}^n (n-k+1)! = \prod_{m=1}^n m!. $$

The logarithm satisfies

$$ \log T_n = \sum_{m=1}^n \log(m!). $$

Stirling’s formula in logarithmic form gives

$$ \log(m!) = m\log m - m + O(\log m). $$

Substituting into the sum yields

$$ \log T_n = \sum_{m=1}^n m\log m - \sum_{m=1}^n m + O!\left(\sum_{m=1}^n \log m\right). $$

The linear term evaluates to

$$ \sum_{m=1}^n m = \frac{n(n+1)}{2} = \frac{n^2}{2} + O(n). $$

The logarithmic error term satisfies

$$ \sum_{m=1}^n \log m = \log(n!) = O(n\log n). $$

For the main term, comparison with an integral gives

$$ \sum_{m=1}^n m\log m = \int_1^n x\log x,dx + O(n\log n). $$

The integral evaluates by integration by parts:

$$ \int x\log x,dx = \frac{x^2}{2}\log x - \frac{x^2}{4}. $$

Hence

$$ \int_1^n x\log x,dx = \frac{n^2}{2}\log n - \frac{n^2}{4} + O(1), $$

so

$$ \sum_{m=1}^n m\log m = \frac{n^2}{2}\log n - \frac{n^2}{4} + O(n\log n). $$

Combining contributions,

$$ \log T_n = \left(\frac{n^2}{2}\log n - \frac{n^2}{4}\right)

  • \frac{n^2}{2}
  • O(n\log n). $$

Thus

$$ \log T_n = \frac{1}{2}n^2\log n - \frac{3}{4}n^2 + O(n\log n). $$

This completes the derivation.

$$ \boxed{\log T_n = \frac{1}{2}n^2\log n - \frac{3}{4}n^2 + O(n\log n)} $$