A036777 - OEIS

%I #45 Apr 25 2022 08:03:15

%S 0,1,2,9,64,625,7776,117642,2096752,43030008,999357660,25912953990,

%T 742054808880,23259517076796,792084372215136,29120668067951460,

%U 1149560690861943360,48497162427675081120,2177517061087611122880,103677374170183264555104,5217647895920644618674240,276740347650892414464815640,15429120173129978156923361280,902095425530332280621924069520

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

%C From _Petros Hadjicostas_, Jun 09 2019: (Start)

%C 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."

%C 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."

%C 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).

%C (End)

%H B. Otto, <a href="https://arxiv.org/abs/1903.00542">Coalescence under Preimage Constraints</a>, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.

%H L. Takacs, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/18_1_1.pdf">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 5.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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

%e 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

%p # This is a crude Maple program based on Eq. (14), p. 4, in Takacs (1993). It calculates a(n) for n >= 2.

%p ff := proc(r, n) simplify(subs(x = 0, diff(sum(x^k/k!, k = 0 .. r)^n, x$(n - 1)))); end;

%p seq(ff(5, i), i = 2 .. 40); # _Petros Hadjicostas_, Jun 09 2019

%t f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;

%t a[n_] := If[n == 1, 1, Derivative[n-1][f[5, n]][0]];

%t a /@ Range[0, 23] (* _Jean-François Alcover_, Apr 20 2020, after _Petros Hadjicostas_ *)

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

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E More terms, name edited, and offset changed by _Petros Hadjicostas_, Jun 09 2019