cp's OEIS Frontend

A195665 Consecutive bit-permutations of nonnegative integers.

%I A195665 #71 Dec 17 2017 03:14:35
%S A195665 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 A195665 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 A195665 5,7,12,14,13,15,0,1,4,5,8,9,12
%N A195665 Consecutive bit-permutations of nonnegative integers.
%C A195665 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 A195665 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 A195665 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 A195665 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 A195665 Tilman Piesk, <a href="/A195665/b195665.txt">First 120 rows of the triangle, flattened</a>
%H A195665 Tilman Piesk, <a href="/A195665/a195665.txt">120x32 top left submatrix</a> (human readable)
%H A195665 Tilman Piesk, <a href="/A195665/a195665_3.txt">720x64 top left submatrix</a> (computer readable)
%H A195665 Tilman Piesk, <a href="/A195665/a195665_4.txt">First 720 rows of the triangle</a>
%H A195665 Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Walsh_permutation;_bit_permutation">Bit-permutations</a> (Wikiversity)
%H A195665 Tilman Piesk, <a href="http://pastebin.com/2N7zha5C">MATLAB code</a>
%e A195665 Top left corner of array:
%e A195665 0 1 2 3 4 5 6 7
%e A195665 0 2 1 3 4 6 5 7
%e A195665 0 1 4 5 2 3 6 7
%e A195665 0 2 4 6 1 3 5 7
%e A195665 0 4 1 5 2 6 3 7
%e A195665 0 4 2 6 1 5 3 7
%e A195665 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 A195665 Corresponding rows of the triangle:
%e A195665 0 1
%e A195665 0 2 1 3
%e A195665 0 1 4 5 2 3 6 7
%e A195665 0 2 4 6 1 3 5 7
%e A195665 0 4 1 5 2 6 3 7
%e A195665 0 4 2 6 1 5 3 7
%Y A195665 The finite permutations in A055089 are applied on the reverse binary digits.
%Y A195665 Row 0: A001477.
%Y A195665 Row 1: A080412.
%Y A195665 Row n!-1 of the triangle is the n-bit bit-reversal permutation. Compare A030109.
%K A195665 nonn,tabf
%O A195665 0,4
%A A195665 _Tilman Piesk_, Sep 23 2011
%E A195665 Huge edit by _Tilman Piesk_, Aug 01 2013