TAOCP 5.1.3: Runs

Section 5.1.3 exercises: 14/14 solved.

14 items

Section 5.1.3. Runs

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

#	Rating	Category	Status	Time
1	[**]		verified	48m06s
2	[**]		solved	4m38s
3	[**]		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

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).