|
|
A006963
|
|
Number of planar embedded labeled trees with n nodes: (2*n-3)!/(n-1)! for n >= 2, a(1) = 1.
(Formerly M3076)
|
|
33
|
|
|
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
|
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
|
J. W. Moon, Counting Labelled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970.
|
|
FORMULA
|
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
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
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(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
|
|
|
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|