cp's OEIS Frontend

A036776 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 4 neighbors that are further away from the root than the node itself.

%I A036776 #53 Nov 29 2023 17:18:33
%S A036776 0,1,2,9,64,625,7770,117390,2088520,42771960,991090800,25635767850,
%T A036776 732235165200,22890759391500,777398836414200,28501053507927000,
%U A036776 1121908690738836000,47194400446765572000,2112854517933207048000,100302903229033765260000,5032863920347902999360000
%N A036776 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 4 neighbors that are further away from the root than the node itself.
%C A036776 a(n) is the number of unordered rooted labeled trees such that each node has outdegree <= 4. - _Geoffrey Critzer_, Mar 23 2013
%C A036776 From pp. 3-4 in Takacs (1993), we see that n is the number of nodes in a labeled rooted tree such that each node has outdegree <= 3, and (as noted above by G. Critzer), a(n) is the number of such unordered rooted labeled trees (with n nodes). Apparently, the author of this sequence and other contributors exclude the node at the root, and thus the offset here is 0 (rather than 1). - _Petros Hadjicostas_, Jun 09 2019
%H A036776 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 A036776 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 = 4.
%H A036776 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A036776 From _Vladimir Kruchinin_, Nov 22 2011: (Start)
%F A036776 E.g.f. A(x) satisfies: A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3 + (1/24)*A(x)^4.
%F A036776 a(n) = n!*Sum_{r=0..n+1} binomial(n+1,r)*Sum_{m=0..r} binomial(r,m)*Sum_{j=0..m} binomial(j,-r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m,j)*3^(-j). (End)
%F A036776 a(n) = (n-1)! * [x^(n-1)] e_4(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The Otto link above yields explicit constants c_k, r_k so that the columns are asymptotically c_4 * n^(-3/2) * r_4^-n. - _Benjamin Otto_, Apr 11 2019
%t A036776 nn=18;f[x_]:=Sum[a[n]x^n/n!,{n,0,nn}];s=SolveAlways[0==Series[f[x]-x(1+f[x]+f[x]^2/2+f[x]^3/3!+f[x]^4/4!),{x,0,nn}],x];Table[a[n],{n,0,nn}]/.s  (* _Geoffrey Critzer_, Mar 23 2013 *)
%t A036776 f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
%t A036776 a[n_] := If[n == 1, 1, Derivative[n-1][f[4, n]][0]];
%t A036776 a /@ Range[0, 20] (* _Jean-François Alcover_, Apr 20 2020, after _Petros Hadjicostas_ in A036777 *)
%o A036776 (Maxima)
%o A036776 a(n):=(n!*sum(binomial(n+1,r)*sum(binomial(r,m)*sum(binomial(j,-r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m,j)*(3)^(-j),j,0,m),m,0,r),r,0,n+1)); /* _Vladimir Kruchinin_, Nov 22 2011 */
%o A036776 (Python)
%o A036776 # print first num_entries entries in the sequence
%o A036776 import math, sympy; x=sympy.symbols('x')
%o A036776 k=4; num_entries = 64
%o A036776 P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0,1]; curr_pow = eP
%o A036776 for term in range(1,num_entries-1):
%o A036776    curr_pow=(curr_pow*eP).expand()
%o A036776    r.append(curr_pow.coeff(x**term)*math.factorial(term))
%o A036776 print(r) # _Benjamin Otto_, Apr 11 2019
%Y A036776 Cf. A036774, A036775, A036777. Column k=4 of A325201; see that entry for sequences related to other preimage constraints constructions.
%K A036776 nonn
%O A036776 0,3
%A A036776 _N. J. A. Sloane_
%E A036776 Edited by _N. J. A. Sloane_, Jul 13 2019 using data from a duplicate of this entry that was submitted by _Benjamin Otto_, Apr 08 2019