login
Triangle of compressed square roots of Gray code * bit-reversal permutation.
2

%I #32 Dec 17 2017 03:17:26

%S 1,3,1,6,1,5,6,9,1,10,12,18,1,17,10,12,18,33,1,34,20,24,36,66,1,65,34,

%T 20,24,36,66,129,1,130,68,40,48,72,132,258,1,257,130,68,40,48,72,132,

%U 258,513,1,514,260,136,80

%N Triangle of compressed square roots of Gray code * bit-reversal permutation.

%C The permutation that turns a natural ordered into a sequency ordered Walsh matrix of size 2^n is the product of the Gray code permutation A003188(0..2^n-1) and the bit-reversal permutation A030109(n,0..2^n-1).

%C (This permutation of 2^n elements can be represented by the compression vector [2^(n-1), 3*[2^(n-2)..4,2,1]] with n elements.)

%C This triangle shows the compression vectors of the unique square roots of these permutations, which correspond to symmetric binary matrices with 2n-1 ones.

%C (These n X n matrices correspond to graphs that can be described by permutations of n elements, which are shown in A239304.)

%C Rows of the square array:

%C T(1,n) = 1,3,6,6,12,12,24,24,48,48,96,96,192,192,384,384,... (compare A003945)

%C T(2,n) = 1,1,9,18,18,36,36,72,72,144,144,288,288,576,576,... (compare A005010)

%C Columns of the square array:

%C T(m,1) = 1,1,5,10,10,20,20,40,40,80,80,160,160,320,320,... (compare A146523)

%C T(m,2) = 3,1,1,17,34,34,68,68,136,136,272,272,544,544,... (compare A110287)

%H Tilman Piesk, <a href="/A239303/b239303.txt">First 140 rows of the triangle, flattened</a>

%H Tilman Piesk, <a href="https://en.wikiversity.org/wiki/Walsh_permutation;_sequency_ordered_Walsh_matrix">Sequency ordered Walsh matrix</a> (Wikiversity)

%H Tilman Piesk, <a href="http://pastebin.com/XDhZLaGy">Calculation in MATLAB</a>

%e Triangular array begins:

%e 1

%e 3 1

%e 6 1 5

%e 6 9 1 10

%e 12 18 1 17 10

%e 12 18 33 1 34 20

%e Square array begins:

%e 1 3 6 6 12 12

%e 1 1 9 18 18 36

%e 5 1 1 33 66 66

%e 10 17 1 1 129 258

%e 10 34 65 1 1 513

%e 20 34 130 257 1 1

%e The Walsh permutation wp(8,12,6,3) = (0,8,12,4, 6,14,10,2, 3,11,15,7, 5,13,9,1) permutes the natural ordered into the sequency ordered Walsh matrix of size 2^4.

%e Its square root is wp(6,9,1,10) = (0,6,9,15, 1,7,8,14, 10,12,3,5, 11,13,2,4).

%e So row 4 of the triangular array is (6,9,1,10).

%Y Cf. A239304, A003188, A030109.

%K nonn,tabl

%O 1,2

%A _Tilman Piesk_, Mar 14 2014