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!)
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 non-negative 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

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 January 24 01:20 EST 2021. Contains 340398 sequences. (Running on oeis4.)