A037293 a(n) = Sum_{i=0..2^(n-1)} binomial(2^(n-1), i)^2.

1, 2, 6, 70, 12870, 601080390, 1832624140942590534, 23951146041928082866135587776380551750, 5768658823449206338089748357862286887740211701975162032608436567264518750790

Offset: 0

Author

John Tromp, Dec 11 1999

Keywords

• nonn
• easy

Comments

For n >= 1, a(n) is the number of n-variable balanced Boolean functions. A Boolean function is balanced if it takes the values 0 and 1 an equal number of times. - Aniruddha Biswas, Nov 05 2024

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..11
• Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
• Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See p. 2.
• Niklas G. Johansson, Efficient Simulation of the Deutsch-Jozsa Algorithm, Master's Project, Department of Electrical Engineering & Department of Physics, Chemistry and Biology, Linkoping University, April, 2015. See Eq. (3.15).

Crossrefs

Cf. A000079, A000984, A001405, A069954, A000721.

Programs

Maple

a:= n-> (t-> binomial(t, iquo(t, 2)))(2^n):
seq(a(n), n=0..8);  # Alois P. Heinz, Jan 14 2017
#
a:=n->sum(binomial(2^(n-1),i)^2,i=0..2^(n-1)); seq(a(n),n=0..8);
a:=n->piecewise(n=0,1,binomial(2^n,2^(n-1))); seq(a(n),n=0..8); # Martin Renner, Jan 16 2017

Mathematica

Flatten[{1,Table[Binomial[2^n, 2^(n-1)], {n, 1, 8}]}] (* Vaclav Kotesovec, Nov 13 2014 *)

PARI

a(n) = sum(i=0, 2^(n-1), binomial(2^(n-1), i)^2)  \\ Michel Marcus, Jun 09 2013

Python

from math import comb
def A037293(n): return comb(1<Chai Wah Wu, Dec 11 2024

Formula

a(n) = A001405(2^n). - Labos Elemer, Apr 11 2001

a(n) ~ 2^(2^n - n/2 + 1/2)/ sqrt(Pi). - Vaclav Kotesovec, Nov 13 2014

a(n) = A000984(2^(n-1)) = binomial(2^n,2^(n-1)) = (2^n)!/((2^(n-1))!)^2 for n > 0. - Martin Renner, Jan 16 2017

a(n) = (2^(2^n)*(2^n + 2)*(1/2*(2^n + 1))!)/(sqrt(Pi)*(2^n + 1)*(1/2*(2^n + 2))!) = (2^(2^n)*(2^n + 2)*Gamma((2^n+3)/2))/(sqrt(Pi)*(2^n + 1)*Gamma(2^(n-1)+2)) for n > 0. - Alexander R. Povolotsky, Nov 19 2022

a(n) = 2 * A069954(n-1) for n > 0. - Tilman Piesk, Oct 11 2024

Extensions

More terms from Erich Friedman