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

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, 20, 24, 36, 66, 129, 1, 130, 68, 40, 48, 72, 132, 258, 1, 257, 130, 68, 40, 48, 72, 132, 258, 513, 1, 514, 260, 136, 80

Offset: 1

Author

Tilman Piesk, Mar 14 2014

Keywords

• nonn
• tabl

Comments

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).

(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.)

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

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

Rows of the square array:

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

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

Columns of the square array:

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

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

Examples

			Triangular array begins:
   1
   3   1
   6   1   5
   6   9   1  10
  12  18   1  17  10
  12  18  33   1  34  20
Square array begins:
   1   3   6   6  12  12
   1   1   9  18  18  36
   5   1   1  33  66  66
  10  17   1   1 129 258
  10  34  65   1   1 513
  20  34 130 257   1   1
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.
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).
So row 4 of the triangular array is (6,9,1,10).
		

Links

• Tilman Piesk, First 140 rows of the triangle, flattened
• Tilman Piesk, Sequency ordered Walsh matrix (Wikiversity)
• Tilman Piesk, Calculation in MATLAB

Crossrefs

Cf. A239304, A003188, A030109.