cp's OEIS Frontend

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

%I A036777 #45 Apr 25 2022 08:03:15
%S A036777 0,1,2,9,64,625,7776,117642,2096752,43030008,999357660,25912953990,
%T A036777 742054808880,23259517076796,792084372215136,29120668067951460,
%U A036777 1149560690861943360,48497162427675081120,2177517061087611122880,103677374170183264555104,5217647895920644618674240,276740347650892414464815640,15429120173129978156923361280,902095425530332280621924069520
%N A036777 Number of labeled rooted trees with a degree constraint (described in the comments below).
%C A036777 From _Petros Hadjicostas_, Jun 09 2019: (Start)
%C A036777 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 A036777 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 A036777 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 A036777 (End)
%H A036777 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 A036777 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 A036777 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A036777 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 A036777 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 A036777 # This is a crude Maple program based on Eq. (14), p. 4, in Takacs (1993). It calculates a(n) for n >= 2.
%p A036777 ff := proc(r, n) simplify(subs(x = 0, diff(sum(x^k/k!, k = 0 .. r)^n, x$(n - 1)))); end;
%p A036777 seq(ff(5, i), i = 2 .. 40); # _Petros Hadjicostas_, Jun 09 2019
%t A036777 f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
%t A036777 a[n_] := If[n == 1, 1, Derivative[n-1][f[5, n]][0]];
%t A036777 a /@ Range[0, 23] (* _Jean-François Alcover_, Apr 20 2020, after _Petros Hadjicostas_ *)
%Y A036777 Cf. A036774 (r = 2), A036775 (r = 3), A036776 (r = 4).
%K A036777 nonn
%O A036777 0,3
%A A036777 _N. J. A. Sloane_
%E A036777 More terms, name edited, and offset changed by _Petros Hadjicostas_, Jun 09 2019