login
Number of at most 4-way branching ordered (i.e., plane) trees.
1

%I #33 Oct 27 2023 20:52:55

%S 1,2,6,20,70,246,875,3144,11385,41470,151778,557712,2056210,7602700,

%T 28180050,104677280,389571983,1452293766,5422187130,20271296100,

%U 75878518695,284339792110,1066585128810,4004566131000,15048213795600

%N Number of at most 4-way branching ordered (i.e., plane) trees.

%C Obtained by Lagrange inversion of the generating function for at most k-way branching trees.

%C Solve z = T/(1+T+...T^k) when k = 4. I.e., the n-th term is the coefficient of x^(n-1) in the expansion of (1+x+x^2+x^3+x^4)^n.

%H Alois P. Heinz, <a href="/A135413/b135413.txt">Table of n, a(n) for n = 1..1000</a> (first 250 terms from G. C. Greubel)

%F a(n) = [ x^(n-1) ] (1+x+x^2+x^3+x^4)^n.

%F a(n) = Sum_{i=0..floor((n-1)/5)} (-1)^i * C(n,i) * C(2*n-5*i-2,n-5*i-1). - _Vladimir Kruchinin_, Mar 28 2019

%p A135413 := proc(n) local ogf,i ; ogf := 1 ; for i from 1 to n do ogf := taylor(ogf*(1+x+x^2+x^3+x^4),x=0,n) ; od: coeftayl(ogf,x=0,n-1) ; end: seq(A135413(n),n=1..30) ; # _R. J. Mathar_, Apr 21 2008

%t Join[{1}, Table[Coefficient[(1 + x + x^2 + x^3 + x^4)^n, x,(n - 1)], {n,2,25}]] (* _G. C. Greubel_, Oct 13 2016 *)

%o (Maxima)

%o a(n):=sum((-1)^i*binomial(n,i)*binomial(2*n-5*i-2,n-5*i-1),i,0,(n-1)/5); /* _Vladimir Kruchinin_, Mar 28 2019 */

%o (PARI) a(n) = polcoef((1+x+x^2+x^3+x^4)^n, n-1, x); \\ _Michel Marcus_, Mar 28 2019

%Y For k=2 this is A005717, for k=3 this is A005726.

%K nonn,easy

%O 1,2

%A Andrey Bovykin (indiscernibles(AT)googlemail.com), Mar 01 2008

%E More terms from _R. J. Mathar_, Apr 21 2008