A294648 Irregular triangle read by rows, representing a family of sequences L(n), for n=1, 2, 3, ... The sequence L(n) (i.e., the n-th row) is the ordinance of vectors of the n-dimensional Boolean cube (hypercube) {0,1}^n in accordance with their (Hamming) weights, where the lexicographic order is chosen as a second criterion for an ordinance the vectors of equal weights.
0, 1, 0, 1, 2, 3, 0, 1, 2, 4, 3, 5, 6, 7, 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 15, 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, 0, 1, 2, 4, 8, 16, 32, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 7, 11, 13, 14, 19, 21
Offset: 1
Examples
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. The WLO of these vectors is given by the sequence L(3)= 0, 1, 2, 4, 3, 5, 6, 7.
The triangle starts:
n=1: 0, 1;
n=2: 0, 1, 2, 3;
n=3: 0, 1, 2, 4, 3, 5, 6, 7;
n=4: 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 15;
n=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;
n=6: 0, 1, 2, 4, 8, 16, 32, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 31, 47, 55, 59, 61, 62, 63;
Links
- Michael De Vlieger, Table of n, a(n) for n = 1..10000
- 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, Fast Computing the Algebraic Degree of Boolean Functions, arXiv:1905.08649 [cs.DM], 2019.
Crossrefs
Programs
-
Maple
with(ListTools): conc := (a,b,c) -> Flatten([op(a),[seq(op(j)+c, j in b)]], 1): rec := proc(n,k) option remember; `if`(k=0, [0], `if`(k=n, [2^n-1], conc(rec(n-1,k), rec(n-1,k-1), 2^(n-1)))) end: L := n -> `if`(n=1, [0,1], Flatten([seq(rec(n,k),k=0..n)], 1)): Flatten([seq(L(n), n = 1..6)], 1); # Peter Luschny, Nov 06 2017
-
Mathematica
conc[a_List, b_List, c_] := Join[a, b + c]; rec[n_, k_] := rec[n, k] = If[k == 0, {0}, If[k == n, {2^n - 1}, conc[rec[n - 1, k], rec[n - 1, k - 1], 2^(n - 1)]]]; L[n_] := If[n == 1, {0, 1}, Flatten[Table[rec[n, k], {k, 0, n}]]]; Array[L, 6] // Flatten (* Jean-François Alcover, Jul 26 2018, after Peter Luschny *) Table[SortBy[Range[0, 2^n - 1], DigitSum[#, 2] &], {n, 6}] (* Paolo Xausa, Jul 28 2025 *) -
PARI
cmph(x, y) = my(d=hammingweight(x)-hammingweight(y)); if (d, d, x-y); row(n) = my(v=[0..2^n-1]); vecsort(v, cmph); \\ Michel Marcus, Sep 16 2023
-
Python
from itertools import product def sortby(x): return (len(x), x.count('1'), x) def agen(maxbindigs): for i in range(1, maxbindigs+1): for t in sorted([p for p in product("01", repeat=i)], key=sortby): yield int("".join(t), 2) print([an for an in agen(6)]) # Michael S. Branicky, Aug 13 2021
Formula
For n=1, 2, 3, ..., L(n) is defined by the recurrence:
if n=1, L(1)= 0, 1;
else L(n)= l(n, 0), l(n, 1), ..., l(n, k), ..., l(n, n), where the subsequences are defined as follows:
l(n, k)= 0, if k=0, else
l(n, k)= 2^n - 1, if k=n, else
l(n, k)= l(n-1, k), l(n-1, k-1) + 2^{n-1}, for 0 < k < n.
Comments:
1) l(n, k)= l(n-1, k), l(n-1, k-1) + 2^{n-1} means that l(n, k) is a concatenation of two subsequences: l(n-1, k) and l(n-1, k-1) + 2^{n-1}. The second one is obtained after addition of the number 2^{n-1} to each member of l(n-1,k-1).
2) The computing of the members of L(n) resembles the computing (and filling in) the binomial coefficients in Pascal's triangle. The binomial coefficients determine the lengths of the subsequences l(n, k), 0 <= k <= n, in L(n). Thus the beginning of each subsequence can be computed easily.
3) The inductive formula, corresponding to the recurrence, is much more useful for implementations.
Comments