login
Triangle read by rows, giving T(n,k) = maximum number of examples (Boolean inputs) at Hamming distance 2 for symmetric Boolean functions that can have different outputs.
2

%I #12 Dec 25 2021 03:53:41

%S 1,1,1,1,0,1,1,1,1,1,1,2,2,2,1,1,3,4,4,3,1,1,4,7,8,7,4,1,1,5,11,15,15,

%T 11,5,1,1,6,16,26,30,26,16,6,1,1,7,22,42,56,56,42,22,7,1,1,8,29,64,98,

%U 112,98,64,29,8,1,1,9,37,93,162,210,210,162,93,37,9,1,1,10,46,130,255,372,420

%N Triangle read by rows, giving T(n,k) = maximum number of examples (Boolean inputs) at Hamming distance 2 for symmetric Boolean functions that can have different outputs.

%C This sets an upper bound on the second order term of the complexity measure introduced by Franco, 2001 for symmetric Boolean functions. The sum of the terms for a given N is equal to 2^(N-1).

%H L. Franco, <a href="https://arxiv.org/abs/cond-mat/0111169">A measure for the complexity of Boolean functions related to their implementation in neural networks</a>, arXiv:cond-mat/0111169 [cond-mat.dis-nn], 2001.

%H L. Franco and S. A. Cannas, <a href="https://arxiv.org/abs/cond-mat/0302412">Non-glassy ground-state in a long-range antiferromagnetic frustrated model in the hypercubic cell</a>, arXiv:cond-mat/0302412 [cond-mat.stat-mech], 2003; Phys. A 332 (2004), no. 1-4, 337-348.

%F T(n, N) = ((N-n)^2 + n^2 - N) * C(N, n) / (N^2 - N) n is the term for the series containing N+1 terms

%F From _Peter Bala_, Mar 20 2018: (Start)

%F Except for (n,k) = (1,0) the formula T(n,k) = C(n,k) - 2*C(n-1,n-k-1) + 2*C(n-2,n-k-2), where C(n,k) = n!/(k!*(n-k)!) for 0 <= k <= n, otherwise 0, appears to give the correct table entries.

%F Appears to equal A159853, the Riordan array ((1-2*x+2*x^2)/(1-x), x/(1-x)), except for the entry T(1,0). If this is correct then provided n =! 1 we have exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(1 + x + x^2/2! + x^3/3!) = 1 + 2*x + 2*x^2/2! + 4*x^3/3! + 8*x^4/4! + 15*x^5/5! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ). (End)

%e Triangle begins:

%e 1 N=0

%e 1 1 N=1

%e 1 0 1 N=2

%e 1 1 1 1 N=3

%e 1 2 2 2 1 N=4

%Y Cf. A088219, A159853.

%K nonn,tabl

%O 0,12

%A Leonardo Franco (Leonardo.Franco(AT)psy.ox.ac.uk), Sep 24 2003