login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036776 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 4 neighbors that are further away from the root than the node itself. 4
0, 1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

a(n) is the number of unordered rooted labeled trees such that each node has outdegree <= 4. - Geoffrey Critzer, Mar 23 2013

From pp. 3-4 in Takacs (1993), we see that n is the number of nodes in a labeled rooted tree such that each node has outdegree <= 3, and (as noted above by G. Critzer), a(n) is the number of such unordered rooted labeled trees (with n nodes). Apparently, the author of this sequence and other contributors exclude the node at the root, and thus the offset here is 0 (rather than 1). - Petros Hadjicostas, Jun 09 2019

LINKS

Table of n, a(n) for n=0..20.

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.

L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 4.

Index entries for sequences related to rooted trees

FORMULA

From Vladimir Kruchinin, Nov 22 2011: (Start)

E.g.f. A(x) satisfies: A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3 + (1/24)*A(x)^4.

a(n) = n!*Sum_{r=0..n+1} binomial(n+1,r)*Sum_{m=0..r} binomial(r,m)*Sum_{j=0..m} binomial(j,-r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m,j)*3^(-j). (End)

a(n) = (n-1)! * [x^(n-1)] e_4(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The Otto link above yields explicit constants c_k, r_k so that the columns are asymptotically c_4 * n^(-3/2) * r_4^-n. - Benjamin Otto, Apr 11 2019

MATHEMATICA

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

f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;

a[n_] := If[n == 1, 1, Derivative[n-1][f[4, n]][0]];

a /@ Range[0, 20] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas in A036777 *)

PROG

(Maxima)

a(n):=(n!*sum(binomial(n+1, r)*sum(binomial(r, m)*sum(binomial(j, -r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m, j)*(3)^(-j), j, 0, m), m, 0, r), r, 0, n+1)); /* Vladimir Kruchinin, Nov 22 2011 */

(Python, from Benjamin Otto, Apr 11 2019 )

# print first num_entries entries in the sequence

import math, sympy; x=sympy.symbols('x')

k=4; num_entries = 64

P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0, 1]; curr_pow = eP

for term in range(1, num_entries-1):

...curr_pow=(curr_pow*eP).expand()

...r.append(curr_pow.coeff(x**term)*math.factorial(term))

print(r)

CROSSREFS

Cf. A036774, A036775, A036777. Column k=4 of A325201; see that entry for sequences related to other preimage constraints constructions.

Sequence in context: A128577 A052514 A274395 * A036777 A325205 A325206

Adjacent sequences:  A036773 A036774 A036775 * A036777 A036778 A036779

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by N. J. A. Sloane, Jul 13 2019 using data from a duplicate of this entry that was submitted by Benjamin Otto, Apr 08 2019

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 09:13 EST 2021. Contains 340204 sequences. (Running on oeis4.)