A294648 -id:A294648 - cp's OEIS frontend

A356028 Irregular triangle {A(n, k)} read by rows, giving in row n the numbers 1, 2, ..., 2^n - 1 ordered according to increasing binary weights, and for like weights decreasing.

1, 2, 1, 3, 4, 2, 1, 6, 5, 3, 7, 8, 4, 2, 1, 12, 10, 9, 6, 5, 3, 14, 13, 11, 7, 15, 16, 8, 4, 2, 1, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3, 28, 26, 25, 22, 21, 19, 14, 13, 11, 7, 30, 29, 27, 23, 15, 31, 32, 16, 8, 4, 2, 1, 48, 40, 36, 34, 33, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3, 56, 52, 50, 49, 44, 42, 41, 38, 37, 35, 28, 26, 25, 22, 21, 19, 14, 13, 11, 7, 60, 58, 57, 54, 53, 51, 46, 45, 43, 39, 30, 29, 27, 23, 15, 62, 61, 59, 55, 47, 31, 63

Offset: 1

Wolfdieter Lang, Jul 27 2022

The length of row n is 2^n - 1 = A000225(n).
Also irregular triangle {A(n, k)} read by rows, giving in row n the numbers with a binary encoding of the list choose([n], m) = choose({1, 2,..., n}, m) (each encoding of length n), for n >= 1 and m = 1, 2, ..., n; written as entries for k = 1, 2, ..., 2^n - 1.
The binary encoding is obtained by setting 1s at the positions given by the choose([n],m) list of lists (in lexicographic order) and 0 otherwise. E.g., choose([3], 2) = [[1, 2], [1, 3], [2, 3]] with the encodings of length 3 [[1, 1, 0], [1, 0, 1], [0, 1, 1]], read as base 2 lists giving the numbers [6, 5, 3].
For the triangle T(n,m) of the sums of like m entries see A134346, (using offset 1).
The sum of row n gives A006516(n) = A171476(n-1), for n >= 1 (see A134346).

			The irregular triangle A begins (commas separate the n subsequences for m = 1, 2, ..., n, corresponding to the binary encoded choose(n, m) lists or binary weights m):
n\k   1 2  3  4   5  6  7  8 9 10  11 12 13 14  15 ...
1:    1
2:    2 1, 3
3:    4 2  1, 6   5  3, 7
4:    8 4  2  1, 12 10  9  6 5  3, 14 13 11  7, 15
...
n = 5: [16 8 4 2 1, 24 20 18 17 12 10 9 6 5 3, 28 26 25 22 21 19 14 13 11 7, 30 29 27 23 15, 31];
n = 6: [32 16 8 4 2 1, 48 40 36 34 33 24 20 18 17 12 10 9 6 5 3, 56 52 50 49 44 42 41 38 37 35 28 26 25 22 21 19 14 13 11 7, 60 58 57 54 53 51 46 45 43 39 30 29 27 23 15, 62 61 59 55 47 31, 63);
...
A(4, 2) gives the number with the binary representation of the choose([4], 2) list [[1,1,0,0], [1,0,1,0], [1,0,0,1], [0,1,1,0], [0,1,0,1], [0,0,1,1]], obtained from the list choose([4], 2) = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]], that is [12, 10, 9, 6, 5, 3].
A(4, 2) from the numbers 1, 2, ..., 15 with binary weight 2, that is of 3, 5, 6, 9, 10, 12, in decreasing order: 12, 10, 9, 6, 5, 3.

Paolo Xausa, Table of n, a(n) for n = 1..8178 (rows 1..12 of the triangle, flattened).

Cf. A000225, A006516, A134346, A171476, A262881, A294648.

