cp's OEIS Frontend

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.

%I A305860 #105 Mar 17 2025 19:34:01
%S A305860 1,2,1,8,6,1,128,104,22,1,32768,26752,5736,278,1,2147483648,
%T A305860 1753251840,375941248,18224744,65814,1,9223372036854775808,
%U A305860 7530159316599308288,1614655367130677248,78274679833913472,282668995843688,4295033110,1
%N 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.
%C A305860 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.
%C A305860 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.
%C A305860 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.
%C A305860 Analogously to Pascal's triangle, a family of subsequences is generated by this triangle (see Example section for clarifications):
%C A305860    A) read by the columns (from left to right):
%C A305860    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_);
%C A305860    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;
%C A305860    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.
%C A305860    B) read by the hypotenuse, or parallel to the hypotenuse:
%C A305860    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;
%C A305860    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;
%C A305860    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.
%H A305860 Michel Marcus, <a href="/A305860/b305860.txt">Table of n, a(n) for n = 0..65</a>
%H A305860 Valentin Bakoev, <a href="https://arxiv.org/abs/1905.08649">Fast Computing the Algebraic Degree of Boolean Functions</a>, arXiv:1905.08649 [cs.DM], 2019.
%F A305860 M(0) = 1.
%F A305860 For n = 1, 2, 3, ..., M(n) is defined recursively as follows.
%F A305860 If n=1, M(1) = 2, 1;
%F A305860 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:
%F A305860    #m(n,0) = 2^(2^(n-1))*#m(n-1,0) = 2^(2^n-1),
%F A305860    #m(n,n) = 1, and
%F A305860    #m(n,k) = 2^(2^(n-1))*#m(n-1,k) + #m(n-1,k-1), for 0 < k < n.
%e A305860 M(0)= 1
%e A305860 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.
%e A305860 To obtain M(2) we apply the recursive formula for n=2:
%e A305860 #m(2,0) = 2^(2^(2-1))*#m(1,0) = 4*2 = 8;
%e A305860 #m(2,1) = 2^(2^(2-1))*#m(1,1) + #m(1,0) = 4*1 + 2 = 6;
%e A305860 #m(2,2) = 1.
%e A305860 Thus M(2) = 8, 6, 1.
%e A305860 To obtain M(3) we compute:
%e A305860 #m(3,0) = 2^(2^(3-1))*#m(2,0) = 16*8 = 128;
%e A305860 #m(3,1) = 2^(2^(3-1))*#m(2,1) + #m(2,0) = 16*6 + 8 = 104;
%e A305860 #m(3,2) = 2^(2^(3-1))*#m(2,2) + #m(2,1) = 16*1 + 6 = 22;
%e A305860 #m(3,3) = 1.
%e A305860 Therefore M(3) = 128, 104, 22, 1.
%e A305860 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:
%e A305860 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;
%e A305860 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;
%e A305860 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;
%e A305860 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.
%e A305860 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
%e A305860 L(3) = l(3,0),...,l(3,3) = (0), (1, 2, 4), (3, 5, 6), (7) = 0, 1, 2, 4, 3, 5, 6, 7.
%e A305860 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.
%e A305860 For the subsequences of L(3) we note:
%e A305860 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.
%e A305860 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.
%e A305860 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.
%e A305860 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).
%e A305860 From _Michel Marcus_, Jul 10 2018: (Start)
%e A305860 Triangle begins:
%e A305860   1,
%e A305860   2, 1,
%e A305860   8, 6, 1,
%e A305860   128, 104, 22, 1,
%e A305860   32768, 26752, 5736, 278, 1,
%e A305860   2147483648, 1753251840, 375941248, 18224744, 65814, 1,
%e A305860   ... (End)
%t A305860 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]]]];
%t A305860 Table[T[n, k], {n, 0, 6}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 25 2018, after _Michel Marcus_ *)
%o A305860 (PARI) 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))));
%o A305860 tabf(nn) = for (n=1, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ _Michel Marcus_, Jul 10 2018
%Y A305860 Cf. A294648, representing the Weight-Lexicographic Order of the vectors of {0,1}^n, is bijectively related (see Example section).
%Y A305860 Cf. A058891, A000012, A060803, A327373.
%K A305860 nonn,tabl
%O A305860 0,2
%A A305860 _Valentin Bakoev_, Jul 08 2018
%E A305860 New name from _Andrey Zabolotskiy_, Aug 01 2024