A211362 Inversion sets of finite permutations interpreted as binary numbers.

0, 1, 4, 3, 6, 7, 32, 33, 20, 11, 22, 15, 48, 41, 52, 43, 30, 31, 56, 57, 60, 59, 62, 63, 512, 513, 516, 515, 518, 519, 288, 289, 148, 75, 150, 79, 304, 297, 180, 107, 158, 95, 312, 313, 188, 123, 190, 127, 768, 769, 644, 579, 646, 583, 800

Offset: 0

Author

Tilman Piesk, Jun 03 2012

Keywords

• nonn

Comments

Each finite permutation has a finite inversion set. The possible elements of the inversion sets are 2-element subsets of the integers, which can be ordered in an infinite sequence (compare A018900). Thus the inversion set can be represented by a binary vector, which can be interpreted as a binary number.

This sequence shows these numbers for the finite permutations in reverse colexicographic order (A055089, A195663). The corresponding inversion vectors are found in A007623. The corresponding inversion numbers (A034968) are the digit sums of the inversion vectors and the cardinality of the inversion sets, an thus also the binary digit sums of the numbers in this sequence.

This sequence is not monotonic. The permutation A211363 shows how the elements of this sequence (a) are ordered. a*A211363 gives the elements of a ordered by size.

Examples

			The 4th finite permutation (2,3,1,4,...) has the inversion set {(1,3),(2,3)}. This set represented by a vector is (0,1,1,zeros...). This vector interpreted as a number is 6. So a(4)=6.
The 23rd finite permutation (4,3,2,1,...) has the inversion set {(1,2),(1,3),(2,3),(1,4),(2,4),(3,4)}. This set represented by a vector is (1,1,1,1,1,1,zeros...). This vector interpreted as a number is 63. So a(23)=63.
Beginning of corresponding array:
n    permutation   inversion set    a(n)
00     1 2 3 4     0  0 0  0 0 0     0
01     2 1 3 4     1  0 0  0 0 0     1
02     1 3 2 4     0  0 1  0 0 0     4
03     3 1 2 4     1  1 0  0 0 0     3
04     2 3 1 4     0  1 1  0 0 0     6
05     3 2 1 4     1  1 1  0 0 0     7
06     1 2 4 3     0  0 0  0 0 1    32
07     2 1 4 3     1  0 0  0 0 1    33
08     1 4 2 3     0  0 1  0 1 0    20
09     4 1 2 3     1  1 0  1 0 0    11
10     2 4 1 3     0  1 1  0 1 0    22
11     4 2 1 3     1  1 1  1 0 0    15
12     1 3 4 2     0  0 0  0 1 1    48
13     3 1 4 2     1  0 0  1 0 1    41
14     1 4 3 2     0  0 1  0 1 1    52
15     4 1 3 2     1  1 0  1 0 1    43
16     3 4 1 2     0  1 1  1 1 0    30
17     4 3 1 2     1  1 1  1 1 0    31
18     2 3 4 1     0  0 0  1 1 1    56
19     3 2 4 1     1  0 0  1 1 1    57
20     2 4 3 1     0  0 1  1 1 1    60
21     4 2 3 1     1  1 0  1 1 1    59
22     3 4 2 1     0  1 1  1 1 1    62
23     4 3 2 1     1  1 1  1 1 1    63
		

Links

• Tilman Piesk, Table of n, a(n) for n = 0..5039
• Wikipedia, Inversion (discrete mathematics)

Crossrefs

Cf. A018900, A055089, A195663, A034968, A211363.