|
%I M3076 #129 Jan 19 2024 08:18:55
%S 1,1,3,20,210,3024,55440,1235520,32432400,980179200,33522128640,
%T 1279935820800,53970627110400,2490952020480000,124903451312640000,
%U 6761440164390912000,393008709555221760000,24412776311194951680000,1613955767240110694400000
%N Number of planar embedded labeled trees with n nodes: (2*n-3)!/(n-1)! for n >= 2, a(1) = 1.
%C For n>1: central terms of the triangle in A173333; cf. A001761, A001813. - _Reinhard Zumkeller_, Feb 19 2010
%C Can be obtained from the Vandermonde permanent of the first n positive integers; see A093883. - _Clark Kimberling_, Jan 02 2012
%C 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
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006963/b006963.txt">Table of n, a(n) for n = 1..200</a>
%H David Callan, <a href="/A006963/a006963_1.pdf">A quick count of plane (or planar embedded) labeled trees</a>.
%H Ali Chouria, Vlad-Florin Drǎgoi, and Jean-Gabriel Luque, <a href="https://arxiv.org/abs/2004.04203">On recursively defined combinatorial classes and labelled trees</a>, arXiv:2004.04203 [math.CO], 2020.
%H Robert Coquereaux and Jean-Bernard Zuber, <a href="http://dx.doi.org/10.1142/S0218216516500474">Maps, immersions and permutations</a>, Journal of Knot Theory and Its Ramifications, Vol. 25, No. 8 (2016), 1650047; <a href="https://arxiv.org/abs/1507.03163">arXiv preprint</a>, arXiv:1507.03163 [math.CO], 2015-2016.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=109">Encyclopedia of Combinatorial Structures 109</a>.
%H Bradley Robert Jones, <a href="http://summit.sfu.ca/item/14554">On tree hook length formulas, Feynman rules and B-series</a>, Master's thesis, Simon Fraser University, 2014.
%H Pierre Leroux and Brahim Miloudi, <a href="http://www.labmath.uqam.ca/~annales/volumes/16-1/PDF/053-080.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80.
%H Pierre Leroux and Brahim Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80. (Annotated scanned copy)
%H J. W. Moon, <a href="http://www.math.ucla.edu/~pak/hidden/papers/Moon-counting_labelled_trees.pdf">Counting Labelled Trees</a>, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970.
%H Ran J. Tessler, <a href="https://arxiv.org/abs/1809.00001">A Cayley-type identity for trees</a>, arXiv:1809.00001 [math.CO], 2018.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>.
%F E.g.f. for a(n+1), n >= 1, log(c(x)); c(x) = g.f. for Catalan numbers A000108. - _Wolfdieter Lang_
%F 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
%F a(n) ~ 2^(-5/2)*n^-2*2^(2*n)*e^-n*n^n. - Joe Keane (jgk(AT)jgk.org), Jun 06 2002
%F a(n+1) = (n+1)*(n+2)*...*(2n-1) for n>=2. - _Jaroslav Krizek_, Nov 09 2010
%F E.g.f. (A(x)-1) is reversion of exp(-x)-exp(-2*x). - _Vladimir Kruchinin_, Jan 30 2012
%F 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
%F 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
%F 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
%F D-finite with recurrence (-n+1)*a(n) +2*(2*n-3)*(n-2)*a(n-1)=0. - _R. J. Mathar_, Jan 03 2018
%F From _Amiram Eldar_, Apr 03 2022: (Start)
%F Sum_{n>=1} 1/a(n) = 3/2 + 3*exp(1/4)*sqrt(Pi)*erf(1/2)/4, where erf is the error function.
%F 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)
%F a(n) = A000407(n-2)/(n-1). - _R. J. Mathar_, Mar 30 2023
%F 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
%e G.f. = x + x^2 + 3*x^3 + 20*x^4 + 210*x^5 + 3024*x^6 + 55440*x^7 + 1235520*x^8 + ...
%e 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
%p 1, seq((2*n-3)!/(n-1)!,n=2..30); # _Robert Israel_, Aug 20 2014
%t Join[{1},Table[(2n-3)!/(n-1)!,{n,2,20}]] (* _Harvey P. Dale_, Nov 03 2011 *)
%t 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 *)
%t a[ n_] := If[n < 2, Boole[n == 1], (2 n - 3)! / (n - 1)!]; (* _Michael Somos_, Aug 19 2014 *)
%t 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 *)
%o (Magma) [1] cat [Factorial(2*n-3)/Factorial(n-1): n in [2..20]]; // _Vincenzo Librandi_, Nov 12 2011
%o (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 */
%o (SageMath)
%o def A006963(n): return 1 if n==1 else factorial(2*n-3)/factorial(n-1)
%o [A006963(n) for n in range(1,31)] # _G. C. Greubel_, May 23 2023
%Y Cf. A000407, A001761, A001813, A173333.
%K nonn,easy,nice
%O 1,3
%A _Simon Plouffe_ and _N. J. A. Sloane_
| 