A036775 -id:A036775 - cp's OEIS frontend

A036774 Number of labeled rooted unordered binary trees (each node has out-degree <= 2).

0, 1, 2, 9, 60, 540, 6120, 83790, 1345680, 24811920, 516650400, 11992503600, 307069963200, 8598348158400, 261387760233600, 8573572885878000, 301809119163552000, 11349727401396384000, 454104511068656448000, 19261139319649202976000

Offset: 0

N. J. A. Sloane

nonn

Fung Lam, Table of n, a(n) for n = 0..394
B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 2.
Index entries for sequences related to rooted trees

A071356(n) = a(n + 1) * 2^n/(n + 1)!.

Cf. A036775 (outdegree <= r = 3), A036776 (out-degree <= r = 4), A036777 (out-degree <= r = 5).

# This is a crude Maple program based on Eq. (14), p. 4, in Takacs (1993). It calculates a(n) for n >= 2. Here, r = 2 is the maximum out-degree of each node.
ff := proc(r, n) simplify(subs(x = 0, diff(sum(x^k/k!, k = 0 .. r)^n, x$(n - 1)))); end;
seq(ff(2, i), i = 2 .. 40); # Petros Hadjicostas, Jun 09 2019

Range[0, 20]! CoefficientList[Series[(1 - x - ((x - 1)^2 - 2 x^2)^(1/2))/x, {x, 0, 20}], x] (* Geoffrey Critzer, Nov 22 2011 *)
f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n - 1][f[2, n]][0]];
a /@ Range[0, 19] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas *)
a[n_] := n! Hypergeometric2F1[1/2 - n/2, 1 - n/2, 2, 2]; a[0] = 0;
Array[a, 20, 0] (* Peter Luschny, Apr 20 2020 *)

makelist(n!*sum(binomial(n-1,2*k)*binomial(2*k,k)/(2^k*(k+1)),k,0,floor((n-1)/2)),n,0,20); /* Emanuele Munarini, Feb 06 2013 */

a(n)=if(n<1,0,n!*polcoeff(2*x/(1-x+sqrt(1-2*x-x^2+O(x^n))),n))

a(n)=if(n<1,0,n!*polcoeff(serreverse(2*x/(2+2*x+x^2)+x*O(x^n)),n))

E.g.f.: (1 - x - sqrt(1-2*x-x^2))/x.
E.g.f. A(x) satisfies x*A(x)^2 + 2*(x-1)*A(x) + 2*x = 0, A(0)=0 and A(x) = x/(1-x-(x/2)*A(x)). - Michael Somos, Sep 06 2003
a(n) = n!*Sum_{k=0..floor((n-1)/2)} binomial(n-1, 2k)*binomial(2k, k)/(2^k*(k+1)). - Emanuele Munarini, Feb 06 2013
a(n) ~ sqrt(2-sqrt(2))*n^(n-1)/(exp(n)*(sqrt(2)-1)^(n+1)). - Vaclav Kotesovec, Sep 24 2013
Recurrence: (n+1)*a(n) = n*(n-1)*(n-2)*a(n-2) + n*(2*n-1)*a(n-1), n >= 3, a(1)=1, a(2)=2. - Fung Lam, Feb 24 2014
a(n) = n!*hypergeom([(1 - n)/2, 1 - n/2], [2], 2) for n >= 1. Peter Luschny, Apr 20 2020

Better description and formula from Christian G. Bower, Nov 29 2001

"unordered" added to the name by David Callan, Apr 22 2012

A325201 Square array whose entry A(n,k) is the number of labeled rooted trees on a set of size n where each node has at most k neighbors that are further away from the root than the node itself, for n >= 0, k >= 0, read by descending antidiagonals.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 6, 0, 0, 1, 2, 9, 24, 0, 0, 1, 2, 9, 60, 120, 0, 0, 1, 2, 9, 64, 540, 720, 0, 0, 1, 2, 9, 64, 620, 6120, 5040, 0, 0, 1, 2, 9, 64, 625, 7620, 83790, 40320, 0, 0, 1, 2, 9, 64, 625, 7770, 113610, 1345680, 362880, 0, 0, 1, 2, 9, 64, 625, 7776, 117390, 1992480, 24811920, 3628800, 0

Offset: 1

