A117402 Row sums of triangle A117401: a(n) = Sum_{k=0..n} 2^((n-k)*k) for n>=0.

1, 2, 4, 10, 34, 162, 1090, 10370, 139522, 2654722, 71435266, 2718435330, 146299424770, 11134711111682, 1198484887715842, 182431106853797890, 39271952800672710658, 11955805018770498519042, 5147453397489773531365378

Offset: 0

Author

Paul D. Hanna, Mar 12 2006

Keywords

• nonn

Comments

a(n) is the number of 2-colored labeled graphs (as in A047863) such that the black nodes are labeled with {1,2,...,k} where k, 0<=k<=n, is the number of black nodes and the white nodes are labeled with {k+1,k+2,...,n}. These graphs form the desired binomial poset (for the case q=2) in the "task left to the reader" in the Stanley reference below. - Geoffrey Critzer, May 31 2020

Examples

			A(x) = 1/(1-x) + x/(1-2x) + x^2/(1-4x) + x^3/(1-8x) + ...
		

References

• R. P. Stanley, Enumerative Combinatorics, Volume I, Second Edition, Cambridge, 2012, Example 3.18.3 e, page 323.

Links

• Robert Israel, Table of n, a(n) for n = 0..116

Crossrefs

Cf. A117401 (triangle), A117403 (antidiagonal sums).

Programs

Magma

[(&+[2^(k*(n-k)): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Jun 28 2021

Maple

N:= 25:
G:= series(add(x^n/(1-2^n*x),n=0..N),x,N+1):
seq(coeff(G,x,n),n=0..N)); # Robert Israel, Dec 11 2018

Mathematica

a[n_]:= Sum[2^((n-k)*k), {k,0,n}]; Array[a, 20, 0] (* Amiram Eldar, Dec 12 2018 *)

PARI

a(n)=sum(k=0,n,2^((n-k)*k))

Sage

[sum(2^(k*(n-k)) for k in (0..n)) for n in (0..20)] # G. C. Greubel, Jun 28 2021

Formula

G.f.: A(x) = Sum_{n>=0} x^n/(1-2^n*x).

Let E(x) = Sum_{n>=0} x^n/2^C(n,2). Then E(x)^2 = Sum_{n>=0} a(n)*x^n/2^C(n,2). - Geoffrey Critzer, May 31 2020

a(n) ~ c * 2^(n^2/4), where c = EllipticTheta[3, 0, 1/2] = JacobiTheta3(0,1/2) = 2.128936827211877158669458548544951324612516539940878092889... if n is even and c = EllipticTheta[2, 0, 1/2] = JacobiTheta2(0,1/2) = 2.128931250513027558591613402575350180853805396958448940969... if n is odd. - Vaclav Kotesovec, Jun 28 2021