login
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

%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