A036770 -id:A036770 - cp's OEIS frontend

A036771 Number of labeled rooted trees with a degree constraint: ((3n)!/(6^n)) binomial(3*n + 1, n).

1, 4, 420, 201600, 264264000, 734557824000, 3723191087616000, 31125877492469760000, 399532678960326912000000, 7462849882264211635200000000, 194563959280510261541299200000000, 6847568575944052279580806348800000000, 316573366618757452963440048714547200000000

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of labeled rooted unordered trees on 3n+1 nodes such that each node has zero or three children. - Geoffrey Critzer, Mar 14 2013

			E.g.f. (with interpolated zeros): 1*x/1! + 4*x^4/4! + 420*x^7/7! + 201600*x^10/10! + 264264000*x^13/13! + 734557824000*x^16/16! + 3723191087616000*x^19/19! + ... = x + 1/6*x^4 + 1/12*x^7 + 1/18*x^10 + 55/1296*x^13 + 91/2592*x^16 + 119/3888*x^19 + ... - _Petros Hadjicostas_, Jun 07 2019

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 47.
Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10; see Eqs. (12) and (13) on p. 4.
Wikipedia, Cubic function.
Index entries for sequences related to rooted trees

Cf. A036770, A036772, A036773.

spec := [S,{S=Union(Z,Prod(Z,Set(S,card=3)))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
A := proc(x) 2*sqrt(2)*cos(1/3*arccos(-3/2*x*sqrt(1/2*x)) - 2/3*Pi)/sqrt(x); end proc;
series(A(x), x = 0, 80);  # Petros Hadjicostas, Jun 07 2019

nn=34;f[x_]:=Sum[a[n]x^n/n!,{n,0,nn}];s=SolveAlways[0=Series[f[x]-x (1+f[x]^3/3!),{x,0,nn}],x];Table[a[n],{n,1,nn,3}]/.s  (* Geoffrey Critzer, Mar 14 2013 *)

from math import factorial, comb
def A036771(n): return factorial(3*n)*comb(3*n+1,n)//3**n>>n  # Chai Wah Wu, Nov 28 2023

E.g.f. (with interpolated zeros): -(1/2)/x * ((-3*x + ((-8 + 9*x^3) / x)^(1/2)) * x^2)^(1/3) - 1/((-3*x + ((-8 + 9*x^3) / x)^(1/2)) * x^2)^(1/3) - (1/2)*I*3^(1/2) * (1/x * ((-3*x + ((-8 + 9*x^3) / x)^(1/2)) * x^2)^(1/3) - 2/((-3*x + ((-8 + 9*x^3) / x)^(1/2)) * x^2)^(1/3)).
Recurrence (with interpolated zeros): Define sequence (b(n): n >= 0) by b(3*n + 1) = a(n) for n >= 0 and b(n) = 0 otherwise. Then it satisfies the recurrence (-9*n^4 - 45*n^3 - 63*n^2 - 27*n) * b(n) + (8*n + 28) * b(n+3) = 0 for n >= 0 with b(0) = 0, b(1) = 1, and b(2) = 0. [Corrected by Petros Hadjicostas, Jun 07 2019]
E.g.f. with interpolated zeros satisfies: A(x) = x*(1 + A(x)^3/3!). -  Geoffrey Critzer, Mar 14 2013
From Petros Hadjicostas, Jun 07 2019: (Start)
In other words, if A(x) = Sum_{n >= 0} b(n)*x^n/n! = Sum_{m >= 0} a(m)*x^(3*m+1)/(3*m+1)!, then  A(x) = x*(1 + A(x)^3/3!).
E.g.f. of (b(n): n >= 1) according to the link for ECS 47 above: Let f(x) = ((-3*x + sqrt((9*x^3 - 8)/x)) * x^2)^(1/3). Then the e.g.f. of (b(n): n >= 1), which includes interpolated zeros, is -f(x)/(2*x) - 1/f(x) - (I*sqrt(3)/2)*(f(x)/x - 2/f(x)). (It is not clear whether it is correct or useful.)
E.g.f. using the solution of a cubic in terms of trigonometric functions: A(x) = (2*sqrt(2)/sqrt(|x|)) * cos( (1/3) * arccos((-3*|x|/2) * sqrt(|x|/2)) - 2*Pi/3 ) for 0 < |x| < 2/9^(1/3). (We have lim_{x -> 0} A(x) = 0.) (End)
Recurrence without interpolated zeros: -3 * (3*n + 4) * (3*n + 1) * (3*n + 2)^2 * a(n) + 4 * (2*n + 3) * a(n + 1) = 0 for n >= 0 with a(0) = 1. - Petros Hadjicostas, Jun 08 2019

A052510 Number of labeled planar binary trees with 2n-1 elements (external nodes or internal nodes).

Original entry on oeis.org

1, 6, 240, 25200, 5080320, 1676505600, 821966745600, 560992303872000, 508633022177280000, 591438478187741184000, 858123464716031754240000, 1519736656012092236759040000, 3226517823533365056503808000000, 8089341114715793820234547200000000

Offset: 1

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Equals central terms of A174449. - G. C. Greubel, Nov 29 2021

G. C. Greubel, Table of n, a(n) for n = 1..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 54 [Link is broken.]

Cf. A000108, A036770, A101921, A174449.

[Factorial(2*n-1)*Catalan(n-1): n in [1..15]]; // G. C. Greubel, Nov 29 2021

spec := [S, {S=Union(Z, Prod(Z, S, S))}, labeled]:
seq(combstruct[count](spec, size=2*n-1), n=1..14);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      4*(n-1)*(2*n-3)*(2*n-1)*a(n-1)/n)
    end:
seq(a(n), n=1..22);  # Alois P. Heinz, Dec 03 2019

nn=20;f[x_]:=Sum[a[n]x^n/n!,{n,0,nn}];s=SolveAlways[0==Series[f[x]-x(1+f[x]^2),{x,0,nn}],x];Select[Flatten[Table[a[n],{n,0,nn}]/.s],#>0&]  (* Geoffrey Critzer, Mar 23 2013 *)
RecurrenceTable[{a[1]==1, n*a[n]==(4*(n-1)*(2*n-3)*(2*n-1))*a[n-1]}, a[n], {n,1,22}] (* Georg Fischer, Dec 03 2019 following Alois P. Heinz *)
a[n_]:= CatalanNumber[n-1] Gamma[2n]; Array[a,14] (* Peter Luschny, Dec 03 2019 *)

a=vector(28);print1(a[1]=1,", ");forstep(k=1,#a-2,2,print1(a[k+2]=4*a[k]*(k^3+3*k^2+2*k)/(k+3),", ")) \\ Hugo Pfoertner, Dec 04 2019

[factorial(2*n-1)*catalan_number(n-1) for n in (1..15)] # G. C. Greubel, Nov 29 2021

E.g.f.: ((1/2)/x)*(1-sqrt(1-4*x^2)). [With interspersed zeros.]
Recurrence: b(1)=1, b(2)=0, b(n)=(4*n^3-12*n^2+8*n)*b(n-2)/(n+1) and a(n) = b(2*n-1).
a(n) = (2n-1)/n * ( (2(n-1))! / (n-1)! )^2. - Travis Kowalski (kowalski(AT)euclid.UCSD.Edu), Dec 15 2000
i*sin(arcsec(2*x)) = -1/(2*x) + x + 6*x^3/3! + 240*x^5/5! + 25200*x^7/7! + ...
a(n) = 2^(n-1) * A036770(n).
a(n) = (2*n-1)! * A000108(n-1). - Michail Stamatakis, Jan 24 2019
Sum_{n>=1} 1/a(n) = 1 + StruveL(0, 1/2)*Pi/8 + StruveL(1, 1/2)*Pi/4, where StruveL is the modified Struve function. - Amiram Eldar, Dec 04 2022

Edited by Georg Fischer, Dec 03 2019

A093049 n-1 minus exponent of 2 in n, a(0) = 0.

Original entry on oeis.org

0, 0, 0, 2, 1, 4, 4, 6, 4, 8, 8, 10, 9, 12, 12, 14, 11, 16, 16, 18, 17, 20, 20, 22, 20, 24, 24, 26, 25, 28, 28, 30, 26, 32, 32, 34, 33, 36, 36, 38, 36, 40, 40, 42, 41, 44, 44, 46, 43, 48, 48, 50, 49, 52, 52, 54, 52, 56, 56, 58, 57, 60, 60, 62, 57, 64, 64, 66, 65, 68

Offset: 0

Ralf Stephan, Mar 16 2004

nonn

			G.f. = 2*x^3 + x^4 + 4*x^5 + 4*x^6 + 6*x^7 + 4*x^8 + 8*x^9 + 8*x^10 + ... - _Michael Somos_, Jan 25 2020

a(n) = n - A007814(n) - 1 = A093048(n) - 1, n>0.

a(n) is the exponent of 2 in A001761(n+1), A002105(n), A002682(n-1), A006963(n), A036770(n-1), A059837(n), A084623(n), |A003707(n)|, |A011859(n)|.

a[ n_] := If[ n == 0, 0, n - 1 - IntegerExponent[n, 2]]; (* Michael Somos, Jan 25 2020 *)

a(n)=if(n<1,0,if(n%2==0,a(n/2)+n/2-1,n-1))

{a(n) = if( n, n - 1 - valuation(n, 2))}; /* Michael Somos, Jan 25 2020 */

def A093049(n): return n-1-(~n& n-1).bit_length() if n else 0 # Chai Wah Wu, Jul 07 2022

Recurrence: a(2n) = a(n) + n - 1, a(2n+1) = 2n.

G.f.: sum(k>=0, t^3(t+2)/(1-t^2)^2, t=x^2^k).

A036772 Number of labeled rooted trees with a degree constraint: ((4n)!/(24^n)) binomial(4*n+1, n).

Original entry on oeis.org

1, 5, 2520, 9909900, 150089940000, 6217438242015000, 574985352122181000000, 103753754577643425255000000, 33189544956070738228953960000000, 17517292900368819935211385551000000000, 14427024664929016470240101675459976000000000

Offset: 0

N. J. A. Sloane

nonn

L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10; see Eq. (13) on p. 4 (with r = 4).
Index entries for sequences related to rooted trees

Cf. A036770, A036771, A036773.

Table[(4n)!/24^n Binomial[4n+1,n],{n,0,10}] (* Harvey P. Dale, Aug 10 2011 *)

From Petros Hadjicostas, Jun 08 2019: (Start)
Recurrence (with no interpolated zeros): -8 * (4*n + 1) * (4*n + 3)^2 * (2*n + 1)^2 * (4*n + 5) * a(n) + (81*n^2 + 162*n + 72) * a(n + 1) = 0 for n >= 0 with a(0) = 1.
E.g.f. (with interpolated zeros): Let G(x) = Sum_{n >= 0} a(n)*x^(4*n + 1)/(4*n + 1)!. Then the e.g.f. satisfies G(x) = x * (1 + G(x)^4/4!).
(End)

A036773 Number of labeled rooted trees with a degree constraint: ((5n)!/(120^n)) C(5*n+1, n).

Original entry on oeis.org

1, 6, 13860, 423783360, 70220478968640, 41004669682770393600, 65405789473547026656472320, 240729724316568938710767014707200, 1813083536072533851678174232377806438400, 25541737277107694920826740625991927645705830400

Offset: 0

N. J. A. Sloane

nonn

L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10; see Eq. (13) on p. 4 (with r = 5).
Index entries for sequences related to rooted trees

Cf. A036770, A036771, A036772.

E.g.f. with interpolated zeros: Let G(x) = Sum_{n >= 0} a(n)*x^(5*n + 1)/(5*n + 1)!. Then this e.g.f. satisfies the equation G(x) = x*(1 + G(x)^5/5!). - Petros Hadjicostas, Jun 08 2019

A126934 Define an array by d(m, 0) = 1, d(m, 1) = m; d(m, k) = (m - k + 1) d(m+1, k-1) - (k-1) (m+1) d(m+2, k-2). Sequence gives d(0,2n).

Original entry on oeis.org

1, -2, 36, -1800, 176400, -28576800, 6915585600, -2337467932800, 1051860569760000, -607975409321280000, 438958245529964160000, -387161172557428389120000, 409616520565759235688960000, -512020650707199044611200000000, 746526108731096207043129600000000, -1255656914885703820246543987200000000

Offset: 0

Vincent v.d. Noort, Mar 21 2007

sign

|a(n)| is the number of functions f:{1,2,...,2n}->{1,2,...,2n} such that each element has either 0 or 2 preimages. That is, |(f^-1)(x)| is in {0,2} for all x in {1,2,...,2n}. - Geoffrey Critzer, Feb 24 2012.

V. van der Noort and N. J. A. Sloane, Paper in preparation, 2007.

G. C. Greubel, Table of n, a(n) for n = 0..150
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 131.
S. Goodenough, C. Lavault, On subsets of Riordan subgroups and Heisenberg--Weyl algebra, arXiv preprint arXiv:1404.1894 [cs.DM], 2014-2016.
S. Goodenough, C. Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16.

See A105937 for the full array.

A200850 The number of forests of labeled rooted strictly binary trees (each vertex has exactly two children or none) on n nodes.

Original entry on oeis.org

1, 1, 1, 4, 13, 91, 511, 5146, 41329, 544573, 5704381, 93001096, 1203040741, 23391560479, 360416247283, 8142893840446, 145661102170081, 3750604005834361, 76415186203927129, 2209120481052933868, 50510327090854792861, 1620053085929867956291

Offset: 0

Geoffrey Critzer, Nov 23 2011

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A036770.

a:= proc(n) option remember;
      `if`(n=0, 1, add((n-1)!/(n-1-2*j)! *binomial(2*j+1, j)/
                       (2^j) *a(n-1-2*j), j=0..(n-1)/2))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 23 2011

Range[0,19]! CoefficientList[Series[Exp[(1-(1-2x^2)^(1/2))/x],{x,0,19}],x]

E.g.f.: exp(A(x)) where A(x) is the e.g.f. for A036770.
Recurrence: 2*a(n) = -(n-2)*(n+1)*a(n-1) + 2*(n-1)*(2*n-3)*a(n-2) + 2*(n-3)*(n-2)*(n-1)^2*a(n-3). - Vaclav Kotesovec, Aug 14 2013
a(n) ~ 2^(n/2+1/2)*n^(n-1)*exp(-n-sqrt(2))*(exp(2*sqrt(2))-(-1)^n). - Vaclav Kotesovec, Aug 14 2013

A052505 Number of labeled 3-constrained functional graphs.

Original entry on oeis.org

1, 3, 300, 141120, 182952000, 505008504000, 2547446533632000, 21222189199411200000, 271682221693022300160000, 5064076705822143609600000000, 131801391770668241689267200000000, 4632178742550388306775251353600000000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the number of functions f:{1,2,...,3n}->{1,2,...,3n} such that the preimage of every element has cardinality 0 or 3. - Geoffrey Critzer, Mar 14 2017

			a(1) = 3 because there are 3 functions from {1,2,3} into {1,2,3} in which the preimage of every element in {1,2,3} is empty or contains 3 elements, namely the 3 constant functions.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 38
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 131.

Cf. A036770.

spec := [S, {g=Union(Z, Prod(Z, Set(g, card=3))), S=Set(Cycle(Prod(Z, Set(g, card=2))))}, labeled]: seq(combstruct[count](spec, size=3*n), n=0..20);

nn = 33; A[z]:= Sum[a[n] z^n, {n, 0, nn}];
sol = SolveAlways[0==Series[A[z] - z*(1+A[z]^3/6), {z,0,nn}], z];
Select[Range[0, nn]!*Flatten[CoefficientList[Series[1/(1-zA[z]^2/2)/. sol, {z, 0, nn}], z]], # > 0 &] (* Geoffrey Critzer, Mar 14 2017 *)
Select[RecurrenceTable[{(-9*n^4-54*n^3-117*n^2-108*n-36)*a[n]+(8*n+12)*a[n+3]==0, a[0]==1, a[1]==0, a[2]==0}, a, {n,0,33}], # > 0 &] (* Georg Fischer, Dec 06 2019 *)

E.g.f.: -2/(-2+x*RootOf(-6*_Z+6*x+x*_Z^3)^2).

Recurrence: {a(1)=0, (-9*n^4-54*n^3-117*n^2-108*n-36)*a(n)+(8*n+12)*a(n+3), a(2)=0, a(4)=0, a(3)=3, a(5)=0}. [interpolated with 0,0]

a(7)-a(11) from Geoffrey Critzer, Mar 14 2017

cp's OEIS Frontend

A036771 Number of labeled rooted trees with a degree constraint: ((3*n)!/(6^n)) * binomial(3*n + 1, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A052510 Number of labeled planar binary trees with 2n-1 elements (external nodes or internal nodes).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A093049 n-1 minus exponent of 2 in n, a(0) = 0.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A036772 Number of labeled rooted trees with a degree constraint: ((4*n)!/(24^n)) * binomial(4*n+1, n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A036773 Number of labeled rooted trees with a degree constraint: ((5*n)!/(120^n)) * C(5*n+1, n).

Views

Author

Keywords

Links

Crossrefs

Formula

A126934 Define an array by d(m, 0) = 1, d(m, 1) = m; d(m, k) = (m - k + 1) d(m+1, k-1) - (k-1) (m+1) d(m+2, k-2). Sequence gives d(0,2n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A200850 The number of forests of labeled rooted strictly binary trees (each vertex has exactly two children or none) on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A036771 Number of labeled rooted trees with a degree constraint: ((3n)!/(6^n)) binomial(3*n + 1, n).

A036772 Number of labeled rooted trees with a degree constraint: ((4n)!/(24^n)) binomial(4*n+1, n).

A036773 Number of labeled rooted trees with a degree constraint: ((5n)!/(120^n)) C(5*n+1, n).