login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 zero row (i.e., M(0)) and its single term 1 are prepended for convenience. 2
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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-bits 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 and 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) in OEIS (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 by Andrew Howroyd);

   1, 6, 104, 26752, 1753251840, 7530159316599308288, ... (not in 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 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 in OEIS (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 in OEIS (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, ... (not in OEIS by Jul 08 2018) - #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.

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.

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.

EXAMPLE

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)

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

PROG

(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

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 (see the third comment).

Sequence in context: A318389 A108084 A108085 * A272983 A195698 A193908

Adjacent sequences:  A305857 A305858 A305859 * A305861 A305862 A305863

KEYWORD

nonn,tabl

AUTHOR

Valentin Bakoev, Jul 08 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 20:23 EDT 2020. Contains 334748 sequences. (Running on oeis4.)