Benjamin Otto, Apr 08 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,k) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most k entries.

			Array begins:
           0           0           0           0           0 ...
           0           1           1           1           1 ...
           0           2           2           2           2 ...
           0           6           9           9           9 ...
           0          24          60          64          64 ...
           0         120         540         620         625 ...
           0         720        6120        7620        7770 ...
           0        5040       83790      113610      117390 ...
           0       40320     1345680     1992480     2088520 ...
           0      362880    24811920    40194000    42771960 ...
           0     3628800   516650400   916927200   991090800 ...
           0    39916800 11992503600 23341071600 25635767850 ...
         ...

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

Column 0: A000004.
Column 1 is A000142, except at n=0 term.
Columns 2-9: A036774, A036775, A036776, A036777, A325205, A325206, A325207, A325208.
A(n,n) gives A152917.
Similar array for arbitrary endofunctions (without limitation on the number of cyclic points) with the same preimage condition {i>=0 | i<=k}: A306800.

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

# print first num_entries entries in column k
import math, sympy; x=sympy.symbols('x')
k=5; 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,k) = (n-1)! * [x^(n-1)] e_k(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. When k>1, the link above yields explicit constants c_k, r_k so that the columns are asymptotically c_k * n^(-3/2) * r_k^-n. Stirling's approximation gives column k=1, and column k=0 is 0.

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

A036777 Number of labeled rooted trees with a degree constraint (described in the comments below).

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7776, 117642, 2096752, 43030008, 999357660, 25912953990, 742054808880, 23259517076796, 792084372215136, 29120668067951460, 1149560690861943360, 48497162427675081120, 2177517061087611122880, 103677374170183264555104, 5217647895920644618674240, 276740347650892414464815640, 15429120173129978156923361280, 902095425530332280621924069520

Offset: 0

N. J. A. Sloane

nonn

From Petros Hadjicostas, Jun 09 2019: (Start)
Quoting from p. 3 of Takacs (1993): "Denote by S_n* the set of all rooted trees with n labeled vertices. ... let us define R as a fixed set of nonnegative integers which always contains 0. Denote by S_n*(R) the subset of S_n* which contains all the trees in S_n* in which the degree of the root is in R and, if j is the degree of any other vertex of a tree, then j-1 \in R."
Quoting from p. 4 of Takacs (1993): "Theorem 2: The number of trees in S_n*(R) is |S_n^*(R)| = (n - 1)! Coeff. of x^(n-1) in ( Sum_{i \in R} x^i/i! )^n."
When R = {0,1,...,r}, the quantity |S_n*(R)|/n^(n-1) has a probabilistic interpretation related to the generalized birthday problem. Let us "put balls at random one by one in n boxes until one of the boxes contains r + 1 balls" (p. 4 in Takacs). We assume that every box has the same probability (i.e., 1/n). Then |S_n*(R)|/n^(n-1) is the probability that at least n balls are needed until the above process stops (i.e., until at least one of the n boxes contains r + 1 balls).
(End)

			Here a(n)/n^(n-1) is the probability that at least n balls are needed until one of the n boxes contains r + 1 = 6 balls (for the first time) when the n boxes are equally likely and we randomly distribute balls in the boxes (one by one) until one box gets r + 1 = 6 balls for the first time.  Clearly, a(n) = n^(n-1) for n = 1..6 for obvious reasons! But a(7) = 117642 < 117649 = 7^6. - _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 = 5.
Index entries for sequences related to rooted trees

Cf. A036774 (r = 2), A036775 (r = 3), A036776 (r = 4).

# This is a crude Maple program based on Eq. (14), p. 4, in Takacs (1993). It calculates a(n) for n >= 2.
ff := proc(r, n) simplify(subs(x = 0, diff(sum(x^k/k!, k = 0 .. r)^n, x$(n - 1)))); end;
seq(ff(5, i), i = 2 .. 40); # Petros Hadjicostas, Jun 09 2019

f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n-1][f[5, n]][0]];
a /@ Range[0, 23] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas *)

In Theorem 2 from p. 4 in Takacs (1993)--see the COMMENTS above--let R = {0,1,...,r} with r = 5. - Petros Hadjicostas, Jun 09 2019

More terms, name edited, and offset changed by Petros Hadjicostas, Jun 09 2019

cp's OEIS Frontend

A036774 Number of labeled rooted unordered binary trees (each node has out-degree <= 2).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A325201 Square array whose entry A(n,k) is the number of labeled rooted trees on a set of size n where each node has at most k neighbors that are further away from the root than the node itself, for n >= 0, k >= 0, read by descending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

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

A036777 Number of labeled rooted trees with a degree constraint (described in the comments below).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions