TAOCP 5.1: Combinatorial Properties of Permutations

Section 5.1 exercises: 4/4 solved.

4 items

Section 5.1. Combinatorial Properties of Permutations

Exercises from TAOCP Volume 3 Section 5.1: 4/4 solved.

#	Rating	Status	Time
1	[**]	solved	40m04s
2	[**]	verified	4m32s
3	[**]	verified	18m15s
4	[**]	solved	3m09s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1: Combinatorial Properties of Permutations ›

TAOCP 5.1 Exercise 1

Let the inversion table of a permutation $a_1a_2\cdots a_n$ be the sequence $b_1b_2\cdots b_n$, where $b_i$ is the number of entries greater than $i$ that occur to the left of $i$ in the permutation.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1: Combinatorial Properties of Permutations ›

TAOCP 5.1 Exercise 2

Let the Josephus elimination process produce the sequence $x_1,x_2,\dots,x_n$, where $x_k$ is the label removed at step $k$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1: Combinatorial Properties of Permutations ›

TAOCP 5.1 Exercise 3

Store the permutation in an array $P$ such that $P(j)$ is the position of $j$ in the permutation.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.1: Combinatorial Properties of Permutations ›

TAOCP 5.1 Exercise 4

We start from the standard interpretation of inversions in a permutation $a_1 a_2 \dots a_n$, where an inversion is a pair $(i,j)$ with $i<j$ and $a_i>a_j$.