cp's OEIS Frontend

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

%I A036775 #56 Nov 29 2023 17:18:50
%S A036775 0,1,2,9,64,620,7620,113610,1992480,40194000,916927200,23341071600,
%T A036775 655922836800,20169411662400,673645440468000,24285190867938000,
%U A036775 939899116892736000,38870133445791648000,1710655202853140544000,79826043011286892320000,3936948118406837614080000,204621522793150838094720000
%N A036775 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 3 neighbors that are further away from the root than the node itself.
%C A036775 a(n) is the number of unordered rooted labeled trees such that each node has outdegree <= 3. - _Geoffrey Critzer_, Mar 22 2013
%C A036775 A preimage constraint on a function is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set. View a labeled rooted tree as an endofunction on the set {1,2,...,n} by sending every non-root node to its neighbor that is closer to the root and sending the root to itself. Thus a(n) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most 3 entries. - _Benjamin Otto_, Apr 08 2019
%C A036775 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). - _Petros Hadjicostas_, Jun 09 2019
%H A036775 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 A036775 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 = 3.
%H A036775 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A036775 E.g.f.: (for shifted sequence a(0)=0, a(1)=1, ...) A(x) satisfies A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3.
%F A036775 a(n) = 3*n!*Sum_{j=0..n+1} binomial(n+1, j)*Sum_{i=j..n+j} binomial(j, i-j)*2^(4*j-2*n-i-2)*6^(n+i+1)*binomial(n-j+1, 3*j-n-i-2)/6^(3*j). - _Vladimir Kruchinin_, Nov 21 2011
%F A036775 a(n) ~ sqrt(s/(1+r*s)) * n^n / (r^(n+1) * exp(n)), where r = 0.37589405207806352... is the root of the equation -8 + 21*r + 2*r^3 = 0 and s = 2.86947048655283754... is the root of the equation -12 + 36*s - 57*s^2 + 16*s^3 = 0. - _Vaclav Kotesovec_, Jan 08 2014
%F A036775 a(n) = (n-1)! * [x^(n-1)] e_3(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_3 * n^(-3/2) * r_3^-n. - _Benjamin Otto_, Apr 08 2019
%t A036775 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!),{x,0,nn}],x];Table[a[n],{n,0,nn}]/.s (* _Geoffrey Critzer_, Mar 22 2013 *)
%t A036775 Table[3*n!*Sum[Binomial[n+1,j]*Sum[Binomial[j,i-j]*2^(4*j-2*n-i-2)*6^(n+i+1)*Binomial[n-j+1,3*j-n-i-2],{i,j,n+j}]/6^(3*j),{j,0,n+1}],{n,0,20}] (* _Vaclav Kotesovec_ after _Vladimir Kruchinin_, Jan 08 2014 *)
%t A036775 f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
%t A036775 a[n_] := If[n == 1, 1, Derivative[n - 1][f[3, n]][0]];
%t A036775 a /@ Range[0, 21] (* _Jean-François Alcover_, Apr 20 2020, after _Petros Hadjicostas_ in A036777 *)
%o A036775 (Maxima) a(n):=3*n!*sum((binomial(n+1,j)*sum(binomial(j,i-j)*2^(4*j-2*n-i-2)*6^(n+i+1)*binomial(n-j+1,3*j-n-i-2),i,j,n+j))/6^(3*j),j,0,(n+1)); /* _Vladimir Kruchinin_, Nov 21 2011 */
%o A036775 (Python)
%o A036775 # print first num_entries entries in the sequence
%o A036775 import math, sympy; x=sympy.symbols('x')
%o A036775 k=3; num_entries = 64
%o A036775 P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0,1]; curr_pow = eP
%o A036775 for term in range(1,num_entries-1):
%o A036775    curr_pow=(curr_pow*eP).expand()
%o A036775    r.append(curr_pow.coeff(x**term)*math.factorial(term))
%o A036775 print(r) # _Benjamin Otto_, Apr 08 2019
%Y A036775 Cf. A036774, A036776, A036777.
%Y A036775 Column k=3 of A325201; see that entry for sequences related to other preimage constraints constructions. - _Benjamin Otto_, Apr 08 2019
%K A036775 nonn
%O A036775 0,3
%A A036775 _N. J. A. Sloane_
%E A036775 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