Counting Inversions

Problem

Arrange nn (n2n \geqslant 2) distinct numbers in some order to form a sequence {an}\{a_n\}. For 1i<jn1 \leqslant i < j \leqslant n, if ai>aja_i > a_j, the pair (ai,aj)(a_i, a_j) is called an inversion of the sequence; the total number of inversions is the sequence's inversion number.

1. List all sequences formed from the numbers 1,2,3,41, 2, 3, 4 that have exactly 22 inversions. 2. Compute the inversion numbers of the following sequences:

  1. an=2n+19a_n = -2n + 19 for 1n1001 \leqslant n \leqslant 100;
  2. an={(13)n,n odd,nn+1,n evena_n = \begin{cases}\left(\dfrac{1}{3}\right)^n, & n \text{ odd},\\[4pt] -\dfrac{n}{n+1}, & n \text{ even}\end{cases} for 1nk1 \leqslant n \leqslant k.
  3. If the sequence a1,a2,,ana_1, a_2, \ldots, a_n has inversion number aa, find the inversion number of the reversed sequence an,an1,,a1a_n, a_{n-1}, \ldots, a_1.

Answer

Solution

Difficulty6/10
Topicscombinatorics, Counting, sequences, Casework, Symmetry

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments
Log in to join the discussion.

No comments yet.