login
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).
2
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,3
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
LINKS
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.
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).
EXAMPLE
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)
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 *)
PROG
(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
CROSSREFS
Row sums are A051179.
Sequence in context: A350010 A193734 A318390 * A110608 A318397 A190015
KEYWORD
nonn,tabl
AUTHOR
Valentin Bakoev, Sep 21 2018
STATUS
approved