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

 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.

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