TAOCP 5.1.2: Permutations of a Multiset
Section 5.1.2 exercises: 24/24 solved.
Section 5.1.2. Permutations of a Multiset
Exercises from TAOCP Volume 3 Section 5.1.2: 24/24 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M05] | math-simple | verified | 30m29s |
| 2 | [10] | simple | solved | 15m46s |
| 3 | [M13] | math-simple | verified | 17m31s |
| 4 | [M11] | math-simple | solved | 18m56s |
| 5 | [M23] | math-medium | verified | 16m30s |
| 6 | [M15] | math-simple | solved | 1h12m |
| 7 | [M21] | math-medium | verified | 1h12m |
| 8 | [30] | hard | solved | 31m23s |
| 9 | [39] | project | solved | 20m23s |
| 10 | ▶ [M30] | math-hard | solved | 50m54s |
| 11 | ▶ [M26] | math-hard | verified | 52m40s |
| 12 | [M16] | math-medium | verified | 59m39s |
| 13 | [M21] | math-medium | solved | 2h58m |
| 14 | [M30] | math-hard | solved | 15m21s |
| 15 | ▶ [M25] | math-medium | solved | 20m08s |
| 16 | [M35] | math-hard | verified | 27m42s |
| 17 | [M24] | math-medium | verified | 38m35s |
| 18 | [M30] | math-hard | solved | 1m06s |
| 19 | [HM28] | hm-hard | verified | 1h34m |
| 20 | ▶ [HM33] | hm-hard | verified | 1h40m |
| 21 | [M21] | math-medium | verified | 2h25m |
| 22 | [M30] | math-hard | solved | 23m16s |
| 23 | [M23] | math-medium | solved | 2h01m |
| 24 | [27] | hard | solved | 1h36m |
TAOCP 5.1.2 Exercise 1
False.
TAOCP 5.1.2 Exercise 2
Using the definition of intercalation, we write \beta=\text{bddad} \qquad\Longrightarrow\qquad \begin{pmatrix} a&b&d&d&d\\
TAOCP 5.1.2 Exercise 3
No.
TAOCP 5.1.2 Exercise 4
If $d < c < b < a$, the canonical factorization of (12) is obtained by reversing the order of the letters in each cycle of the factorization given in (17).
TAOCP 5.1.2 Exercise 5
Condition (b) must exclude the case $x=y$.
TAOCP 5.1.2 Exercise 6
**Solution to Exercise 5.
TAOCP 5.1.2 Exercise 7
Let the six admissible column types in (19) be \binom{b}{a},\quad \binom{c}{a},\quad \binom{a}{b},\quad \binom{c}{b},\quad \binom{a}{c},\quad \binom{b}{c},
TAOCP 5.1.2 Exercise 8
Stopped thinking
TAOCP 5.1.2 Exercise 9
**9.
TAOCP 5.1.2 Exercise 10
**Solution to Exercise 5.
TAOCP 5.1.2 Exercise 11
**Exercise 5.
TAOCP 5.1.2 Exercise 12
We are given a permutation of the multiset $\{A\cdot a,\;B\cdot b,\;C\cdot c,\;D\cdot d\}$ with $A+C = B+D$.
TAOCP 5.1.2 Exercise 13
**Exercise 13 (M21).
TAOCP 5.1.2 Exercise 14
Let \(M\) be a multiset whose elements come from a totally ordered set.
TAOCP 5.1.2 Exercise 15
Let the multiset be \(M = \{n_1\cdot x_1,\, n_2\cdot x_2,\,\ldots,\, n_m\cdot x_m\}\) with \(x_1<x_2<\cdots<x_m\) and \(\sum n_i = n\).
TAOCP 5.1.2 Exercise 16
Let $M = \{n_1 \cdot x_1, n_2 \cdot x_2, \dots, n_t \cdot x_t\}$ be a multiset with $x_1 < x_2 < \dots < x_t$ and $n = n_1 + n_2 + \dots + n_t$.
TAOCP 5.1.2 Exercise 17
The generating function for the number of inversions in a random permutation of the multiset \(\{n_1\cdot x_1, n_2\cdot x_2, \ldots, n_m\cdot x_m\}\) (with \(x_1 < x_2 < \cdots < x_m\)) is the \(z\)-m...
TAOCP 5.1.2 Exercise 18
For a permutation \(a_1 a_2 \ldots a_n\) of a multiset, an **inversion** is a pair \((i,j)\) with \(i < j\) and \(a_i > a_j\).
TAOCP 5.1.2 Exercise 19
We prove by induction on \(N\), the number of columns (total length) of \(\pi\), that \[ S(\pi)=\sum_{\lambda\le\pi}\mu(\lambda)=0\qquad\text{for }\pi\ne\epsilon, \] where \(\lambda\le\pi\) means \(\l...
TAOCP 5.1.2 Exercise 20
Let \(x_1,\dots,x_m\) be distinct symbols.
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...
TAOCP 5.1.2 Exercise 22
Let a *permutation of the multiset* $\{n_1\cdot 1,\ldots,n_m\cdot m\}$ be a sequence of length $n=n_1+\cdots+n_m$ containing exactly $n_j$ copies of $j$ for each $j$.
TAOCP 5.1.2 Exercise 23
**Solution** Let the original DNA strand be a word \(w\) of length \(N\) over the four‑letter alphabet \(\{a,b,c,d\}\) with multiplicities \(A,B,C,D\) (\(A+B+C+D=N\)).