OFFSET
0,3
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.
LINKS
Tilman Piesk, Table of n, a(n) for n = 0..5039
Wikipedia, Inversion (discrete mathematics)
EXAMPLE
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Tilman Piesk, Jun 03 2012
STATUS
approved