TAOCP 5.1.1: Inversions

Section 5.1.1 exercises: 29/29 solved.

29 items

Section 5.1.1. Inversions

Exercises from TAOCP Volume 3 Section 5.1.1: 29/29 solved.

#	Rating	Category	Status	Time
1	[10]	simple	verified	48m13s
2	[M20]	math-medium	solved	55m43s
3	[18]	medium	solved	35m40s
4	▶ [20]	medium	verified	34m29s
5	[35]	hard	verified	10m50s
6	▶ [26]	hard	verified	7m22s
7	[30]	hard	verified	17m27s
8	[M24]	math-medium	verified	24m33s
9	[M21]	math-medium	verified	22m
10	[HM20]	hm-medium	verified	11m52s
11	[M25]	math-medium	verified	8m54s
12	[M28]	math-hard	verified	17m06s
13	[M23]	math-medium	verified	6m41s
14	[M22]	math-medium	verified	1h07m
15	[M25]	math-medium	verified	8m12s
16	[M25]	math-medium	verified	23m53s
17	[39]	project	solved	1h20m
18	[M30]	math-hard	verified	1h29m
19	[M28]	math-hard	verified	1h03m
20	[M41]	math-project	solved	26m31s
21	▶ [M25]	math-medium	verified	1h25m
22	▶ [M26]	math-hard	verified	1h06m
23	▶ [M27]	math-hard	verified	57m13s
24	[M26]	math-hard	solved	22m
25	[M30]	math-hard	verified	2h00m
26	[M25]	math-medium	verified	17m07s
27	[M37]	math-project	verified	1h34m
28	▶ [25]	medium	verified	1h44m
29	[28]	hard	verified	1h05m

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 1

Let the permutation be written in one-line form $a_1 a_2 \cdots a_9$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 2

**Corrected Solution for Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 3

Let $p_i$ denote the position of the element $i$ in the permutation, so that $a_{p_i}=i$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 4

**Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 5

We need to solve Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 6

Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 7

Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 8

We adopt the notation of the text and Exercise 7.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 9

Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$ and let $a'_1 a'_2 \ldots a'_n$ be its inverse, so that $a'_k$ is the position of $k$ in $a$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 10

The truncated octahedron in Figure 1 is the permutohedron of order 4.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 11

Let $T = \{(x,y) \mid 1 \le y < x \le n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 12

Let $T = \{(x,y) \mid 1 \le y < x \le n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 13

Let $I_n(k)$ denote the number of permutations of $\{1,2,\ldots,n\}$ with exactly $k$ inversions.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 14

A partition of $n$ into $k$ distinct parts is a sequence $p_1 > p_2 > \cdots > p_k \ge 1$ with $\sum_{i=1}^k p_i = n$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

We want to prove that the coefficient of $z^m$ in \[ \frac{1}{(1-z)(1-z^2)\cdots(1-z^n)} \] equals the number of sequences $(p_1, p_2, \ldots, p_n)$ with $p_1 \ge p_2 \ge \cdots \ge p_n \ge 0$ a...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 16

The exercise as printed contains two typographical errors: 1.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 17

MacMahon's correspondence, described at the end of §5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 18

We are given a sequence of $N = 2^n$ independent random $n$-bit integers $X_0, X_1, \ldots, X_{N-1}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 19

Let $n > 1$ be an integer and let $m$ be an integer with $\gcd(m,n)=1$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 20

A **complex partition** of the Gaussian integer $m+ni$ is a set of distinct parts of the form $p+qi$ with $p,q\ge 0$ and $|p-q|\le 1$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 21

**Solution** We begin by recalling the relevant definitions.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 22

Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 23

We have $n$ men numbered $1,2,\dots,n$ sitting in a circle in increasing order clockwise.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 24

Let $f:\{1,\dots,n\}\to\{1,\dots,n\}$ be a function satisfying $f(j)\ge j$ for all $j$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 25

**Solution to Exercise 25 (Foata and Schützenberger)** Let $\alpha = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 26

Let $\pi = a_1 a_2 \ldots a_n$ be a uniformly random permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 27

Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 28

Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.1: Inversions ›

TAOCP 5.1.1 Exercise 29

Let $\pi = a_1 a_2 \ldots a_n$ and $\pi' = a'_1 a'_2 \ldots a'_n$ be permutations of $\{1,2,\ldots,n\}$.

TAOCP 5.1.1: Inversions

Section 5.1.1. Inversions

TAOCP 5.1.1 Exercise 1

TAOCP 5.1.1 Exercise 2

TAOCP 5.1.1 Exercise 3

TAOCP 5.1.1 Exercise 4

TAOCP 5.1.1 Exercise 5

TAOCP 5.1.1 Exercise 6

TAOCP 5.1.1 Exercise 7

TAOCP 5.1.1 Exercise 8

TAOCP 5.1.1 Exercise 9

TAOCP 5.1.1 Exercise 10

TAOCP 5.1.1 Exercise 11

TAOCP 5.1.1 Exercise 12

TAOCP 5.1.1 Exercise 13

TAOCP 5.1.1 Exercise 14

TAOCP 5.1.1 Exercise 15

TAOCP 5.1.1 Exercise 16

TAOCP 5.1.1 Exercise 17

TAOCP 5.1.1 Exercise 18

TAOCP 5.1.1 Exercise 19

TAOCP 5.1.1 Exercise 20

TAOCP 5.1.1 Exercise 21

TAOCP 5.1.1 Exercise 22

TAOCP 5.1.1 Exercise 23

TAOCP 5.1.1 Exercise 24

TAOCP 5.1.1 Exercise 25

TAOCP 5.1.1 Exercise 26

TAOCP 5.1.1 Exercise 27

TAOCP 5.1.1 Exercise 28

TAOCP 5.1.1 Exercise 29