%I #53 Jul 07 2020 00:49:08
%S 1,1,2,1,6,8,1,14,112,128,1,30,2016,30720,32768,1,62,65472,67043328,
%T 2080374784,2147483648,1,126,4194176,4398042316800,144110790029344768,
%U 9079256848778919936,9223372036854775808
%N 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).
%C 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.
%C 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.
%C 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
%H Valentin Bakoev, <a href="/A319511/b319511.txt">Rows n=0..8 of the triangle, flattened</a>
%H Valentin Bakoev, <a href="/A319511/a319511.pdf">Distribution of the boolean functions of n variables according to their algebraic degrees</a>, Serdica Journal of Computing, 13 (2019), No 2, pp 17-26.
%H Valentin Bakoev, <a href="https://arxiv.org/abs/1905.08649">Fast Computing the Algebraic Degree of Boolean Functions</a>, arXiv:1905.08649 [cs.DM], 2019.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Algebraic_normal_form">Algebraic normal form</a>
%F T(n,k) = ((2^binomial(n, k)) - 1)*2^(Sum_{i=0..k-1} binomial(n, i)).
%F T(n,0) = 1.
%F T(n,1) = 2^(n + 1) - 2 = A000918(n+1).
%F T(n,0) + T(n,1) + 1 = 2^(n+1) = A000079(n+1).
%F T(n,n) = 2^(2^n - 1) = A058891(n+1) = A001146(n)/2.
%F T(n,n) = A305860(n,0).
%e Triangle begins:
%e 1;
%e 1, 2;
%e 1, 6, 8;
%e 1, 14, 112, 128;
%e 1, 30, 2016, 30720, 32768;
%e 1, 62, 65472, 67043328, 2080374784, 2147483648;
%e 1, 126, 4194176, 4398042316800, 144110790029344768, 9079256848778919936, 9223372036854775808;
%e ...
%e From _Andrew Howroyd_, Sep 23 2018: (Start)
%e 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:
%e k=0: {{}};
%e k=1: {{1}}, {{1},{}}, {{2}}, {{2},{}}, {{1},{2}}, {{1},{2},{}};
%e 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},{}}.
%e (End)
%t 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 *)
%o (Maxima) T(n,k):= (2^binomial(n,k) - 1)*2^sum(binomial(n,i), i, 0, k-1);
%o (PARI) T(n,k) = {((2^binomial(n, k)) - 1)*2^sum(i=0, k-1, binomial(n, i))} \\ _Andrew Howroyd_, Sep 22 2018
%Y Row sums are A051179.
%Y Cf. A000079, A000918, A001146, A058891, A305860.
%K nonn,tabl
%O 0,3
%A _Valentin Bakoev_, Sep 21 2018