TAOCP 5.1.4: Tableaux and Involutions
Section 5.1.4 exercises: 44/44 solved.
Section 5.1.4. Tableaux and Involutions
Exercises from TAOCP Volume 3 Section 5.1.4: 44/44 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [16] | medium | verified | 43m18s |
| 2 | [M21] | math-medium | verified | 14m53s |
| 3 | ▶ [M25] | math-medium | verified | 1m26s |
| 4 | ▶ [M30] | math-hard | verified | 2m42s |
| 5 | ▶ [M22] | math-medium | solved | 3m41s |
| 6 | [M26] | math-hard | verified | 1m17s |
| 7 | [M20] | math-medium | solved | 42m04s |
| 8 | [M18] | math-medium | verified | 56m28s |
| 9 | [M32] | math-hard | solved | 11m30s |
| 10 | [M20] | math-medium | solved | 16m42s |
| 11 | [20] | medium | solved | 46m42s |
| 12 | [M32] | math-hard | solved | 10m59s |
| 13 | [M28] | math-hard | solved | 12m07s |
| 14 | [M43] | math-project | solved | 20m52s |
| 15 | [M29] | math-hard | verified | 44m12s |
| 16 | [M08] | math-simple | verified | 36m57s |
| 17 | [HM25] | hm-medium | solved | 2h14m |
| 18 | [HM30] | hm-hard | verified | 1h24m |
| 19 | [M40] | math-project | verified | 1h01m |
| 20 | ▶ [M25] | math-medium | verified | 12m53s |
| 21 | [HM91] | hm-research | solved | 2h10m |
| 22 | [M39] | math-project | verified | 1h12m |
| 23 | ▶ [HM30] | hm-hard | solved | 9m15s |
| 24 | [M28] | math-hard | solved | 28m07s |
| 25 | [M30] | math-hard | verified | 52m41s |
| 26 | [M21] | math-medium | verified | 14m10s |
| 27 | [M24] | math-medium | solved | 28m46s |
| 28 | [M43] | math-project | solved | 9m32s |
| 29 | [HM25] | hm-medium | verified | 1h15m |
| 30 | [M41] | math-project | verified | 1h23m |
| 31 | [HM30] | hm-hard | verified | 4h31m |
| 32 | [HM21] | hm-medium | verified | 13m11s |
| 33 | [M25] | math-medium | verified | 19m22s |
| 34 | [25] | medium | solved | 4h28m |
| 35 | ▶ [30] | hard | verified | 2h22m |
| 36 | [HM27] | hm-hard | verified | 1h02m |
| 37 | [M20] | math-medium | verified | 43m02s |
| 38 | ▶ [M30] | math-hard | verified | 44m57s |
| 39 | [M38] | math-project | solved | 26m44s |
| 40 | [HM43] | hm-project | solved | 1h54m |
| 41 | [25] | medium | verified | 9m20s |
| 42 | ▶ [30] | hard | solved | 1h40m |
| 43 | [35] | hard | solved | 41m33s |
| 44 | [M37] | math-project | solved | 27m06s |
TAOCP 5.1.4 Exercise 1
Let \begin{pmatrix} a_1&a_2&\cdots&a_9\\ b_1&b_2&\cdots&b_9 \end{pmatrix}
TAOCP 5.1.4 Exercise 2
For each entry $a_i$ of the permutation, let $t_i$ be the class defined in the text.
TAOCP 5.1.4 Exercise 3
Let $P$ be the tableau corresponding to a permutation $a_1 a_2 \dots a_m$.
TAOCP 5.1.4 Exercise 4
Let a permutation $\pi = a_1 a_2 \cdots a_{n^2}$ of $\{1,2,\dots,n^2\}$.
TAOCP 5.1.4 Exercise 5
We give a complete corrected proof by isolating the precise mechanism that guarantees both row and column inequalities during each bumping operation, without circular reasoning.
TAOCP 5.1.4 Exercise 6
Let Algorithm S be the full sequence of insertions described in Algorithm I applied successively, terminating with a tableau $P$ and a final added position $(r,s)$ determined at the last insertion ste...
TAOCP 5.1.4 Exercise 7
Let $P$ be a tableau of shape $(m_1,m_2,\dots,m_k)$, with $m_1 \ge m_2 \ge \dots \ge m_k > 0$.
TAOCP 5.1.4 Exercise 8
**Exercise 5.
TAOCP 5.1.4 Exercise 9
Let M= \begin{pmatrix} q_1&q_2&\cdots&q_n\\ p_1&p_2&\cdots&p_n
TAOCP 5.1.4 Exercise 10
Let N(a,b,c) denote the number of permutations of the multiset
TAOCP 5.1.4 Exercise 11
**Exercise 5.
TAOCP 5.1.4 Exercise 12
Let A(x_1,\ldots,x_n) denote the alternating polynomial introduced in this section.
TAOCP 5.1.4 Exercise 13
We work within the framework of Section 5.
TAOCP 5.1.4 Exercise 14
We state Theorem D(c) in the notation of Section 5.
TAOCP 5.1.4 Exercise 15
We are given the multiset \(M = \{1\cdot a,\; m\cdot b,\; n\cdot c\}\) and we want to count its permutations that satisfy the following prefix condition: > reading the permutation from left to right,...
TAOCP 5.1.4 Exercise 16
The partial ordering (39) is defined on the pairs \((q_i, p_i)\) of the two-line array \[ \begin{pmatrix} q_1 & q_2 & \cdots & q_n \\ p_1 & p_2 & \cdots & p_n \end{pmatrix} = \begin{pmatrix} 1 & 3 & 5...
TAOCP 5.1.4 Exercise 17
Let \(\Delta(x_1,\dots,x_n)\) denote the Vandermonde determinant \[ \Delta(x_1,\dots,x_n)=\prod_{1\le i<j\le n}(x_j-x_i).
TAOCP 5.1.4 Exercise 18
Let $\Delta(x_1,\dots,x_n)$ denote the Vandermonde determinant We are to evaluate, for $m\ge 0$, the sum Consider the Vandermonde matrix
TAOCP 5.1.4 Exercise 19
We are asked for the number of ways to fill an array whose first row has \(n_1-2\) boxes, second row \(n_2\) boxes, third row \(n_3\) boxes, …, with the numbers \(1,2,\dots,N-2\) (where \(N=n_1+\cdots...
TAOCP 5.1.4 Exercise 20
Let \(T\) be a rooted tree with \(n\) nodes.
TAOCP 5.1.4 Exercise 21
Let \(\lambda = (n_1, n_2, \dots, n_m)\) be a **strict partition**, i.
TAOCP 5.1.4 Exercise 22
**Solution** Let \(\lambda = (n_1, n_2, \dots, n_m)\) be a partition with \(n_1 \ge n_2 \ge \dots \ge n_m \ge 1\).
TAOCP 5.1.4 Exercise 23
The array consists of two rows, each containing \(m\) cells; hence the total number of cells is \(n = 2m\).
TAOCP 5.1.4 Exercise 24
We consider the sum \[ S = \sum_{\substack{q_1+\cdots+q_m = n \\ 0\le q_1,\ldots,q_m\le n}} \binom{m}{q_1}\cdots\binom{m}{q_m}\,\Delta(q_1,\ldots,q_m)^2, \] where \(\Delta(q_1,\ldots,q_m)=\prod_{1\le...
TAOCP 5.1.4 Exercise 25
By Theorem A in this section, there is a bijection between permutations of \(\{1,2,\ldots,n\}\) and ordered pairs \((P,Q)\) of standard Young tableaux of the same shape.
TAOCP 5.1.4 Exercise 26
We evaluate the integral \[ I_t = \int_{-\infty}^{\infty} x^t \exp(-2x^2) \sqrt{n} \, dx, \] where \(t\) is a nonnegative integer and \(n > 0\) is a constant.
TAOCP 5.1.4 Exercise 27
Let \(Q\) be a standard Young tableau on \(\{1,2,\dots,n\}\).
TAOCP 5.1.4 Exercise 28
Let \(S_n\) be the symmetric group on \(\{1,2,\ldots,n\}\).
TAOCP 5.1.4 Exercise 29
**Solution** Let \(\pi\) be a uniformly random permutation of \(\{1,2,\dots,n\}\).
TAOCP 5.1.4 Exercise 30
Let \(P\) be a finite partially ordered set (poset) with \(n\) elements.
TAOCP 5.1.4 Exercise 31
We place \(n\) mutually nonattacking rooks on an \(n\times n\) board, which corresponds to a permutation \(\pi\) of \(\{1,\dots,n\}\) with a rook at \((i,\pi(i))\).
TAOCP 5.1.4 Exercise 32
Let \(X\) be a normal random variable with mean \(1\) and variance \(1\).
TAOCP 5.1.4 Exercise 33
The statement is **true**.
TAOCP 5.1.4 Exercise 34
A **tableau shape** (or Young diagram) is a finite set of cells $\lambda \subset \mathbb{N}^2$ such that $(i,j) \in \lambda$ implies $(i',j') \in \lambda$ for all $1 \le i' \le i$, $1 \le j' \le j$.
TAOCP 5.1.4 Exercise 35
Let \(\lambda\) be a Ferrers shape with row lengths \(n_1 \ge n_2 \ge \cdots \ge n_{n'_1} > 0\) and column lengths \(n'_1 \ge n'_2 \ge \cdots \ge n'_{n_1} > 0\).
TAOCP 5.1.4 Exercise 36
**Solution** Let \(\lambda\) be a fixed Young diagram with \(n\) cells.
TAOCP 5.1.4 Exercise 37
A plane partition is an infinite array of nonnegative integers \(p_{ij}\) \((i,j\ge 1)\) satisfying \[ p_{ij} \ge p_{i+1,j},\qquad p_{ij} \ge p_{i,j+1} \] for all \(i,j\), with only finitely many nonz...
TAOCP 5.1.4 Exercise 38
Let \(T\) be a Young diagram (tableau shape) with \(n = |T|\) cells.
TAOCP 5.1.4 Exercise 39
We need to solve exercise 39 from TAOCP Volume 3, Section 5.
TAOCP 5.1.4 Exercise 40
**Solution to Exercise 40 (HM43)** We analyze the random process that builds a standard Young tableau by inserting the numbers \(1,2,\ldots,n\) one at a time.
TAOCP 5.1.4 Exercise 41
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.
TAOCP 5.1.4 Exercise 42
We consider the two gene orders as signed permutations of the set $\{g_1,g_2,g_3,g_4,g_5,g_6,g_7\}$, where the superscript $B$ denotes the reverse orientation.