A053525 Expansion of e.g.f.: (1-x)/(2-exp(x)).

1, 0, 1, 4, 23, 166, 1437, 14512, 167491, 2174746, 31374953, 497909380, 8619976719, 161667969646, 3265326093109, 70663046421208, 1631123626335707, 40004637435452866, 1038860856732399105, 28476428717448349996, 821656049857815980455

Offset: 0

Author

N. J. A. Sloane, Jan 15 2000

Keywords

• nonn
• nice
• easy

Comments

The number of connected labeled threshold graphs on n vertices. - Sam Spiro, Sep 22 2019

Also the number of 2-interval parking functions of size n. - Sam Spiro, Sep 24 2019

Examples

			G.f. = 1 + x^2 + 4*x^3 + 23*x^4 + 166*x^5 + 1437*x^6 + 14512*x^7 + ...
		

References

• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.4(a).

Links

• T. D. Noe, Table of n, a(n) for n = 0..100
• Jean-Christophe Aval, Adrien Boussicault, and Philippe Nadeau, Tree-like Tableaux, Electronic Journal of Combinatorics, 20(4), 2013, #P34.
• Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97-117. See Th. 6.3.
• Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.
• Sam Spiro, Subset Parking Functions, arXiv:1909.10109 [math.CO], 2019.

Crossrefs

Cf. A000670, A005840, A052882.

Programs

Magma

m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (1-x)/(2-Exp(x)) )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Mar 15 2019

Maple

A053525 := proc(n) option remember;
`if`(n < 2, 1 - n, add(binomial(n, k) * A053525(k), k = 0..n-1)) end:
seq(A053525(n), n = 0..20); # Peter Luschny, Oct 24 2021

Mathematica

With[{nn=20},CoefficientList[Series[(1-x)/(2-Exp[x]),{x,0,nn}], x] Range[0,nn]!] (* Harvey P. Dale, May 17 2012 *)

PARI

{a(n) = if( n<0, 0, n! * polcoeff( (1 - x) / (2 - exp(x + x*O(x^n))), n))}; /* Michael Somos, Aug 01 2016 */

Sage

m = 25; T = taylor((1-x)/(2-exp(x)), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, Mar 15 2019

Formula

a(n) = c(n) - n*c(n-1) where c() = A000670.

a(n) ~ n!/2 * (1-log(2))/(log(2))^(n+1). - Vaclav Kotesovec, Dec 08 2012

Binomial transform is A005840. - Michael Somos, Aug 01 2016

a(n) = Sum_{k=0..n-1} binomial(n, k) * a(k), n>1. - Michael Somos, Aug 01 2016

a(n) = A005840(n) / 2, n>1. - Michael Somos, Aug 01 2016

E.g.f. A(x) satisfies (1 - x) * A'(x) = A(x) * (x - 2 + 2*A(x)). - Michael Somos, Aug 01 2016

a(n) = Sum_{k=1..n-1} (n-k)*A008292(n-1,k-1)*2^(k-1), valid for n>=2. - Sam Spiro, Sep 22 2019