A319511 Triangle read by rows: T(n,k) is the number of Boolean functions on n variables having an algebraic degree equal to k (for n >= 0 and 0 <= k <= n).

1, 1, 2, 1, 6, 8, 1, 14, 112, 128, 1, 30, 2016, 30720, 32768, 1, 62, 65472, 67043328, 2080374784, 2147483648, 1, 126, 4194176, 4398042316800, 144110790029344768, 9079256848778919936, 9223372036854775808

Offset: 0

Author

Valentin Bakoev, Sep 21 2018

Keywords

• nonn
• tabl

Comments

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

Examples

			Triangle begins:
  1;
  1, 2;
  1, 6, 8;
  1, 14, 112, 128;
  1, 30, 2016, 30720, 32768;
  1, 62, 65472, 67043328, 2080374784, 2147483648;
  1, 126, 4194176, 4398042316800, 144110790029344768, 9079256848778919936, 9223372036854775808;
  ...
From _Andrew Howroyd_, Sep 23 2018: (Start)
Case n=2: There are a total of 15 Boolean functions on two variables excluding the constant 0 function or equivalently 15 nonempty sets of subsets of {1,2}. These can be partitioned according to k the size of the largest subset as follows:
k=0: {{}};
k=1: {{1}}, {{1},{}}, {{2}}, {{2},{}}, {{1},{2}}, {{1},{2},{}};
k=2: {{1,2}}, {{1,2},{}}, {{1,2},{1}}, {{1,2},{1},{}}, {{1,2},{2}}, {{1,2},{2},{}}, {{1,2},{1},{2}}, {{1,2},{1},{2},{}}.
(End)
		

Links

• Valentin Bakoev, Rows n=0..8 of the triangle, flattened
• Valentin Bakoev, Distribution of the boolean functions of n variables according to their algebraic degrees, Serdica Journal of Computing, 13 (2019), No 2, pp 17-26.
• Valentin Bakoev, Fast Computing the Algebraic Degree of Boolean Functions, arXiv:1905.08649 [cs.DM], 2019.
• Wikipedia, Algebraic normal form

Crossrefs

Row sums are A051179.

Cf. A000079, A000918, A001146, A058891, A305860.

Programs

Mathematica

Table[(2^Binomial[n, k] - 1)*2^Sum[Binomial[n, i], {i, 0, k - 1}], {n, 0, 6}, {k, 0, n}] // Flatten (* Michael De Vlieger, Jul 02 2019 *)

Maxima

T(n,k):= (2^binomial(n,k) - 1)*2^sum(binomial(n,i), i, 0, k-1);

PARI

T(n,k) = {((2^binomial(n, k)) - 1)*2^sum(i=0, k-1, binomial(n, i))} \\ Andrew Howroyd, Sep 22 2018

Formula

T(n,k) = ((2^binomial(n, k)) - 1)*2^(Sum_{i=0..k-1} binomial(n, i)).

T(n,0) = 1.

T(n,1) = 2^(n + 1) - 2 = A000918(n+1).

T(n,0) + T(n,1) + 1 = 2^(n+1) = A000079(n+1).

T(n,n) = 2^(2^n - 1) = A058891(n+1) = A001146(n)/2.

T(n,n) = A305860(n,0).