cp's OEIS Frontend

The n-th row of the triangle is defined recursively as row(0) = 0 which corresponds to the empty word, and row(n) = row(n-1)0, row^r(n-1)1, for n > 0. Here row(n-1)0 is the sequence of words of the (n-1)-bit Gray code of this type suffixed with 0, and row^r(n-1)1 means the sequence of reflected words (i.e., words are taken in reverse order) of the (n-1)-bit Gray code of this type and then each word is suffixed with 1.

Another way to obtain row(n) is by applying the transition sequence A001511(n), which indicates which bit to flip in the current word to get the next word - see the FORMULA section.

If we reverse the internal order of bits in each word of row(n), we obtain the binary reflected n-bit Gray code (see A003188) and vice versa.

The n-th row of the table is denoted by row(n) and contains a permutation of the integers from the interval [0, 2^n-1] which defines an ordering of all binary vectors of length n. Let the elements of the set B_n = {b_n, b_(n-1), ..., b_2, b_1} be linearly ordered: b_n < b_(n-1) < ... < b_2 < b_1. When we consider the binary vectors defined by row(n) as characteristic vectors, they define all subsets of B_n, sorted first by their cardinalities and then lexicographically. The sequence in row(n) is partitioned into n+1 subsequences of integers whose binary vectors have the same (Hamming) weight.

Equivalently, the sequence in row(n) defines all (n,k) combinations over a linearly ordered set in lexicographic order, for k = 0, 1, ..., n.

Like A294648 and A351939, A359336 represents one of the numerous weight orderings of the vectors of the n-dimensional Boolean cube (or the subsets of a set of n-elements sorted by their size) - see A051459.

Following the formula for row(n), we get:

T(n,0) = 0;

T(n, 2^n-1) = 2^n-1;

T(n,n) = 1, for n >= 1.

T(n,k) = 2^(n-k) for 1 <= k <= n.

Thus the regular triangle T(n,k), for n = 1, 2, 3, ... and for 1 <= k <= n consists of powers of 2 (A000079): in ascending order by columns and in descending order by rows.

The sequence in the n-th row of the triangle is denoted by row(n). It contains the values in the range 0..2^n-1 corresponding to the binary vectors of length n. The integers in row (n), considered as characteristic vectors of the set B_n = {b_n, b_(n-1), ..., b_2, b_1}, whose elements are linearly ordered: b_n < b_(n-1) < ... < b_2 < b_1, define all subsets of B_n in lexicographic order. To obtain row(n) we reason inductively as follows. Obviously, row(0) = 0 = a(0) and corresponds to the empty set {}. Assume that the sequence row(n-1) = i_0, i_1, ..., i_(2^(n-1)-1) is obtained. It defines a lexicographic order of the subsets of B_(n-1) = {b_(n-1) , ..., b_2, b_1} - note that its elements linearly ordered. Then row (n) = i_0, 2^(n-1) + i_0, 2^(n-1) + i_1, ..., 2^(n-1) + i_(2^(n-1)-1), i_1, ..., i_(2^(n-1)-1) defines all subsets of B_n in lexicographic order. In other words, row(n) = 0, (row(n-1) + 2^(n-1)), (row(n-1) without the first term 0), i.e., row(n-1) is taken twice: first, all terms of row(n-1) are incremented by 2^(n-1) and second, the resulting sequence is inserted after the first term of row(n-1), which is always 0 and corresponds to {}.

Values in the range 0..2^n-1 correspond to length n binary vectors. The Hamming weight is the number of 1 bits. Reflected Gray code is described in A003188 and A014550.

Rows can be subdivided into subsequences of vectors having the same Hamming weight. Within each subsequence, adjacent values will differ by 2 bits. For example, the subsequence of length 5 vectors with Hamming weight 2 is 00011, 00110, 00101, 01100, 01010, 01001, 11000, 10100, 10010, 10001 (in decimal 3, 6, 5, 12, 10, 9, 24, 20, 18, 17).

A revolving door algorithm can be used to enumerate values of the same weight in the required order. See Knuth ("Gray codes for combinations", p. 362) for additional information.

The canonical representation of a given Boolean function f of n variables by its Algebraic Normal Form (ANF) is a multivariate polynomial of the form f(x_1, x_2, ..., x_n)= a + M_1 + M_2 + ... + M_s, where a is the Boolean constant 0 or 1, the + sign denotes sum modulo 2 (XOR) between different monomials, and 0 <= s < 2^n. The monomial M_i is a conjunction of some of these variables, for i= 1, 2, ..., s. The algebraic degree of a monomial is the number of variables in the monomial and the algebraic degree of a Boolean function is the maximum degree of the monomials. There are binomial(n, k) monomials of k variables, for k= 0, 1, ..., n. The case k= 0 means that no one of the variables is chosen to form a monomial. It corresponds to the Boolean constant 1, which is considered as a monomial. Its algebraic degree is equal to 0 and so T(n,0)= 1, for n= 0, 1, ... The zero constant is not considered as a monomial. It corresponds to the empty set - the case when no one of the possible monomials is chosen to form an ANF. Its algebraic degree is defined usually as -infinity. That is why the zero constant is not represented in the triangle.

The set of all Boolean functions of n variables can be partitioned into subsets in accordance with their algebraic degrees. The n-th row of the triangle represents the cardinalities of these subsets. Thus the sum of all numbers in the n-th row is the number of all Boolean functions of n variables - 1 (because of the zero constant), i.e., 2^(2^n)-1.

Equivalently, the number of nonempty sets of subsets of an n-set such that the maximum cardinality of the subsets is k. - Andrew Howroyd, Sep 23 2018

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.

The sequences represent the ordinance of vectors of the n-dimensional Boolean cube (hypercube) {0,1}^n in accordance with their (Hamming) weights. The lexicographic order is chosen as a second criterion for the ordinance of the vectors of equal weights. We refer to this order as a Weight-Lexicographic Order (WLO). The WLO is represented by the (serial) numbers of the vectors, instead of the vectors itself. It is well known that if the vectors of {0,1}^n are in lexicographic (standard) order, their numbers form the sequence of natural numbers 0, 1, 2, ..., 2^n-1. So, the WLO means a permutation of the numbers 0, 1, 2, ..., 2^n-1, such that the corresponding vectors are in WLO. This sequence (permutation) is denoted by L(n). It consists of (n+1) subsequences, corresponding to the layers of the Boolean cube.