TAOCP 5.1.3: Runs

Section 5.1.3 exercises: 29/29 solved.

29 items

Section 5.1.3. Runs

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

#	Rating	Category	Status	Time
1	[M26]	math-hard	verified	48m06s
2	▶ [M22]	math-medium	solved	4m38s
3	[HM25]	hm-medium	verified	17m38s
4	[M21]	math-medium	solved	1h11m
5	[M20]	math-medium	verified	1m48s
6	▶ [M21]	math-medium	verified	36m38s
7	[HM40]	hm-project	verified	1m57s
8	[M24]	math-medium	solved	1h02m
9	[M30]	math-hard	verified	46m09s
10	[HM30]	hm-hard	verified	51m13s
11	[M40]	math-project	verified	45m11s
12	[M33]	math-hard	solved	2m38s
13	[05]	simple	solved	1m48s
14	[M18]	math-medium	solved	4m24s
15	▶ [M21]	math-medium	verified	10m41s
16	[M30]	math-hard	solved	18m
17	[M25]	math-medium	verified	17m
18	[M28]	math-hard	verified	38m47s
19	▶ [M26]	math-hard	verified	27m39s
20	▶ [M21]	math-medium	verified	17m49s
21	[M22]	math-medium	verified	16m51s
22	[M46]	math-research	solved	38m44s
23	[HM42]	hm-project	solved	21m01s
24	[M30]	math-hard	verified	48m37s
25	[M25]	math-medium	verified	12m27s
26	[M20]	math-medium	verified	18m35s
27	▶ [M21]	math-medium	verified	13m49s
28	[HM35]	hm-hard	verified	1h40m
29	▶ [HM30]	hm-hard	solved	37m58s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 1

**Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 2

The claim is that for integers $n,k,q>0$, \binom{n}{q}\binom{k}{q}\in \mathbb{Z}.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 3

Using the binomial theorem, (1-1)^n=\sum_{k=0}^{n}\binom{n}{k}1^{\,n-k}(-1)^k =\sum_{k=0}^{n}\binom{n}{k}(-1)^k .

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 4

**Corrected Solution to Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 5

Let $p$ be a prime.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 6

The mistake is that Mr.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 7

Let $X_n$ denote the number of descents in a random permutation of ${1,2,\dots,n}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 8

**Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 9

Let a **run** in a permutation be a maximal increasing sequence of consecutive elements.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 10

h_k(z)=\sum_{m\ge k}p_{km}z^m is the probability generating function of the total length S_k=L_1+\cdots+L_k

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 11

**Exercise 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 12

Let the multiset be M=\{n_1\cdot 1,\; n_2\cdot 2,\; \ldots,\; n_m\cdot m\}, \qquad n=n_1+\cdots+n_m.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 13

Let $X_1 X_2 \cdots X_{52}$ be the sequence of suits obtained from a uniformly random permutation of a multiset containing $13$ clubs, $13$ diamonds, $13$ hearts, and $13$ spades, ordered $C<D<H<S$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 14

Let w = 3111231423342244 a word on $\{1,2,3,4\}$ having 5 runs (maximal weakly increasing consecutive blocks).

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 15

Let $R$ be the number of alternating runs in a random permutation $a_1 a_2 \ldots a_n$ of $\{1,2,\ldots,n\}$, with $n \ge 2$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 16

We follow the definition of alternating runs given in Exercise 15.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

We are asked to count the binary sequences $a_1 a_2 \ldots a_n$ (each $a_j \in \{0,1\}$) that contain exactly $k$ runs, where a run is defined by the condition that there are exactly $k-1$ ind...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 18

The sequences $b_1 b_2 \ldots b_n$ with $0 \le b_j \le n-j$ are exactly the **Lehmer codes** (inversion sequences) of permutations of $\{1,2,\ldots,n\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 19

An $n \times n$ chessboard has rows and columns indexed $1,2,\dots,n$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 20

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.3: Runs ›

TAOCP 5.1.3 Exercise 21

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.3: Runs ›

TAOCP 5.1.3 Exercise 22

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.3: Runs ›

TAOCP 5.1.3 Exercise 23

We need to solve Exercise 23 from Section 5.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 24

The Eulerian number $\left\langle {n \atop k} \right\rangle$ is defined as the number of permutations of $\{1,2,\ldots,n\}$ with exactly $k$ descents (and therefore exactly $k+1$ ascending run...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 25

Let $S_n = U_1 + \cdots + U_n$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 26

Let $\vartheta = z \frac{d}{dz}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 27

Let $F(n,k)$ denote the number of increasing forests on the vertex set $\{1,2,\dots,n\}$ that have exactly $k+1$ leaves.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 28

The expected length $z_m$ of the $m$th ascending run in a random infinite sequence of distinct numbers is \[ z_m = \sum_{k=m}^{\infty} \frac{1}{k!

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1.3: Runs ›

TAOCP 5.1.3 Exercise 29

Let $s_{nk}$ denote the number of permutations $a_1a_2\ldots a_n$ of $\{1,2,\ldots,n\}$ that contain exactly $k$ peaks and exactly $k$ descents.

TAOCP 5.1.3: Runs

Section 5.1.3. Runs

TAOCP 5.1.3 Exercise 1

TAOCP 5.1.3 Exercise 2

TAOCP 5.1.3 Exercise 3

TAOCP 5.1.3 Exercise 4

TAOCP 5.1.3 Exercise 5

TAOCP 5.1.3 Exercise 6

TAOCP 5.1.3 Exercise 7

TAOCP 5.1.3 Exercise 8

TAOCP 5.1.3 Exercise 9

TAOCP 5.1.3 Exercise 10

TAOCP 5.1.3 Exercise 11

TAOCP 5.1.3 Exercise 12

TAOCP 5.1.3 Exercise 13

TAOCP 5.1.3 Exercise 14

TAOCP 5.1.3 Exercise 15

TAOCP 5.1.3 Exercise 16

TAOCP 5.1.3 Exercise 17

TAOCP 5.1.3 Exercise 18

TAOCP 5.1.3 Exercise 19

TAOCP 5.1.3 Exercise 20

TAOCP 5.1.3 Exercise 21

TAOCP 5.1.3 Exercise 22

TAOCP 5.1.3 Exercise 23

TAOCP 5.1.3 Exercise 24

TAOCP 5.1.3 Exercise 25

TAOCP 5.1.3 Exercise 26

TAOCP 5.1.3 Exercise 27

TAOCP 5.1.3 Exercise 28

TAOCP 5.1.3 Exercise 29