

A036777


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


4



0, 1, 2, 9, 64, 625, 7776, 117642, 2096752, 43030008, 999357660, 25912953990, 742054808880, 23259517076796, 792084372215136, 29120668067951460, 1149560690861943360, 48497162427675081120, 2177517061087611122880, 103677374170183264555104, 5217647895920644618674240, 276740347650892414464815640, 15429120173129978156923361280, 902095425530332280621924069520
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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 j1 \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^(n1) in ( Sum_{i \in R} x^i/i! )^n."
When R = {0,1,...,r}, the quantity S_n*(R)/n^(n1) 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^(n1) 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)


LINKS

Table of n, a(n) for n=0..23.
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), 110, esp. Eq. (14) with r = 5.
Index entries for sequences related to rooted trees


FORMULA

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


EXAMPLE

Here a(n)/n^(n1) 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^(n1) for n = 1..6 for obvious reasons! But a(7) = 117642 < 117649 = 7^6.  Petros Hadjicostas, Jun 09 2019


MAPLE

# 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


MATHEMATICA

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


CROSSREFS

Cf. A036774 (r = 2), A036775 (r = 3), A036776 (r = 4).
Sequence in context: A052514 A274395 A036776 * A325205 A325206 A325207
Adjacent sequences: A036774 A036775 A036776 * A036778 A036779 A036780


KEYWORD

nonn


AUTHOR

N. J. A. Sloane


EXTENSIONS

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


STATUS

approved



