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

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

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), 1-10, 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 above--let R = {0,1,...,r} with r = 5. - Petros Hadjicostas, Jun 09 2019

Example

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

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[n-1][f[5, n]][0]];
a /@ Range[0, 23] (* Jean-Franç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