A325201 -id:A325201 - cp's OEIS frontend

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.

0, 1, 2, 9, 64, 620, 7620, 113610, 1992480, 40194000, 916927200, 23341071600, 655922836800, 20169411662400, 673645440468000, 24285190867938000, 939899116892736000, 38870133445791648000, 1710655202853140544000, 79826043011286892320000, 3936948118406837614080000, 204621522793150838094720000

Offset: 0

N. J. A. Sloane

nonn

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

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

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

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 *)

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 */

# 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) # Benjamin Otto, Apr 08 2019

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

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

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.

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000

Offset: 0

N. J. A. Sloane

nonn

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

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

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

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 *)

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 */

# 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) # Benjamin Otto, Apr 11 2019

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

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

A325205 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 6 neighbors that are further away from the root than the node itself.

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7776, 117649, 2097144, 43046136, 999970020, 25936053990, 742947675624, 23295384644532, 793591829158128, 29187143427692250, 1152639088016576160, 48646833059722978080, 2185150741063924810176, 104085328898784937079376, 5240461483486301616704160

Offset: 0

Benjamin Otto, Apr 11 2019

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 6 entries.

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

Column k=6 of A325201; see that entry for sequences related to other preimage constraints constructions.

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=6; 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)

a(n) = (n-1)! * [x^(n-1)] e_6(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The link above yields explicit constants c_k, r_k so that the columns are asymptotically c_6 * n^(-3/2) * r_6^-n.

A325206 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 7 neighbors that are further away from the root than the node itself.

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046712, 999999180, 25937373990, 743005653984, 23297946618804, 793707788417544, 29192570114517810, 1152902963147295360, 48660197610533102880, 2185856466420637543104, 104124189019562479248624, 5242691958381764070687360

Offset: 0

Benjamin Otto, Apr 11 2019

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

Column k=7 of A325201; see that entry for sequences related to other preimage constraints constructions.

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=7; 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)

a(n) = (n-1)! * [x^(n-1)] e_7(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The link above yields explicit constants c_k, r_k so that the columns are asymptotically c_7 * n^(-3/2) * r_7^-n.

A325207 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 8 neighbors that are further away from the root than the node itself.

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 999999990, 25937423490, 743008289364, 23298080054964, 793714478374818, 29192909282466930, 1152920554828545360, 48661137306426044400, 2185908358103092063584, 104127157513055758393026, 5242868049702388548952080

Offset: 0

Benjamin Otto, Apr 11 2019

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

Column k=8 of A325201; see that entry for sequences related to other preimage constraints constructions.

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=8; 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)

a(n) = (n-1)! * [x^(n-1)] e_8(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The link above yields explicit constants c_k, r_k so that the columns are asymptotically c_8 * n^(-3/2) * r_8^-n.

A325208 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 9 neighbors that are further away from the root than the node itself.

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424590, 743008369224, 23298084997044, 793714764270428, 29192925433321650, 1152921466989795360, 48661189511753527280, 2185911410555033096364, 104127340753401006230046, 5242879377215160617336400

Offset: 0

Benjamin Otto, Jul 05 2019

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

Column k=9 of A325201; see that entry for sequences related to other preimage constraints constructions.

e[k_][x_] := Sum[x^j/j!, {j, 0, k}];
a[0] = 0; a[n_] := (n - 1)! Coefficient[e[9][x]^n, x, n - 1];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 06 2019 *)

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=9; 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)

a(n) = (n-1)! * [x^(n-1)] e_9(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The link above yields explicit constants c_k, r_k so that the columns are asymptotically c_9 * n^(-3/2) * r_9^-n.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

Python

Formula

Extensions

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

Python

Formula

Extensions

A325205 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 6 neighbors that are further away from the root than the node itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A325206 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 7 neighbors that are further away from the root than the node itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A325207 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 8 neighbors that are further away from the root than the node itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A325208 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 9 neighbors that are further away from the root than the node itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula