A058014 Number of labeled trees with n+1 nodes such that the degrees of all nodes, excluding the first node, are odd.

1, 1, 1, 4, 13, 96, 541, 5888, 47545, 686080, 7231801, 130179072, 1695106117, 36590059520, 567547087381, 14290429935616, 257320926233329, 7405376630685696, 151856004814953841, 4917457306800619520

Offset

0,4

Links

Seiichi Manyama, Table of n, a(n) for n = 0..422

Alexander Postnikov, Papers.

A. Postnikov and R. P. Stanley, Deformations of Coxeter hyperplane arrangements, J. Combin. Theory, Ser. A, 91 (2000), 544-597. (Section 10.2.)

Formula

a(n) = (1/2^n) * Sum_{k=0..n} binomial(n,k) * (n + 1 - 2*k)^(n-1).

From Paul D. Hanna, Mar 29 2008: (Start)

E.g.f. satisfies A(x) = exp( x*[A(x) + 1/A(x)]/2 ).

E.g.f. A(x) equals the inverse function of 2*x*log(x)/(1 + x^2).

Let r = radius of convergence of A(x), then r = 0.6627434193491815809747420971092529070562335491150224... and A(r) = 3.31905014223729720342271370055697247448941708369151595... where A(r) and r satisfy A(r) = exp( (A(r)^2 + 1)/(A(r)^2 - 1) ) and r = 2*A(r)/(A(r)^2 - 1). (End)

E.g.f. A(x)=exp(B(x)), B(x) satisfies B(x)=x*cosh(B(x)). [Vladimir Kruchinin, Apr 19 2011]

a(n) ~ (1-(-1)^n*s^2)/s * n^(n-1) * ((1-s^2)/(2*s))^n / exp(n), where s = 0.3012910191606573456... is the root of the equation (1+s^2) = (s^2-1)*log(s), r = 2*s/(1-s^2). - Vaclav Kotesovec, Jan 08 2014

E.g.f. satisfies A(-x) = 1/A(x). - Alexander Burstein, Oct 26 2021

Example

E.g.f.: A(x) = 1 + x + x^2/2! + 4x^3/3! + 13x^4/4! + 96x^5/5! +...

Maple

a := n -> 2^(-n)*add(binomial(n, k)*(n+1-2*k)^(n-1), k=0..n);

Mathematica

a[n_] := Sum[((n-2k+1)^(n-1)*n!) / (k!*(n-k)!), {k, 0, n}] / 2^n; a[1] = 1; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 14 2011, after Maple *)

Prog

(PARI) {a(n)=local(A=1+x); for(i=0, n, A=exp(x*(A+1/(A +x*O(x^n)))/2)); n!*polcoeff(A, n)} - Paul D. Hanna, Mar 29 2008
(PARI) {a(n) = sum(k=0, n, binomial(n, k)*(n+1-2*k)^(n-1))/2^n} \\ Seiichi Manyama, Sep 27 2020

Crossrefs

Cf. bisections: A007106, A143601.

Cf. A138764 (variant).

Sequence in context: A326565 A041433 A222764 * A290392 A261785 A331013

Adjacent sequences: A058011 A058012 A058013 * A058015 A058016 A058017

Keyword

easy,nice,nonn

Author

Alex Postnikov (apost(AT)math.mit.edu), Nov 13 2000

Extensions

Updated URL and author's e-mail address - R. J. Mathar, May 23 2010

Status

approved