A356028row[n_]:=SortBy[Range[2^n-1],{DigitCount[#,2,1]&,-#&}];
Array[A356028row,6] (* Paolo Xausa, Dec 20 2023 *)

cmph(x, y) = my(d=hammingweight(x)-hammingweight(y)); if (d, d, y-x);
row(n) = my(v=[1..2^n-1]); vecsort(v, cmph); \\ Michel Marcus, Sep 16 2023

Name suggested by Kevin Ryde.

A047869 Subsets of an 8-element set in order by number of elements in each subset.

Original entry on oeis.org

0, 1, 2, 4, 8, 16, 32, 64, 128, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100

Offset: 1

Joe Loughry (loughry(AT)uswest.net)

Subsets are represented by binary vectors.

			The analogous sequences for smaller k are as follows (rows of A294648 for k >= 1):
for k = 0: 0;
for k = 1: 0, 1;
for k = 2: 0, 1, 2, 3;
for k = 3: 0, 1, 2, 4, 3, 5, 6, 7;
for k = 4: 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 15;
for k = 5: 0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 15, 23, 27, 29, 30, 31.

Sean A. Irvine, Table of n, a(n) for n = 1..256
J. Loughry, Efficiently Enumerating the Subsets of a Set

Cf. A003188.

Row 8 of A294648.

SortBy[Range[0, 255], DigitCount[#, 2, 1] &] (* Paolo Xausa, Mar 31 2025 *)

Offset corrected by Sean A. Irvine, May 22 2021

A305860 Triangle m(n,k) read by rows (n >= 0, 0 <= k <= n): to get the binary expansion of m(n,k), for 0 <= i < 2^n, write 1 if the binary weight of i is equal to k or 0 otherwise, left to right.

Original entry on oeis.org

1, 2, 1, 8, 6, 1, 128, 104, 22, 1, 32768, 26752, 5736, 278, 1, 2147483648, 1753251840, 375941248, 18224744, 65814, 1, 9223372036854775808, 7530159316599308288, 1614655367130677248, 78274679833913472, 282668995843688, 4295033110, 1

Offset: 0

Valentin Bakoev, Jul 08 2018

Triangle read by rows, representing a family of sequences M(n), for n = 0, 1, 2, ... The n-th row of the triangle consists of n+1 integers, denoted by #m(n,0), #m(n,1), ..., #m(n,n), which are the terms of the sequence M(n). They are the serial numbers of n+1 binary vectors of size 2^n, denoted by m(n,0), m(n,1), ..., m(n,n), correspondingly. Each vector m(n,k) is a characteristic vector of all vectors from the n-dimensional Boolean cube (hypercube) {0,1}^n, having (Hamming) weight equal to k, for k = 0, 1, ..., n, and for n > 0. The zeroth row (i.e., M(0)) and its single term 1 are prepended for convenience.
The n-th row (i.e., the sequence M(n)) represents the vectors of equal (Hamming) weights of the n-dimensional Boolean cube (hypercube) {0,1}^n, for n = 1, 2, ... A serial number of the vector a_i = (a_1, a_2, ..., a_n) of {0,1}^n is denoted by #a_i and it is the natural number whose n-bit binary representation is a_1, a_2, ..., a_n. When the vectors of {0,1}^n are in lexicographic order, their serial numbers form the sequence 0, 1, 2, ..., 2^n-1. The sequence M(n) has n+1 terms, denoted by #m(n,0), #m(n,1), ..., #m(n,n). Here #m(n,k) is the natural number corresponding to the binary vector m(n,k) of size 2^n, for k = 0, 1, ..., n. The i-th coordinate of m(n,k) is unit if the weight of vector a_i (of {0,1}^n) is equal to k, or it is zero otherwise, for i = 0, 1, ..., 2^n-1. Thus m(n,k) is a characteristic vector of all vectors of the n-dimensional Boolean cube, having a weight equal to k. Each characteristic vector m(n,k) is represented by its serial number #m(n,k) in M(n), for k = 0, 1, ..., n.
The vector m(n,k), for some k, 0 <= k <= n, can be used as a mask to check whether a given Boolean function of n variables takes a value 1 on some vector of weight k -- that is why the notations M and m are chosen. This check is done by a bitwise conjunction(s) between the truth table vector of the function and the mask, so it is very fast.
Analogously to Pascal's triangle, a family of subsequences is generated by this triangle (see Example section for clarifications):
   A) read by the columns (from left to right):
   1, 2, 8, 128, 32768, 2147483648, 9223372036854775808, ...: A058891(n+1) (the integers of the type a(n) = 2^(2^(n-1) - 1), for n = 1, 2, ...). Here #m(n,0), for n = 1, 2, ..., are the serial numbers of characteristic vectors of all vectors of {0,1}^n, having weight = 0 (this relation was pointed out by Andrew Howroyd);
   1, 6, 104, 26752, 1753251840, 7530159316599308288, ... (not in the OEIS as of Jul 08 2018): #m(n,1), for n = 1, 2, ..., are the serial numbers of characteristic vectors of all vectors of {0,1}^n, having weight = 1;
   1, 22, 5736, 375941248, 1614655367130677248, ... (not in the OEIS as of Jul 08 2018): #m(n,2), for n = 2, 3, ..., are the serial numbers of characteristic vectors of all vectors of {0,1}^n, having weight = 2, and so on.
   B) read by the hypotenuse, or parallel to the hypotenuse:
   1, 1, 1, 1, ...: A000012 (the all 1's sequence). Here #m(n,n), for n=1, 2, ..., are the serial numbers of characteristic vectors of all vectors of {0,1}^n, having weight = n;
   2, 6, 22, 278, 65814, 4295033110, ...: A060803 (Sum_{k = 0..n} 2^(2^k)). Here #m(n,n-1), for n=1, 2, ..., are the serial numbers of characteristic vectors of all vectors of {0,1}^n, having weight = n-1;
   8, 104, 5736, 18224744, 282668995843688, ... (twice A327373): #m(n,n-2), for n = 2, 3, ..., are the serial numbers of characteristic vectors of all vectors of {0,1}^n, having weight = n-2, and so on.

			M(0)= 1
M(1)= 2, 1 - given by definition. For n > 1, we use an inductive approach (i.e., iteration) instead of recursion since a straightforward recursive function for computing the terms of M(n) is not efficient.
To obtain M(2) we apply the recursive formula for n=2:
#m(2,0) = 2^(2^(2-1))*#m(1,0) = 4*2 = 8;
#m(2,1) = 2^(2^(2-1))*#m(1,1) + #m(1,0) = 4*1 + 2 = 6;
#m(2,2) = 1.
Thus M(2) = 8, 6, 1.
To obtain M(3) we compute:
#m(3,0) = 2^(2^(3-1))*#m(2,0) = 16*8 = 128;
#m(3,1) = 2^(2^(3-1))*#m(2,1) + #m(2,0) = 16*6 + 8 = 104;
#m(3,2) = 2^(2^(3-1))*#m(2,2) + #m(2,1) = 16*1 + 6 = 22;
#m(3,3) = 1.
Therefore M(3) = 128, 104, 22, 1.
Let's clarify the meaning of its terms. The lexicographic order of {0,1}^3 is (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1), and the corresponding sequence of (serial) numbers is 0, 1, 2, ..., 7. We have:
m(3,0) = (1,0,0,0,0,0,0,0) is the characteristic vector of the unique vector of weight 0 and hereby #m(3,0) = 2^7 = 128;
m(3,1) = (0,1,1,0,1,0,0,0) is the characteristic vector of all vectors of weight 1 and #m(3,1)=104;
m(3,2) = (0,0,0,1,0,1,1,0) is the characteristic vector of all vectors of weight 2 and then #m(3,2)=22;
m(3,3) = (0,0,0,0,0,0,0,1) the characteristic vector of the unique vector of weight 3 and #m(3,3)=1.
This sequence is bijectively related to the sequence A294648, representing the Weight-Lexicographic Order of the vectors of {0,1}^n. The row M(n) bijectively corresponds to the row L(n) of A294648, for n= 1,2, ... For example, if n=3, the third row of A294648 is
L(3) = l(3,0),...,l(3,3) = (0), (1, 2, 4), (3, 5, 6), (7) = 0, 1, 2, 4, 3, 5, 6, 7.
We recall that the coordinates of m(n,k) are numbered from left to right by 0, 1, ..., 2^n-1, and L(n) contains all these integers, partitioned in subsequences.
For the subsequences of L(3) we note:
l(3,0) = 0, which is the serial number of the unique vector (0,0,0) of {0,1}^3 of weight 0. It corresponds to m(3,0) since m(3,0) contains a unit in its leftmost coordinate only.
l(3,1) = 1, 2, 4, which are the serial numbers of all 3 vectors of {0,1}^3 of weight 1. So l(3,1) corresponds to m(3,1) -- note that 1, 2 and 4 are the coordinates in which m(3,1) contains units.
l(3,2) = 3, 5, 6, which are the serial numbers of all 3 vectors of {0,1}^3 of weight 2. It corresponds to m(3,1) -- note that 3, 5 and 6 are the coordinates in which m(3,2) contains units.
l(3,3) = 7, which is the serial number of the unique vector (1,1,1) of {0,1}^3 of weight 3. It corresponds to m(3,3).
From _Michel Marcus_, Jul 10 2018: (Start)
Triangle begins:
  1,
  2, 1,
  8, 6, 1,
  128, 104, 22, 1,
  32768, 26752, 5736, 278, 1,
  2147483648, 1753251840, 375941248, 18224744, 65814, 1,
  ... (End)

Michel Marcus, Table of n, a(n) for n = 0..65
Valentin Bakoev, Fast Computing the Algebraic Degree of Boolean Functions, arXiv:1905.08649 [cs.DM], 2019.

Cf. A294648, representing the Weight-Lexicographic Order of the vectors of {0,1}^n, is bijectively related (see Example section).

Cf. A058891, A000012, A060803, A327373.

T[n_, k_] := If[n == 1, If[k == 0, 2, 1], If[k == 0, 2^(2^n - 1), If[k == n, 1, 2^(2^(n-1)) T[n-1, k] + T[n-1, k-1]]]];
Table[T[n, k], {n, 0, 6}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 25 2018, after Michel Marcus *)

T(n, k) = if (n==1, if (k==0, 2, 1), if (k==0, 2^(2^n-1), if (k==n, 1, 2^(2^(n-1))*T(n-1,k) + T(n-1,k-1))));
tabf(nn) = for (n=1, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Jul 10 2018

M(0) = 1.
For n = 1, 2, 3, ..., M(n) is defined recursively as follows.
If n=1, M(1) = 2, 1;
otherwise, M(n) = #m(n,0), #m(n,1), ..., #m(n,k), ..., #m(n,n), where the term #m(n,k) is defined as follows:
   #m(n,0) = 2^(2^(n-1))*#m(n-1,0) = 2^(2^n-1),
   #m(n,n) = 1, and
   #m(n,k) = 2^(2^(n-1))*#m(n-1,k) + #m(n-1,k-1), for 0 < k < n.

New name from Andrey Zabolotskiy, Aug 01 2024

A344084 Concatenated list of all finite nonempty sets of positive integers sorted first by maximum, then by length, and finally lexicographically.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 4, 1, 4, 2, 4, 3, 4, 1, 2, 4, 1, 3, 4, 2, 3, 4, 1, 2, 3, 4, 5, 1, 5, 2, 5, 3, 5, 4, 5, 1, 2, 5, 1, 3, 5, 1, 4, 5, 2, 3, 5, 2, 4, 5, 3, 4, 5, 1, 2, 3, 5, 1, 2, 4, 5, 1, 3, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5

Offset: 1

Gus Wiseman, May 11 2021

			The sets are the columns below:
  1 2 1 3 1 2 1 4 1 2 3 1 1 2 1 5 1 2 3 4 1 1 1 2 2 3 1
      2   3 3 2   4 4 4 2 3 3 2   5 5 5 5 2 3 4 3 4 4 2
              3         4 4 4 3           5 5 5 5 5 5 3
                              4                       5
As a tetrangle, the first four triangles are:
  {1}
  {2},{1,2}
  {3},{1,3},{2,3},{1,2,3}
  {4},{1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}

Wikiversity, Lexicographic and colexicographic order

Triangle lengths are A000079.
Triangle sums are A001793.
Positions of first appearances are A005183.
Set maxima are A070939.
Set lengths are A124736.
Cf. A005117, A014466, A209862.
Partition/composition orderings: A026791, A026792, A026793, A036036, A036037, A048793, A066099, A080577, A112798, A118457, A124734, A162247, A193073, A211992, A228100, A228531, A246688, A272020, A296774, A299755, A304038, A319247, A329631, A334301, A334302, A334439, A334442, A335122, A344085, A344086, A344087, A344088, A344089.
Partition/composition applications: A036043, A049085, A115623, A129129, A185974, A238966, A294648, A333483, A333484, A333485, A333486, A334433, A334434, A334435, A334436, A334437, A334438, A334440, A334441, A335123, A335124, A339195.

Mathematica
```
SortBy[Rest[Subsets[Range[5]]],Last]
```

A351939 Irregular triangle read by rows: the n-th row contains the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code.

Original entry on oeis.org

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

Offset: 0

Valentin Bakoev, Feb 26 2022

Values in the range 0..2^n-1 correspond to length n binary vectors. The Hamming weight is the number of 1 bits. Reflected Gray code is described in A003188 and A014550.
Rows can be subdivided into subsequences of vectors having the same Hamming weight. Within each subsequence, adjacent values will differ by 2 bits. For example, the subsequence of length 5 vectors with Hamming weight 2 is 00011, 00110, 00101, 01100, 01010, 01001, 11000, 10100, 10010, 10001 (in decimal 3, 6, 5, 12, 10, 9, 24, 20, 18, 17).
A revolving door algorithm can be used to enumerate values of the same weight in the required order. See Knuth ("Gray codes for combinations", p. 362) for additional information.

			Triangle T(n,k) begins:
n=0: 0;
n=1: 0, 1;
n=2: 0, 1, 2, 3;
n=3: 0, 1, 2, 4, 3, 6, 5, 7;
n=4: 0, 1, 2, 4, 8, 3, 6, 5, 12, 10, 9, 7, 13, 14, 11, 15;
n=5: 0, 1, 2, 4, 8, 16, 3, 6, 5, 12, 10, 9, 24, 20, 18, 17, 7, 13, 14, 11, 25, 26, 28, 21, 22, 19, 15, 27, 30, 29, 23, 31;
...
For row n = 3, the binary words of length 3 in reflected Gray code order are 000, 001, 011, 010, 110, 111, 101, 100. Arranging these by Hamming weight but otherwise preserving the order gives 000, 001, 010, 100, 011, 110, 101, 111. As decimal numbers these are 0, 1, 2, 4, 3, 6, 5, 7, which is row 3.

D. Knuth, The art of computer programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011.
F. Ruskey, Combinatorial Generation. Working Version (1j-CSC 425/520), 2003.

Valentin Bakoev, Table of n, a(n) for n = 0..65535
Valentin Bakoev, Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube, Discrete Mathematics, Algorithms and Applications, Vol. 13 No 3, 2150021 (2021); arXiv preprint, arXiv:1811.04421 [cs.DM], 2018-2020.
Valentin Bakoev, Ordering the Boolean Cube Vectors by Their Weights and with Minimal Change, Int'l Conf. Algebraic Informatics (CAI 2022) Lecture Notes Comp. Sci. (LNCS) Vol. 13706, 43-54.
Sage Reference Manual, Gray codes

Row sums are A006516.
Right border gives A000225.
Left border gives A000004.
T(n,n) gives A131577.
Cf. A000120 (Hamming weight), A003188, A014550 (reflected Gray code), A294648 (weight-lexicographic order).

b:= proc(n) b(n):= `if`(n<2, n, Bits[Xor](n, b(iquo(n, 2)))) end:
h:= proc(n) h(n):= add(i, i=Bits[Split](n)) end:
T:= n-> sort([$0..2^n-1], (x,y)-> h(x)Alois P. Heinz, Mar 01 2022

b[n_] := If[n < 2, n, BitXor[n, b[Quotient[n, 2]]]];
h[n_] := DigitCount[n, 2, 1];
T[n_] := SortBy[{h, b}][Range[0, 2^n - 1]];
Table[T[n], {n, 0, 6}] // Flatten (* Jean-François Alcover, Oct 21 2022, after Alois P. Heinz *)

row(n)=vecsort(vector(2^n, i, i--; bitxor(i, i>>1)), (x,y) -> cmp(hammingweight(x), hammingweight(y)))
{ for(n=0, 5, print(row(n))) } \\ Andrew Howroyd, Feb 28 2022

The n-th row is the concatenation of the subsequences g(n, 0), ..., g(n, n), where the subsequences are defined as follows:
  g(n, 0) = (0),
  g(n, n) = (2^n - 1),
  g(n, k) = g(n-1, k) concatenate (g^r(n-1, k-1) + 2^(n-1)) for 0 < k < n.
In the above, g^r(n-1, k-1) + 2^(n-1) means the 2^(n-1) is added to each member of the subsequence g(n-1, k-1) in reversed order.

A382467 Irregular triangle read by rows, where row n lists the integers from 0 to 2^n - 1 sorted by the number of zeros in their binary representation (in case of ties, by their decimal value).

Original entry on oeis.org

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

Offset: 0

Paolo Xausa, Mar 31 2025

			Triangle begins:
  [0]  0;
  [1]  0,  1;
  [2]  0,  1,  3,  2;
  [3]  0,  1,  3,  7,  2,  5,  6,  4;
  [4]  0,  1,  3,  7, 15,  2,  5,  6, 11, 13, 14,  4,  9, 10, 12,  8;
  ...

Paolo Xausa, Table of n, a(n) for n = 0..8190 (rows 0..12 of triangle, flattened).

Cf. A080791, A294648 (sorted by number of ones).
Main diagonal gives A000225.
Last elements of rows give A131577.
Row sums give A006516.

b:= proc(n) b(n):= add(1-i, i=Bits[Split](n)) end:
T:= n-> sort([$0..2^n-1], (x, y)-> b(x)Alois P. Heinz, Mar 31 2025

Table[SortBy[Range[0, 2^n - 1], DigitCount[#, 2, 0] &], {n, 0, 6}]

A359336 Irregular triangle read by rows: the n-th row lists the values 0..2^n-1 representing all subsets of a set of n elements. When its elements are linearly ordered, the subsets are sorted first by their size and then lexicographically.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 1, 6, 5, 3, 7, 0, 8, 4, 2, 1, 12, 10, 9, 6, 5, 3, 14, 13, 11, 7, 15, 0, 16, 8, 4, 2, 1, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3, 28, 26, 25, 22, 21, 19, 14, 13, 11, 7, 30, 29, 27, 23, 15, 31, 0, 32, 16, 8, 4, 2, 1, 48, 40, 36, 34, 33, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3, 56, 52, 50, 49

Offset: 0

Valentin Bakoev, Dec 27 2022

The n-th row of the table is denoted by row(n) and contains a permutation of the integers from the interval [0, 2^n-1] which defines an ordering of all binary vectors of length n. Let the elements of the set B_n = {b_n, b_(n-1), ..., b_2, b_1} be linearly ordered: b_n < b_(n-1) < ... < b_2 < b_1. When we consider the binary vectors defined by row(n) as characteristic vectors, they define all subsets of B_n, sorted first by their cardinalities and then lexicographically. The sequence in row(n) is partitioned into n+1 subsequences of integers whose binary vectors have the same (Hamming) weight.
Equivalently, the sequence in row(n) defines all (n,k) combinations over a linearly ordered set in lexicographic order, for k = 0, 1, ..., n.
Like A294648 and A351939, A359336 represents one of the numerous weight orderings of the vectors of the n-dimensional Boolean cube (or the subsets of a set of n-elements sorted by their size) - see A051459.
Following the formula for row(n), we get:
T(n,0) = 0;
T(n, 2^n-1) = 2^n-1;
T(n,n) = 1, for n >= 1.
T(n,k) = 2^(n-k) for 1 <= k <= n.
Thus the regular triangle T(n,k), for n = 1, 2, 3, ... and for 1 <= k <= n consists of powers of 2 (A000079): in ascending order by columns and in descending order by rows.

			In the following table, the members of row(3) are given in column dec., the corresponding characteristic vectors are in column bin., and the corresponding subsets of B_3 are listed under B_3.
dec., bin., B_3 = {a, b, c}
---------------------------
 0    000        {}
 4    100        {a}
 2    010        {b}
 1    001        {c}
 6    110        {a, b}
 5    101        {a, c}
 3    011        {b, c}
 7    111        {a, b, c}
As seen, the corresponding subsets of equal size are ordered lexicographically.
Triangle T(n,k) begins:
    k = 0   1   2   3   4   5   6   7 ...
  n=0:  0;
  n=1:  0,  1;
  n=2:  0,  2,  1,  3;
  n=3:  0,  4,  2,  1,  6,  5,  3,  7;
  n=4:  0,  8,  4,  2,  1, 12, 10,  9,  6,  5,  3, 14, 13, 11,  7, 15,
  n=5:  0, 16,  8,  4,  2,  1, 24, 20, 18, 17, 12, 10,  9,  6,  5,  3, 28, 26, 25, 22, 21, 19, 14, 13, 11, 7, 30, 29, 27, 23, 15, 31;
  ...

Valentin Bakoev, Rows n = 0..10, flattened
Valentin Bakoev, Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube, Discrete Mathematics, Algorithms and Applications, Vol. 13 No 3, 2150021 (2021); arXiv preprint, arXiv:1811.04421 [cs.DM], 2018-2020.
Valentin Bakoev, An Algorithm for Generating All Subsets in Lexicographic Order, ICAI 2022, pp. 271-275.

Cf. A000004 (column k=0), A000225 (right border), A000012 (main diagonal), A006516 (row sums).
Cf. A294648 (weight-lexicographic order of the binary vectors), A351939 (the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code).
Cf. A356028.

For n = 1, 2, 3, ..., row(n) is a concatenation of the subsequences r(n, 0), r(n, 1), ..., r(n, n) defined by the recurrence:
r(n, 0) = (0),
r(n, n) = (2^n - 1),
r(n, k) = (r(n-1, k-1) + 2^(n-1)) concatenate r(n-1, k), for 0 < k < n.
In the above, r(n-1, k-1) + 2^(n-1) means the 2^(n-1) is added to each member of the subsequence r(n-1, k-1).

A381500 a(n) = A019565(A187769(n)).

Original entry on oeis.org

1, 2, 3, 6, 5, 10, 15, 30, 7, 14, 21, 35, 42, 70, 105, 210, 11, 22, 33, 55, 77, 66, 110, 165, 154, 231, 385, 330, 462, 770, 1155, 2310, 13, 26, 39, 65, 91, 143, 78, 130, 195, 182, 273, 455, 286, 429, 715, 1001, 390, 546, 910, 1365, 858, 1430, 2145, 2002, 3003

Offset: 0

Michael De Vlieger, Peter Munn, and Antti Karttunen, Feb 27 2025

The squarefree numbers, ordered first by largest prime factor (dividing the sequence into rows), then by number of prime factors, then lexicographically by their prime factors (written in descending order).

We index (a(n)) from offset 0, matching the choice for A019565 and similar sequences.

			Table begins:
  Row 0:  1;
  Row 1:  2;
  Row 2:  3,  6;
  Row 3:  5, 10, 15, 30;
  Row 4:  7, 14, 21, 35, 42, 70, 105, 210;
  Row 5: 11, 22, 33, 55, 77, 66, 110, 165, 154, 231, 385, 330, 462, 770, 1155, 2310;
  ...
Table of a(n) for n = 0..31, demonstrating relationship of this sequence with s = A187769:
          <-factors                    <-factors
   n  a(n)  2 3 5 7  s(n)  |   n   a(n)  2 3 5 7 11 s(n)
  -------------------------|----------------------------
   0    1   .          0   |  16    11   . . . . x   16
   1    2   x          1   |  17    22   x . . . x   17
   2    3   . x        2   |  18    33   . x . . x   18
   3    6   x x        3   |  19    55   . . x . x   20
   4    5   . . x      4   |  20    77   . . . x x   24
   5   10   x . x      5   |  21    66   x x . . x   19
   6   15   . x x      6   |  22   110   x . x . x   21
   7   30   x x x      7   |  23   165   . x x . x   22
   8    7   . . . x    8   |  24   154   x . . x x   25
   9   14   x . . x    9   |  25   231   . x . x x   26
  10   21   . x . x   10   |  26   385   . . x x x   28
  11   35   . . x x   12   |  27   330   x x x . x   23
  12   42   x x . x   11   |  28   462   x x . x x   27
  13   70   x . x x   13   |  29   770   x . x x x   29
  14  105   . x x x   14   |  30  1155   . x x x x   30
  15  210   x x x x   15   |  31  2310   x x x x x   31
  -------------------------|----------------------------
            1 2 4 8  s(n)  |             1 2 4 8 16 s(n)
             bits->                         bits->

Michael De Vlieger, Table of n, a(n) for n = 0..16383
Michael De Vlieger, Log log scatterplot of a(n), n = 0..2^16-1.
Michael De Vlieger, Plot p | a(n) at (x,y) = (n, pi(p)), n = 0..2047, 12X vertical exaggeration.
Michael De Vlieger, Fan style binary tree showing a(n), n = 0..2048, with a color function showing smallest and greatest terms in each row in green and red, respectively.

Cf. A019565, A119416, A163866, A187769, A253550, A294648, A344085.

A002110, A098012 are subsequences.

a187769 = {{0}}~Join~Table[SortBy[Range[2^n, 2^(n + 1) - 1], DigitCount[#, 2, 1] &], {n, 0, 8}] // Flatten; a019565[x_] := Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[x, 2]; Map[a019565, a187769]

a(n) = A019565(A187769(n)).
As an irregular triangle T(n,k), where row 0 = {1}:
For n > 1, omega(T(n,1)) = 1, omega(T(n, 2^(n-1))) = n, thus row n is divided into n segments S such that with S, omega(T(n,k)) = m, where m = 1..n. (See A187769 for the lengths of segments associated with Pascal's triangle A007318.)
S(-1,-1) = (1).
For n >= 0:
S(n-1, n) = (); S(n, -1) = ();
for 0 <= m <= n, S(n,m) = ( A253550'(S(n-1, m)), A119416'(S(n-1, m-1)) ), where Axxx'((i_1, i_2, ..., i_j)) denotes Axxx(i_1), Axxx(i_2), ..., Axxx(i_j).
a(A163866(n)) = A098012(n).

cp's OEIS Frontend

A356028 Irregular triangle {A(n, k)} read by rows, giving in row n the numbers 1, 2, ..., 2^n - 1 ordered according to increasing binary weights, and for like weights decreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A047869 Subsets of an 8-element set in order by number of elements in each subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A305860 Triangle m(n,k) read by rows (n >= 0, 0 <= k <= n): to get the binary expansion of m(n,k), for 0 <= i < 2^n, write 1 if the binary weight of i is equal to k or 0 otherwise, left to right.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A344084 Concatenated list of all finite nonempty sets of positive integers sorted first by maximum, then by length, and finally lexicographically.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A351939 Irregular triangle read by rows: the n-th row contains the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A382467 Irregular triangle read by rows, where row n lists the integers from 0 to 2^n - 1 sorted by the number of zeros in their binary representation (in case of ties, by their decimal value).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A359336 Irregular triangle read by rows: the n-th row lists the values 0..2^n-1 representing all subsets of a set of n elements. When its elements are linearly ordered, the subsets are sorted first by their size and then lexicographically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A381500 a(n) = A019565(A187769(n)).