A382250 Irregular 3-dimensional table, where layer n is an irregular 2D table with A000041(n) columns, each of which lists the n-bit binary numbers whose run lengths correspond to a given partition.

0, 0, 0, 1, 0, 1, 3, 2, 0, 1, 7, 2, 4, 6, 3, 5, 0, 1, 15, 2, 8, 14, 3, 7, 4, 6, 12, 5, 9, 11, 13, 10, 0, 1, 31, 2, 16, 30, 3, 15, 4, 6, 8, 14, 24, 28, 5, 17, 23, 29, 7, 9, 11, 13, 19, 25, 27, 10, 18, 20, 22, 26, 12, 21, 0, 1, 63, 2, 32, 62, 3, 31, 4, 6, 16, 30, 48, 60, 5, 33, 47, 61, 7, 15, 8, 14

Offset: 0

Author

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

Keywords

• nonn

Comments

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.

Examples

			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
		

Crossrefs

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

Programs

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}

Formula

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.