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.

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

Author

Valentin Bakoev, Jul 08 2018

Keywords

• nonn
• tabl

Comments

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.

Examples

			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)
		

Links

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

Crossrefs

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.

Programs

Mathematica

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

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))));
tabf(nn) = for (n=1, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Jul 10 2018

Formula

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.

Extensions

New name from Andrey Zabolotskiy, Aug 01 2024