TAOCP 5.1.2 Exercise 21

Let $f(n_1,\dots,n_m)$ be the number of permutations $a_1a_2\ldots a_n$ of the multiset $\{n_1\cdot 1, \dots, n_m\cdot m\}$ (with $n = \sum_{i=1}^m n_i$) that satisfy a_{j+1} \ge a_j - d \qquad (1 \le...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.2: Permutations of a Multiset

Exercise 21. [M21] Given $n_1, \ldots, n_m$, and $d \ge 0$, how many permutations $a_1 a_2 \ldots a_n$ of the multiset ${n_1 \cdot 1, \ldots, n_m \cdot m}$ satisfy $a_{j+1} \ge a_j - d$ for $1 \le j < n = n_1 + \cdots + n_m$?

Verified: yes
Solve time: 2h25m

Solution

Let $f(n_1,\dots,n_m)$ be the number of permutations $a_1a_2\ldots a_n$ of the multiset ${n_1\cdot 1, \dots, n_m\cdot m}$ (with $n = \sum_{i=1}^m n_i$) that satisfy
$$ a_{j+1} \ge a_j - d \qquad (1 \le j < n). $$ We assume $d \ge 0$ and $n_i \ge 0$ for all $i$.

Lemma 1. If a permutation of ${n_1\cdot 1, \dots, n_m\cdot m}$ satisfies the condition, then deleting all occurrences of $m$ leaves a permutation of ${n_1\cdot 1, \dots, n_{m-1}\cdot (m-1)}$ that also satisfies the condition.

Proof. Consider two consecutive elements $x$ and $y$ in the shortened sequence. In the original sequence they were separated by a (possibly empty) block of $m$'s. The validity of the original sequence implies $y \ge m-d$ (if a block of $m$'s precedes $y$) and $m \ge x-d$ (which is automatic since $m \ge x$). Because $x \le m$, we have $x-d \le m-d \le y$, hence $y \ge x-d$. Thus every adjacent pair in the shortened sequence satisfies the required inequality. ∎

Lemma 2. Every valid permutation of ${n_1\cdot 1, \dots, n_m\cdot m}$ can be uniquely obtained by taking a valid permutation of ${n_1\cdot 1, \dots, n_{m-1}\cdot (m-1)}$ and inserting the $n_m$ copies of $m$ into certain “allowed gaps”.

Proof. By Lemma 1, deleting all $m$'s from a valid permutation yields a valid shorter permutation. Conversely, suppose we have a valid permutation $\pi$ of the smaller multiset. We insert $m$'s into the gaps of $\pi$ (before the first element, between consecutive elements, and after the last element). The condition $a_{j+1} \ge a_j - d$ restricts where $m$ may be placed:

  • If $m$ is followed by an element $y$, we must have $y \ge m-d$.
  • If $m$ is preceded by an element $x$, we need $m \ge x-d$, which holds automatically because $m \ge x$.
  • A block of consecutive $m$'s always satisfies the condition since $m \ge m-d$.

Therefore a gap is forbidden precisely when it lies immediately before an element $y < m-d$; all other gaps are allowed. The number of forbidden gaps equals the number of elements $< m-d$ in $\pi$, which is $$ F = \sum_{i=1}^{m-d-1} n_i \qquad (\text{with } n_i = 0 \text{ for } i < 1). $$ The total number of gaps in $\pi$ is $N' + 1$ where $N' = \sum_{i=1}^{m-1} n_i$. Hence the number of allowed gaps is $$ A = (N' + 1) - F = 1 + \sum_{i=\max(1,,m-d)}^{m-1} n_i. $$ Distributing $n_m$ identical copies of $m$ into these $A$ allowed gaps (order within a gap does not matter) can be done in $$ \binom{A + n_m - 1}{n_m} = \binom{\sum_{i=\max(1,,m-d)}^{m} n_i}{n_m} $$ ways. This number depends only on the multiplicities $n_1,\dots,n_m$, not on the particular choice of $\pi$. Every valid permutation of the full multiset arises exactly once in this way. ∎

From Lemma 2 we obtain the recurrence $$ f(n_1,\dots,n_m) = f(n_1,\dots,n_{m-1}) \cdot \binom{\sum_{i=\max(1,,m-d)}^{m} n_i}{n_m}, $$ with the base case $f(n_1) = 1$ (the only permutation of ${n_1\cdot 1}$ is $1,1,\ldots,1$, which trivially satisfies the condition). Iterating the recurrence gives $$ f(n_1,\dots,n_m) = \prod_{k=1}^{m} \binom{\sum_{i=\max(1,,k-d)}^{k} n_i}{n_k}. $$ Setting $n_j = 0$ for $j > m$ we can rewrite the product more compactly as $$ f(n_1,\dots,n_m) = \prod_{k=1}^{m} \binom{n_k + n_{k+1} + \cdots + n_{k+d}}{n_k}. $$

Verification of boundary cases.

  • If $d = 0$, each binomial becomes $\binom{n_k}{n_k} = 1$, so the product is $1$ (only the non‑decreasing permutation works).
  • If $d \ge m-1$, then for every $k$ the sum $n_k + n_{k+1} + \cdots + n_{k+d}$ equals $n_k + \cdots + n_m$. The product telescopes to $$ \prod_{k=1}^{m} \frac{(n_k+\cdots+n_m)!}{n_k!,(n_{k+1}+\cdots+n_m)!} = \frac{n!}{n_1!,\cdots,n_m!}, $$ which is the total number of permutations of the multiset, as expected because the condition imposes no restriction when $d \ge m-1$.

This completes the proof. ∎

Answer: $$ \boxed{\prod_{k=1}^{m} \binom{n_k + n_{k+1} + \cdots + n_{k+d}}{n_k}} $$ where $n_j = 0$ for $j > m$.