A087698 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.

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, 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, 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

Offset

0,12

Comments

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).

Links

Table of n, a(n) for n=0..84.

L. Franco, A measure for the complexity of Boolean functions related to their implementation in neural networks, arXiv:cond-mat/0111169 [cond-mat.dis-nn], 2001.

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

Formula

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

From Peter Bala, Mar 20 2018: (Start)

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.

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)

Example

Triangle begins:
1 N=0
1 1 N=1
1 0 1 N=2
1 1 1 1 N=3
1 2 2 2 1 N=4

Crossrefs

Cf. A088219, A159853.

Sequence in context: A213126 A118400 A159853 * A101677 A364366 A152067

Adjacent sequences: A087695 A087696 A087697 * A087699 A087700 A087701

Keyword

nonn,tabl

Author

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

Status

approved