A005840 Expansion of (1-x)*e^x/(2-e^x).

1, 1, 2, 8, 46, 332, 2874, 29024, 334982, 4349492, 62749906, 995818760, 17239953438, 323335939292, 6530652186218, 141326092842416, 3262247252671414, 80009274870905732, 2077721713464798210, 56952857434896699992, 1643312099715631960910

Offset: 0

Author

Simon Plouffe

Keywords

• nonn
• easy
• nice

Comments

Also number of distinct resistances possible for n arbitrary resistors each connected in series or parallel with previous ones (cf. A051045).

The n-th term of A051045 uses the n different resistances 1, ..., n ohms, whereas the problem corresponding to A005840 allows arbitrary general resistances a1, a2, ..., an, chosen so as to give the maximum possible number of distinct equivalent resistances - Eric Weisstein

Stanley's Problem 5.4(a) involves threshold graphs; Problem 5.4(c) involves hyperplane arrangements.

a(n) is the number of labeled threshold graphs on n vertices. [This is more specific than the reference to Stanley.] [Svante Janson, Apr 01 2009]

If circuits were allowed that combine complex subcircuits in series or parallel, rather than requiring that one of them consists of a single resistor, then there are more additional possible resistances. For n = 4, there are additional 6 possible values. See illustration in links. - Kival Ngaokrajang, Aug 26 2013 (rephrased by Dave R.M. Langers, Nov 13 2013)

Conjecture: A285868 (with offset 1) shows the associated connected threshold graphs. - R. J. Mathar, Apr 29 2019

Re: above conjecture - the number of connected threshold graphs on n labeled vertices is A317057 (see also A053525). [David Galvin, Oct 18 2021]

Examples

			exp(x)*(1-x)/(2-exp(x)) = 1 + x + x^2 + 4/3*x^3 + 23/12*x^4 + 83/30*x^5 + 479/120*x^6 + 1814/315*x^7 + O(x^8); then the coefficients are multiplied by n! to get 1, 1, 2, 8, 46, 332, 2874, 29024, ...
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• 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
• J. S. Beissinger and U. N. Peled, Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials, J Graphs Combin., 3 (1987), 213--219. MR903610 [From _Svante Janson_, Apr 01 2009]
• Chao-Ping Chen and Xue-Feng Han, On Somos' quadratic recurrence constant, J. Number Theory, 166 (2016) 31-40. See page 34 equation (2.3).
• Mike de Vries, Graphical realizations of degree sequences, packing multiple colors and random graphs, Master's Thesis, Utrecht Univ. (Netherlands, 2023).
• Priyavrat Deshpande and Krishna Menon, Sketches, moves and partitions: counting regions of deformations of reflection arrangements, arXiv:2308.16653 [math.CO], 2023.
• P. Diaconis, S. Holmes and S. Janson, Threshold graph limits and random threshold graphs, Internet. math 5 (3) (2008) 267-320.
• D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.
• Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97-117.
• Andrew H. Hoefel and Jeff Mermin, Gotzmann squarefree ideals, Ill. J. Math. 56, No. 2, 397-414 (2012), Proposition 3.13.
• Ricky I. Liu, K. Mészáros and A. H. Morales, Flow polytopes and the space of diagonal harmonics, arXiv preprint arXiv:1610.08370 [math.CO], 2016.
• Kival Ngaokrajang, Illustration for n = 4; [a1, a2, a3, a4] = [3, 5, 7, 9]
• Seunghyun Seo, The Catalan Threshold Arrangement, Journal of Integer Sequences, 2017 Vol. 20, #17.1.1.
• Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.
• R. P. Stanley, A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Combinatorics. DIMACS Series in Discrete Math., Amer. Math. Soc., Vol. 4, pp. 555-570, 1991.
• Eric Weisstein's World of Mathematics, Resistor Network

Crossrefs

2*A053525(n), n>1.

Programs

Maple

A005840 := proc(n) option remember;
1 - n + add(binomial(n, k) * A005840(k), k = 0..n-1) end:
seq(A005840(n), n = 0..20); # Peter Luschny, Oct 25 2021

Mathematica

nn = 20; Range[0, nn]! CoefficientList[Series[(1 - x) Exp[x]/(2 - Exp[x]), {x, 0, nn}], x] (* Harvey P. Dale, Jul 20 2011 *)

PARI

my(x='x+O('x^30)); Vec(serlaplace((1-x)*exp(x)/(2-exp(x)))); \\ Michel Marcus, Jan 04 2016

Formula

a(n) ~ n! * (1-log(2)) / (log(2))^(n+1). - Vaclav Kotesovec, Sep 29 2014

E.g.f.: (1 - x) * e^x / (2 - e^x).

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

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

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

BINOMIAL transform of A053525. - Michael Somos, Aug 01 2016

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