|
%I M1872 #101 Sep 06 2023 01:12:15
%S 1,1,2,8,46,332,2874,29024,334982,4349492,62749906,995818760,
%T 17239953438,323335939292,6530652186218,141326092842416,
%U 3262247252671414,80009274870905732,2077721713464798210,56952857434896699992,1643312099715631960910
%N Expansion of (1-x)*e^x/(2-e^x).
%C Also number of distinct resistances possible for n arbitrary resistors each connected in series or parallel with previous ones (cf. A051045).
%C 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
%C Stanley's Problem 5.4(a) involves threshold graphs; Problem 5.4(c) involves hyperplane arrangements.
%C 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]
%C 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)
%C Conjecture: A285868 (with offset 1) shows the associated connected threshold graphs. - _R. J. Mathar_, Apr 29 2019
%C Re: above conjecture - the number of connected threshold graphs on n labeled vertices is A317057 (see also A053525). [_David Galvin_, Oct 18 2021]
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.4(a).
%H T. D. Noe, <a href="/A005840/b005840.txt">Table of n, a(n) for n=0..100</a>
%H J. S. Beissinger and U. N. Peled, <a href="http://dx.doi.org/10.1007/BF01788543">Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials</a>, J Graphs Combin., 3 (1987), 213--219. MR903610 [From _Svante Janson_, Apr 01 2009]
%H Chao-Ping Chen and Xue-Feng Han, <a href="http://dx.doi.org/10.1016/j.jnt.2016.02.018">On Somos' quadratic recurrence constant</a>, J. Number Theory, 166 (2016) 31-40. See page 34 equation (2.3).
%H Mike de Vries, <a href="https://studenttheses.uu.nl/bitstream/handle/20.500.12932/43718/Thesis.pdf">Graphical realizations of degree sequences, packing multiple colors and random graphs</a>, Master's Thesis, Utrecht Univ. (Netherlands, 2023).
%H Priyavrat Deshpande and Krishna Menon, <a href="https://arxiv.org/abs/2308.16653">Sketches, moves and partitions: counting regions of deformations of reflection arrangements</a>, arXiv:2308.16653 [math.CO], 2023.
%H P. Diaconis, S. Holmes and S. Janson, <a href="https://doi.org/10.1080/15427951.2008.10129166">Threshold graph limits and random threshold graphs</a>, Internet. math 5 (3) (2008) 267-320.
%H D. Galvin, G. Wesley and B. Zacovic, <a href="https://arxiv.org/abs/2110.08953">Enumerating threshold graphs and some related graph classes</a>, arXiv:2110.08953 [math.CO], 2021.
%H Venkatesan Guruswami, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00022-9">Enumerative aspects of certain subclasses of perfect graphs</a>, Discrete Math. 205 (1999), 97-117.
%H Andrew H. Hoefel and Jeff Mermin, <a href="http://projecteuclid.org/euclid.ijm/1385129955">Gotzmann squarefree ideals</a>, Ill. J. Math. 56, No. 2, 397-414 (2012), Proposition 3.13.
%H Ricky I. Liu, K. Mészáros and A. H. Morales, <a href="http://arxiv.org/abs/1610.08370">Flow polytopes and the space of diagonal harmonics</a>, arXiv preprint arXiv:1610.08370 [math.CO], 2016.
%H Kival Ngaokrajang, <a href="/A005840/a005840.pdf">Illustration for n = 4; [a1, a2, a3, a4] = [3, 5, 7, 9]</a>
%H Seunghyun Seo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Seo/seo2.html">The Catalan Threshold Arrangement</a>, Journal of Integer Sequences, 2017 Vol. 20, #17.1.1.
%H Sam Spiro, <a href="https://arxiv.org/abs/1909.06518">Counting Threshold Graphs with Eulerian Numbers</a>, arXiv:1909.06518 [math.CO], 2019.
%H R. P. Stanley, <a href="http://dedekind.mit.edu/~rstan/pubs/pubfiles/83.pdf">A zonotope associated with graphical degree sequences</a>, in Applied Geometry and Discrete Combinatorics. DIMACS Series in Discrete Math., Amer. Math. Soc., Vol. 4, pp. 555-570, 1991.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ResistorNetwork.html">Resistor Network</a>
%F a(n) ~ n! * (1-log(2)) / (log(2))^(n+1). - _Vaclav Kotesovec_, Sep 29 2014
%F E.g.f.: (1 - x) * e^x / (2 - e^x).
%F E.g.f. A(x) satisfies (1 - x) * A'(x) = A(x) * (A(x) - x). - _Michael Somos_, Aug 01 2016
%F 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
%F a(n) = (1-n) + Sum_{k=0..n-1} binomial(n, k) * a(k). - _Michael Somos_, Aug 01 2016
%F BINOMIAL transform of A053525. - _Michael Somos_, Aug 01 2016
%F a(n) = Sum_{k=1..n-1} (n-k)*A008292(n-1,k-1)*2^k, for n>=2. - _Sam Spiro_, Sep 22 2019
%e 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, ...
%p A005840 := proc(n) option remember;
%p 1 - n + add(binomial(n, k) * A005840(k), k = 0..n-1) end:
%p seq(A005840(n), n = 0..20); # _Peter Luschny_, Oct 25 2021
%t nn = 20; Range[0, nn]! CoefficientList[Series[(1 - x) Exp[x]/(2 - Exp[x]), {x, 0, nn}], x] (* _Harvey P. Dale_, Jul 20 2011 *)
%o (PARI) my(x='x+O('x^30)); Vec(serlaplace((1-x)*exp(x)/(2-exp(x)))); \\ _Michel Marcus_, Jan 04 2016
%Y 2*A053525(n), n>1.
%K nonn,easy,nice
%O 0,3
%A _Simon Plouffe_
|
