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, 113144789723082206461, 4071967909087792857088
Offset: 0
Examples
E.g.f.: A(x) = 1 + x + x^2/2! + 4x^3/3! + 13x^4/4! + 96x^5/5! +...
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.)
Programs
-
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 *) -
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
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
a(0) = 1; a(n) = Sum_{k=0..floor((n-1)/2)} (2*k+1) * binomial(n-1,2*k) * a(2*k) * a(n-1-2*k). - Seiichi Manyama, Jul 05 2025
Extensions
Updated URL and author's e-mail address - R. J. Mathar, May 23 2010