login
Inversion sets of finite permutations interpreted as binary numbers.
4

%I #10 Jun 08 2012 20:15:32

%S 0,1,4,3,6,7,32,33,20,11,22,15,48,41,52,43,30,31,56,57,60,59,62,63,

%T 512,513,516,515,518,519,288,289,148,75,150,79,304,297,180,107,158,95,

%U 312,313,188,123,190,127,768,769,644,579,646,583,800

%N Inversion sets of finite permutations interpreted as binary numbers.

%C 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.

%C 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.

%C 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.

%H Tilman Piesk, <a href="/A211362/b211362.txt">Table of n, a(n) for n = 0..5039</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Inversion_%28discrete_mathematics%29">Inversion (discrete mathematics)</a>

%e 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.

%e 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.

%e Beginning of corresponding array:

%e n permutation inversion set a(n)

%e 00 1 2 3 4 0 0 0 0 0 0 0

%e 01 2 1 3 4 1 0 0 0 0 0 1

%e 02 1 3 2 4 0 0 1 0 0 0 4

%e 03 3 1 2 4 1 1 0 0 0 0 3

%e 04 2 3 1 4 0 1 1 0 0 0 6

%e 05 3 2 1 4 1 1 1 0 0 0 7

%e 06 1 2 4 3 0 0 0 0 0 1 32

%e 07 2 1 4 3 1 0 0 0 0 1 33

%e 08 1 4 2 3 0 0 1 0 1 0 20

%e 09 4 1 2 3 1 1 0 1 0 0 11

%e 10 2 4 1 3 0 1 1 0 1 0 22

%e 11 4 2 1 3 1 1 1 1 0 0 15

%e 12 1 3 4 2 0 0 0 0 1 1 48

%e 13 3 1 4 2 1 0 0 1 0 1 41

%e 14 1 4 3 2 0 0 1 0 1 1 52

%e 15 4 1 3 2 1 1 0 1 0 1 43

%e 16 3 4 1 2 0 1 1 1 1 0 30

%e 17 4 3 1 2 1 1 1 1 1 0 31

%e 18 2 3 4 1 0 0 0 1 1 1 56

%e 19 3 2 4 1 1 0 0 1 1 1 57

%e 20 2 4 3 1 0 0 1 1 1 1 60

%e 21 4 2 3 1 1 1 0 1 1 1 59

%e 22 3 4 2 1 0 1 1 1 1 1 62

%e 23 4 3 2 1 1 1 1 1 1 1 63

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

%K nonn

%O 0,3

%A _Tilman Piesk_, Jun 03 2012