A195665 - OEIS

%I #71 Dec 17 2017 03:14:35

%S 0,1,0,2,1,3,0,1,4,5,2,3,6,7,0,2,4,6,1,3,5,7,0,4,1,5,2,6,3,7,0,4,2,6,

%T 1,5,3,7,0,1,2,3,8,9,10,11,4,5,6,7,12,13,14,15,0,2,1,3,8,10,9,11,4,6,

%U 5,7,12,14,13,15,0,1,4,5,8,9,12

%N Consecutive bit-permutations of nonnegative integers.

%C All rows of this array are infinite permutations of the nonnegative integers. Row m (counted from 0) is always generated by modifying the sequence of nonnegative integers in the following way: The sequence of integers is written in reverse binary. Than the finite permutation p_m (row m of array A055089) is applied on the digits of all entries.

%C The rows of the top left n! X 2^n submatrix describe the rotations and reflections of the n-hypercube that preserve the binary digit sums of the vertex numbers. With permutation composition these permutations form the symmetric group S_n.

%C Applying such a permutation on the binary string of a Boolean function gives the string of a function in the same big equivalence class (compare A227723).

%C Triangle row m has length 2^n for m in the interval [(n-1)!,n![. The rest of the array row repeats the same pattern. The first digit of the rest is the digit before plus one.

%H Tilman Piesk, <a href="/A195665/b195665.txt">First 120 rows of the triangle, flattened</a>

%H Tilman Piesk, <a href="/A195665/a195665.txt">120x32 top left submatrix</a> (human readable)

%H Tilman Piesk, <a href="/A195665/a195665_3.txt">720x64 top left submatrix</a> (computer readable)

%H Tilman Piesk, <a href="/A195665/a195665_4.txt">First 720 rows of the triangle</a>

%H Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Walsh_permutation;_bit_permutation">Bit-permutations</a> (Wikiversity)

%H Tilman Piesk, <a href="http://pastebin.com/2N7zha5C">MATLAB code</a>

%e Top left corner of array:

%e 0 1 2 3 4 5 6 7

%e 0 2 1 3 4 6 5 7

%e 0 1 4 5 2 3 6 7

%e 0 2 4 6 1 3 5 7

%e 0 4 1 5 2 6 3 7

%e 0 4 2 6 1 5 3 7

%e The entry in row 2, column 5 (both counted from 0) is 3: 5 in reverse binary is 101, permutation p_2 applied on 101 gives 110, 110 from reverse binary to decimal is 3.

%e Corresponding rows of the triangle:

%e 0 1

%e 0 2 1 3

%e 0 1 4 5 2 3 6 7

%e 0 2 4 6 1 3 5 7

%e 0 4 1 5 2 6 3 7

%e 0 4 2 6 1 5 3 7

%Y The finite permutations in A055089 are applied on the reverse binary digits.

%Y Row 0: A001477.

%Y Row 1: A080412.

%Y Row n!-1 of the triangle is the n-bit bit-reversal permutation. Compare A030109.

%K nonn,tabf

%O 0,4

%A _Tilman Piesk_, Sep 23 2011

%E Huge edit by _Tilman Piesk_, Aug 01 2013