login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006963 Number of planar embedded labeled trees with n nodes: (2*n-3)!/(n-1)! for n >= 2, a(1) = 1.
(Formerly M3076)
30
1, 1, 3, 20, 210, 3024, 55440, 1235520, 32432400, 980179200, 33522128640, 1279935820800, 53970627110400, 2490952020480000, 124903451312640000, 6761440164390912000, 393008709555221760000, 24412776311194951680000, 1613955767240110694400000 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
For n>1: central terms of the triangle in A173333; cf. A001761, A001813. - Reinhard Zumkeller, Feb 19 2010
Can be obtained from the Vandermonde permanent of the first n positive integers; see A093883. - Clark Kimberling, Jan 02 2012
All trees can be embedded in the plane, but "planar embedded" means that orientation matters but rotation doesn't. For example, the n-star with n-1 edges has n! ways to label it, but rotation removes a factor of n-1. Another example, the n-path has n! ways to label it, but rotation removes a factor of 2. - Michael Somos, Aug 19 2014
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Ali Chouria, Vlad-Florin Drǎgoi, and Jean-Gabriel Luque, On recursively defined combinatorial classes and labelled trees, arXiv:2004.04203 [math.CO], 2020.
Robert Coquereaux and Jean-Bernard Zuber, Maps, immersions and permutations, Journal of Knot Theory and Its Ramifications, Vol. 25, No. 8 (2016), 1650047; arXiv preprint, arXiv:1507.03163 [math.CO], 2015-2016.
Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Pierre Leroux and Brahim Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80.
Pierre Leroux and Brahim Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80. (Annotated scanned copy)
J. W. Moon, Counting Labelled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970.
Ran J. Tessler, A Cayley-type identity for trees, arXiv:1809.00001 [math.CO], 2018.
FORMULA
E.g.f. for a(n+1), n >= 1, log(c(x)); c(x) = g.f. for Catalan numbers A000108. - Wolfdieter Lang
Integral representation as n-th moment of a positive function on a positive half-axis, in Maple notation: a(n) = int(x^n * erfc(sqrt(x)/2)/2, x=0..infinity), n=0, 1..., where erfc(x) is the complementary error function. - Karol A. Penson, Sep 27 2001
a(n) ~ 2^(-5/2)*n^-2*2^(2*n)*e^-n*n^n. - Joe Keane (jgk(AT)jgk.org), Jun 06 2002
a(n+1) = (n+1)*(n+2)*...*(2n-1) for n>=2. - Jaroslav Krizek, Nov 09 2010
E.g.f. (A(x)-1) is reversion of exp(-x)-exp(-2*x). - Vladimir Kruchinin, Jan 30 2012
G.f.: 1 + x*G(0) where G(k) = 1 + x*(2*k+1)*(4*k+3)/(k + 1 - 4*x*(k+1)^2*(4*k+5)/(4*x*(k+1)*(4*k+5) + (2*k+3)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 02 2013
E.g.f.: 1 + x*E(0) where E(k) = 1 + x*(2*k+1)*(4*k+3)/(2*(k + 1)^2 - 8*x*(k+1)^3*(4*k+5)/(4*x*(k+1)*(4*k+5) + (2*k+3)^2/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 02 2013
E.g.f: sqrt(1-4*x)/4 - 1/4 + 3*x/2 - x*log((1+sqrt(1-4*x))/2). - Robert Israel, Aug 20 2014
D-finite with recurrence (-n+1)*a(n) +2*(2*n-3)*(n-2)*a(n-1)=0. - R. J. Mathar, Jan 03 2018
From Amiram Eldar, Apr 03 2022: (Start)
Sum_{n>=1} 1/a(n) = 3/2 + 3*exp(1/4)*sqrt(Pi)*erf(1/2)/4, where erf is the error function.
Sum_{n>=1} (-1)^(n+1)/a(n) = 1/2 - sqrt(Pi)*erfi(1/2)/(4*exp(1/4)), where erfi is the imaginary error function. (End)
a(n) = A000407(n-2)/(n-1). - R. J. Mathar, Mar 30 2023
a(1) = 1; a(n) = (-1)^(n - 1)*Sum_{k=1..n - 1} (-1)^k*binomial(2*n - 3, n + k - 2)*Stirling1(n + k - 1, k + 1). - Detlef Meya, Jan 18 2024
EXAMPLE
G.f. = x + x^2 + 3*x^3 + 20*x^4 + 210*x^5 + 3024*x^6 + 55440*x^7 + 1235520*x^8 + ...
a(5) = 210 = 30 + 60 + 120 where 30 is for the star, 60 for the path, and 120 for the tree with one trivalent vertex. - Michael Somos, Aug 19 2014
MAPLE
1, seq((2*n-3)!/(n-1)!, n=2..30); # Robert Israel, Aug 20 2014
MATHEMATICA
Join[{1}, Table[(2n-3)!/(n-1)!, {n, 2, 20}]] (* Harvey P. Dale, Nov 03 2011 *)
a[ n_] := With[{m = n - 1}, If[m < 1, Boole[m == 0], m! SeriesCoefficient[ -Log[(1 + Sqrt[1 - 4 x]) / 2], {x, 0, m}]]] (* Michael Somos, Jul 01 2013 *)
a[ n_] := If[n < 2, Boole[n == 1], (2 n - 3)! / (n - 1)!]; (* Michael Somos, Aug 19 2014 *)
a[1] := 1; a[n_] := (-1)^(n - 1)*Sum[(-1)^k*Binomial[2*n - 3, n + k - 2]*StirlingS1[n + k - 1, k + 1], {k, 1, n - 1}]; Flatten[Table[a[n], {n, 1, 19}]] (* Detlef Meya, Jan 18 2024 *)
PROG
(Magma) [1] cat [Factorial(2*n-3)/Factorial(n-1): n in [2..20]]; // Vincenzo Librandi, Nov 12 2011
(PARI) {a(n) = n--; if( n<1, n==0, n! * polcoeff( -log( (1 + sqrt(1 - 4*x + x * O(x^n))) / 2), n))}; /* Michael Somos, Jul 01 2013 */
(SageMath)
def A006963(n): return 1 if n==1 else factorial(2*n-3)/factorial(n-1)
[A006963(n) for n in range(1, 31)] # G. C. Greubel, May 23 2023
CROSSREFS
Sequence in context: A218673 A230478 A014068 * A243426 A365438 A113333
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 10:59 EST 2024. Contains 370378 sequences. (Running on oeis4.)