|
| |
|
|
A195665
|
|
Table read by antidiagonals: Consecutive bit-permutations of non-negative integers.
|
|
1
|
|
|
|
0, 1, 0, 2, 2, 0, 3, 1, 1, 0, 4, 3, 4, 2, 0, 5, 4, 5, 4, 4, 0, 6, 6, 2, 6, 1, 4, 0, 7, 5, 3, 1, 5, 2, 1, 0, 8, 7, 6, 3, 2, 6, 2, 2, 0, 9, 8, 7, 5, 6, 1, 3, 1, 1, 0, 10, 10, 8, 7, 3, 5, 8, 3, 4, 2, 0, 11, 9, 9, 8, 7, 3, 9, 8, 5, 4, 4, 0, 12, 11, 12, 10, 8, 7, 10, 10, 8, 6, 1, 4, 0, 13, 12, 13, 12, 12, 8, 11, 9, 9, 8, 5, 2, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
All rows are infinite permutations of the non-negative integers. Row m (counted from 0) is always generated by modifying the sequence of non-negative integers in the following way: The sequence of integers is written in reverse binary. Than the finite permutation p_m (A195664) is applied on the digits of all entries.
The rows of the top left n!x2^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.
Applying such a permutation on the binary string of a Boolean function gives the string of a related function in the same equivalence class of the kind counted by A000616. Let p_m be a finite permutation of n elements and P_m the corresponding permutation of 2^n elements, let s be arguments x_1,...,x_n and S the binary string of the n-ary Boolean function f(s). Than f(p_m(s)) has the binary string P_m(S).
|
|
|
LINKS
|
Tilman Piesk, Table of n, a(n) for n = 0..7259
Tilman Piesk, 120x32 top left submatrix (human readable)
Tilman Piesk, 720x64 top left submatrix (computer readable)
Tilman Piesk, Bit-permutations
Tilman Piesk, Example:Bit-permutations and Boolean functions
Tilman Piesk, MATLAB code from the calculation
|
|
|
EXAMPLE
|
Top left corner of array:
0 1 2 3 4 5 6 7
0 2 1 3 4 6 5 7
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 1 5 3 7
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.
|
|
|
CROSSREFS
|
The finite permutations in A195664 are applied on the reverse binary digits.
Row 0: A001477.
Row 1: A080412.
First 2^n digits of row n!-1 are the bit-reversal permutations, found also in block n (counted from 0) of A030109.
Sequence in context: A058648 A112174 A089990 * A071427 A093949 A108807
Adjacent sequences: A195662 A195663 A195664 * A195666 A195667 A195668
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Tilman Piesk, Sep 23 2011
|
|
|
STATUS
|
approved
|
| |
|
|
