0,7

The n-th layer contains the 2^(n-1) numbers from 0 to 2^(n-1)-1, each of which corresponds, through the run lengths of the digits when written with n bits, uniquely to one of the 2^(n-1) compositions of n. (For example, 000 <=> 3, 001 <=> 2+1; 010 <=> 1+1+1.) The numbers are grouped together in columns which correspond to the distinct partitions of n, so there are A000041(n) of these, where A000041 are the partition numbers.

Numbers that will never be in a top row are listed in A175021 = 6, 11, 13, 14, 20, 22, 23, 25, 26, 27, 28, 29, 30, 38, .... All other numbers will eventually be in a fixed position in the top row of all large enough layers.

If we denote by A(n, c, r) the r-th element of column number c in layer n, then

A(n, c, 1) = c-1 for 1 <= c <= min(n, 6); lim_{n -> oo} A(n, c+1, 1) = A175020(c).

A(n, 2, 2) = 2^(n-1) - 1 is the last element of column 2 for all n > 2.

A(n, 3, 2) = 2^(n-2), and A(n, 3, 3) = 2^(n-1) - 2 is the last element of column 3 for all n > 3.

A(n, 4, 2) = 2^(n-2) - 1 is the last element of column 4 for all n > 4.

The table starts as follows:

n = 0: There is A000041(0) = 1 partition of 0, the empty partition, which equals the

run lengths of the empty sequence of digits of 0 written with 0 binary digits.

So there is 1 column with just one number, 0:

0

n = 1: Again there is A000041(1) = 1 partition of 1, so there is 1 column, which

contains the number 0 written with n = 1 bits, so that run lengths are (1):

0

n = 2: There are A000041(2) = 2 columns for the two partitions of 2; each column

contains one number: 0 = 00 <=> partition (2), resp. 1 = 01 <=> (1,1):

0 1

n = 3: There are A000041(3) = 3 columns for the three partitions of 3,

corresponding to the 2^2 = 4 compositions which are the run lengths of

0 = 000 <=> partition (3) in column 1,

1 = 001 and 3 = 011 (partition 2+1 = 1+2) in column 2,

and 2 = 010 (partition (1,1,1) or 1+1+1) in column 3:

0 1 2

3

n = 4: Here are A000041(4) = 5 columns for the five partitions of 4, corresponding

to 2^3 = 8 compositions of 4 given as run lengths of the numbers 0, ..., 7

written with 4 bits: Column 1 holds the number 0 = 0000 <=> partition (4),

column 2 holds the numbers 1 = 0001 and 7 = 0111 <=> partition 3+1 = 1+3,

column 3 holds 2 = 0010, 4 = 0100 and 6 = 0110 for 2+1+1 = 1+1+2 = 1+2+1,

column 4 holds 3 = 0011 for 2+2, and column 5 holds 5 = 0101 for 1+1+1+1:

0 1 2 3 5

7 4

6

n = 5: 0 1 2 3 4 5 10

15 8 7 6 9

14 12 11

13

n = 6: 0 1 2 3 4 5 7 9 10 12 21

31 16 15 6 17 11 18

30 8 23 13 20

14 29 19 22

24 25 26

28 27

(PARI) {layer(n)=my(M=Map(), C=[], p, i); for(k=1, 2^max(n-1, 0), mapisdefined(M, p=vecsort(A101211_row(2^n-k)), &i) || mapput(M, p, i=#C=concat(C, [[]])); C[i]=concat(C[i], k-1)); C}

Cf. A000041 (partition numbers), A000079 (powers of 2), A007088 (binary numbers), A101211 and A318927 (run lengths of binary numbers).

The number of columns of length 1 in layer n is A000005(n).

Cf. A175021 (numbers never in the first row), A175020 (limit of the first rows without initial 0).

Sequence in context: A365727 A054654 A355423 * A345066 A253669 A154477

Adjacent sequences: A382247 A382248 A382249 * A382251 A382252 A382253

Ali Sada and M. F. Hasler, Mar 24 2025

approved