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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036775 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 3 neighbors that are further away from the root than the node itself. 4
0, 1, 2, 9, 64, 620, 7620, 113610, 1992480, 40194000, 916927200, 23341071600, 655922836800, 20169411662400, 673645440468000, 24285190867938000, 939899116892736000, 38870133445791648000, 1710655202853140544000, 79826043011286892320000, 3936948118406837614080000, 204621522793150838094720000 (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 <= 3. - Geoffrey Critzer, Mar 22 2013

A preimage constraint on a function is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set. View a labeled rooted tree as an endofunction on the set {1,2,...,n} by sending every non-root node to its neighbor that is closer to the root and sending the root to itself. Thus a(n) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most 3 entries. - Benjamin Otto, Apr 08 2019

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). - Petros Hadjicostas, Jun 09 2019

LINKS

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

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 = 3.

Index entries for sequences related to rooted trees

FORMULA

E.g.f.: (for shifted sequence a(0)=0, a(1)=1, ...) A(x) satisfies A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3.

a(n) = 3*n!*Sum_{j=0..n+1} binomial(n+1, j)*Sum_{i=j..n+j} binomial(j, i-j)*2^(4*j-2*n-i-2)*6^(n+i+1)*binomial(n-j+1, 3*j-n-i-2)/6^(3*j). - Vladimir Kruchinin, Nov 21 2011

a(n) ~ sqrt(s/(1+r*s)) * n^n / (r^(n+1) * exp(n)), where r = 0.37589405207806352... is the root of the equation -8 + 21*r + 2*r^3 = 0 and s = 2.86947048655283754... is the root of the equation -12 + 36*s - 57*s^2 + 16*s^3 = 0. - Vaclav Kotesovec, Jan 08 2014

a(n) = (n-1)! * [x^(n-1)] e_3(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_3 * n^(-3/2) * r_3^-n. - Benjamin Otto, Apr 08 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!), {x, 0, nn}], x]; Table[a[n], {n, 0, nn}]/.s (* Geoffrey Critzer, Mar 22 2013 *)

Table[3*n!*Sum[Binomial[n+1, j]*Sum[Binomial[j, i-j]*2^(4*j-2*n-i-2)*6^(n+i+1)*Binomial[n-j+1, 3*j-n-i-2], {i, j, n+j}]/6^(3*j), {j, 0, n+1}], {n, 0, 20}] (* Vaclav Kotesovec after Vladimir Kruchinin, Jan 08 2014 *)

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

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

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

PROG

(Maxima) a(n):=3*n!*sum((binomial(n+1, j)*sum(binomial(j, i-j)*2^(4*j-2*n-i-2)*6^(n+i+1)*binomial(n-j+1, 3*j-n-i-2), i, j, n+j))/6^(3*j), j, 0, (n+1)); /* Vladimir Kruchinin, Nov 21 2011 */

(Python, from Benjamin Otto, Apr 08 2019)

# print first num_entries entries in the sequence

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

k=3; 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, A036776, A036777.

Column k=3 of A325201; see that entry for sequences related to other preimage constraints constructions. - Benjamin Otto, Apr 08 2019

Sequence in context: A331658 A269487 A179199 * A141209 A269770 A269649

Adjacent sequences:  A036772 A036773 A036774 * A036776 A036777 A036778

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 March 8 10:20 EST 2021. Contains 341948 sequences. (Running on oeis4.)