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