TAOCP 1.3.3: Applications to Permutations
Section 1.3.3 exercises: 37/37 solved.
Section 1.3.3. Applications to Permutations
Exercises from TAOCP Volume 1 Section 1.3.3: 37/37 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [02] | simple | verified | 1m07s |
| 2 | [10] | simple | verified | 1m22s |
| 3 | [03] | simple | verified | 1m19s |
| 4 | [10] | simple | verified | 2m50s |
| 5 | [M10] | math-simple | verified | 1m14s |
| 6 | [M28] | math-hard | verified | 1m21s |
| 7 | [10] | simple | solved | 4m51s |
| 8 | [23] | medium | verified | 1m31s |
| 9 | [10] | simple | verified | 1m04s |
| 10 | [M28] | math-hard | verified | 1m32s |
| 11 | [15] | simple | verified | 1m28s |
| 12 | [M27] | math-hard | solved | 1m15s |
| 13 | [M24] | math-medium | verified | 9m43s |
| 14 | [M34] | math-hard | verified | 24m50s |
| 15 | [M12] | math-simple | solved | 4m13s |
| 16 | [M15] | math-simple | verified | 32m02s |
| 17 | [M24] | math-medium | verified | 44s |
| 18 | [M27] | math-hard | verified | 16m52s |
| 19 | [HM21] | hm-medium | verified | 47s |
| 20 | [M20] | math-medium | verified | 2m07s |
| 21 | [M22] | math-medium | verified | 42s |
| 22 | [HM34] | hm-hard | verified | 11m55s |
| 23 | [HM42] | hm-project | solved | 11m45s |
| 24 | [M41] | math-project | verified | 4m38s |
| 25 | [M22] | math-medium | verified | 27m26s |
| 26 | [M24] | math-medium | verified | 26m57s |
| 27 | [M20] | math-medium | verified | 42s |
| 28 | [M21] | math-medium | solved | 5m35s |
| 29 | [M25] | math-medium | verified | 3m |
| 30 | [M24] | math-medium | verified | 8m56s |
| 31 | [HM38] | hm-project | verified | 5m18s |
| 32 | [M25] | math-medium | solved | 3m14s |
| 33 | [M33] | math-hard | solved | 6m48s |
| 34 | [M25] | math-medium | verified | 47s |
| 35 | [M30] | math-hard | verified | 57s |
| 36 | [27] | hard | verified | 3m13s |
| 37 | [M26] | math-hard | solved | 3m09s |
TAOCP 1.3.3 Exercise 1
Let $f(x)=2x \bmod 7$ on ${0,1,2,3,4,5,6}$.
TAOCP 1.3.3 Exercise 2
The transformation is given by (a,b,c,d,e,f)\leftarrow(c,d,f,b,e,a), which induces the mapping $a\mapsto c$, $b\mapsto d$, $c\mapsto f$, $d\mapsto b$, $e\mapsto e$, $f\mapsto a$.
TAOCP 1.3.3 Exercise 3
The product of the two given permutations is computed by applying the right-hand permutation first, followed by the left-hand permutation.
TAOCP 1.3.3 Exercise 4
**Corrected Solution to Exercise 1.
TAOCP 1.3.3 Exercise 5
Kí hiệu phép hoán vị đã cho là $(acf)(bd)$, trong đó $e$ là điểm bất động và bị lược bỏ trong ký hiệu chu trình.
TAOCP 1.3.3 Exercise 6
We are asked to determine the effect on the execution timing of Program $A$ if the assumption that all blank words appear at the extreme right of the input is removed.
TAOCP 1.3.3 Exercise 7
Let P=(acfg)(bcd)(aed)(fade)(bgfae), with permutations composed from right to left.
TAOCP 1.3.3 Exercise 8
Algorithm $B$ maintains a table $T$ such that, after a cycle has been completely scanned, the effect of that cycle has already been incorporated into the current permutation.
TAOCP 1.3.3 Exercise 9
No.
TAOCP 1.3.3 Exercise 10
The problem asks for the timing characteristics of Program $B$, expressed through quantities $A, B, \ldots, Z$, and then to rewrite the total time in terms of $X, Y, M, N, U, V$ defined in (19) togeth...
TAOCP 1.3.3 Exercise 11
Let $\pi$ be a permutation expressed in cycle form as a product of disjoint cycles: \pi = (x_{11} x_{12} \dots x_{1n_1})(x_{21} x_{22} \dots x_{2n_2})\cdots(x_{k1} x_{k2} \dots x_{kn_k}), where each c...
TAOCP 1.3.3 Exercise 12
The proposed solution addresses the stated integral J(x)=\int_0^{y x^{1/4}} e^{-u}\left(1+\frac ux\right)^x\,du, and attempts to derive an asymptotic expansion through terms of order $O(x^{-2})$.
TAOCP 1.3.3 Exercise 13
Let the current permutation be P = (a_1,a_2,\dots,a_n).
TAOCP 1.3.3 Exercise 14
Let $A$ denote the total number of executions of the assignment j\leftarrow i in Algorithm $J$.
TAOCP 1.3.3 Exercise 15
Yes.
TAOCP 1.3.3 Exercise 16
Let the initial permutation in linear notation be $1324$.
TAOCP 1.3.3 Exercise 17
Let $C_r$ denote the number of $r$-cycles occurring among all $n!$ permutations of $n$ elements.
TAOCP 1.3.3 Exercise 18
Let $p_{nkm}$ denote the probability that a permutation of $n$ elements contains exactly $k$ cycles of length $m$.
TAOCP 1.3.3 Exercise 19
Equation (25) gives the number of derangements as P_{n0} = n!
TAOCP 1.3.3 Exercise 20
Let r=\alpha_1+\alpha_2+\alpha_3+\cdots be the total number of cycles of the permutation, including the one-cycles.
TAOCP 1.3.3 Exercise 21
Let a permutation of $n$ objects have exactly $\alpha_k$ cycles of length $k$ for each $k \ge 1$, with only finitely many nonzero $\alpha_k$.
TAOCP 1.3.3 Exercise 22
We start by using the standard cycle enumeration formula.
TAOCP 1.3.3 Exercise 23
**Corrected Solution for Exercise 1.
TAOCP 1.3.3 Exercise 24
Let the permutation be decomposed into cycles, and let $\alpha_k$ denote the number of cycles of length $k$.
TAOCP 1.3.3 Exercise 25
Let $S_n$ be the set of all permutations of ${1,2,\dots,n}$, each taken with equal probability $1/n!$.
TAOCP 1.3.3 Exercise 26
Let $S_1, S_2, \ldots, S_M$ be subsets of a fixed universe $U$.
TAOCP 1.3.3 Exercise 27
Let N=a\,m_1m_2\cdots m_t, and for each $j$ $(1\le j\le t)$ let
TAOCP 1.3.3 Exercise 28
For $1\le k\le n$, let R_k=(n\ n-1\ \cdots\ k).
TAOCP 1.3.3 Exercise 29
Let $J_n$ denote the Josephus permutation with step size $m=2$ on the set ${1,2,\dots,n}$.
TAOCP 1.3.3 Exercise 30
Let $n$ be a positive integer, and let $J_{2n+1}$ denote the Josephus permutation for $2n+1$ people with step size $m=2$.
TAOCP 1.3.3 Exercise 31
Let $m>1$.
TAOCP 1.3.3 Exercise 32
Let \pi = (2\,3)^{e_2}(4\,5)^{e_4}\cdots(2m\,2m+1)^{e_{2m}} \, (1\,2)^{e_1}(3\,4)^{e_3}\cdots(2m-1\,2m)^{e_{2m-1}}, where each $e_k \in \{0,1\}$.
TAOCP 1.3.3 Exercise 33
Working
TAOCP 1.3.3 Exercise 34
Let the array be x_0x_1\ldots x_{m-1} = \alpha,\qquad x_mx_{m+1}\ldots x_{m+n-1} = \beta, so that the original array is $\alpha\beta$ of length $m+n$.
TAOCP 1.3.3 Exercise 35
Let the initial array be indexed $0,1,\ldots,l+m+n-1$ and written x_0x_1\cdots x_{l+m+n-1}=\alpha\beta\gamma, where
TAOCP 1.3.3 Exercise 36
Let an array $X[0 \dots l+m+n-1]$ be partitioned into consecutive blocks \alpha = x_0 \dots x_{l-1}, \quad \beta = x_l \dots x_{l+m-1}, \quad \gamma = x_{l+m} \dots x_{l+m+n-1}.