cp's OEIS Frontend

A121448 Triangle read by rows: T(n,k) is the number of binary trees with n edges and having k vertices of outdegree 1 (n>=0, k>=0). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.

%I A121448 #56 Jan 23 2025 13:54:51
%S A121448 1,0,2,1,0,4,0,6,0,8,2,0,24,0,16,0,20,0,80,0,32,5,0,120,0,240,0,64,0,
%T A121448 70,0,560,0,672,0,128,14,0,560,0,2240,0,1792,0,256,0,252,0,3360,0,
%U A121448 8064,0,4608,0,512,42,0,2520,0,16800,0,26880,0,11520,0,1024,0,924,0,18480,0
%N A121448 Triangle read by rows: T(n,k) is the number of binary trees with n edges and having k vertices of outdegree 1 (n>=0, k>=0). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.
%C A121448 T(2n,0) = binomial(2n,n)/(n+1) (the Catalan numbers; A000108); T(2n+1,0)=0. T(n,n)=2^n (A000079). Sum(k*T(n,k),k=0..n)=2*binomial(2n,n-1)=2*A001791(n). After deleting the zeros, reflection of A091894.
%C A121448 From _Tom Copeland_, Feb 07 2016: (Start)
%C A121448 A shifted o.g.f. is OG(x,t) = [1 - 2tx - sqrt[(1-2tx)^2-4x^2]] / (2x) = x + 2t x^2 + (1+4t^2) x^3 + ... with compositional inverse OGinv(x,t) =  x / (1 + 2tx + x^2), the shifted o.g.f. for A053117 (mod signs).
%C A121448 For x > 0 and choosing the positive square root, OG(x^2,t) = H(x,t) = x^2 + 2t x^4 + (1+4t^2) x^6 + ... has the compositional inverse Hinv(x,t) = sqrt[x / (1 + 2tx + x^2)] , which satisfies Hinv(H(x, t), t) = x, and which is the generating function for the Legendre polynomials (mod signs, cf. A008316) times sqrt(x).
%C A121448 In general, GB(x,t,b) =  [x / (1 - 2tx + x^2)]^b is a generator for the Gegenbauer polynomials times x^b for positive roots with compositional inverse about the origin GBinv(x,t,b) = OG(x^(1/b),-t) for x>0. Cf. A097610.
%C A121448 (End)
%C A121448 From _Tom Copeland_, Feb 09 2016: (Start)
%C A121448 z1 = OG(x,t) is the zero that vanishes for x=0 for the quadratic polynomial Q(z;z1(x,t),z2(x,t)) =(z-z1)(z-z2) = z^2 - (z1+z2) z + (z1*z2) = z^2 - e1 z + e2 = z^2 - [(1-2tx)/x] z + 1, where e1 and e2 are the elementary symmetric polynomials for two indeterminates.
%C A121448 The other zero is given by z2(x,t) = [1 - 2tx + sqrt[(1-2tx)^2-4x^2]] / (2x) = (1 - 2tx)/x - z1(x,t).
%C A121448 The two are zeros of the elliptic curve in Legendre normal form y^2 = z (z-z1)(z-z2). (Added Feb 13 2016. See Landweber et al., p 14. Cf. A097610.)
%C A121448 (End)
%H A121448 Colin Defant, <a href="http://arxiv.org/abs/1604.01723">Postorder Preimages</a>, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
%H A121448 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000385/">The number of vertices with out-degree 1 in a binary tree</a>.
%H A121448 P. Landweber, D. Ravenel, and R. Stong, <a href="https://www.math.rochester.edu/people/faculty/doug/mypapers/lrs.pdf">Periodic cohomology theories defined by elliptic curves</a>
%F A121448 T(n,k) = 2^k*binomial(n+1,k)binomial(n+1-k,(n-k)/2)/(n+1) if n-k is even; otherwise, T(n,k) = 0. G.f. G=G(t,z) satisfies G=1+2tzG+z^2*G^2.
%F A121448 T(n,k) = 2^k*A097610(n,k). - _Philippe Deléham_, Aug 17 2006
%F A121448 From _Tom Copeland_, Feb 09 2016: (Start)
%F A121448 The following is from the formalism in A097610 with h1 = 2t, h2 = 1, and MT(n,h1,h2) = MT(n,2t,1) and with OG(x,t) defined above.
%F A121448 E.g.f.: M(x,t) = e^(2tx) AC(x) = exp[x MT(.,2t,1)] = exp[x P(.,t)], where AC(x) = I_1(2x)/x = Sum_{n>=0} x^(2n)/(n!(n+1)!) = exp(c.x) is the e.g.f. of A126120.
%F A121448 P(n,t) = MT(n,2t,1) = (c. + 2t)^n = Sum_{k=0..n} binomial(n,k) c(n-k) (2t)^k with c(k) = A126120(k). P(n,t+s) = (c. + 2t + 2s)^n = (P(.,t) + 2s)^n.
%F A121448 P(n,t) = t^n FC(n,c./t) = t^n (2 + c./t)^n, where FC(n,t) = (2 + t)^n are the face polynomials (vectors) of the hypercubes of A038207, i.e., the row polynomials of this entry can be obtained as the umbral composition of the reverse face polynomials with the aerated Catalan numbers of A000108.
%F A121448 The lowering and raising operators for the row polynomials P(n,t) of this entry are L = (1/2) d/dt = (1/2) D and R = 2t + dlog{AC(L)}/dL = 2t + Sum_{n>=0} b(n) L^(2n+1)/(2n+1)! = 2t + L - L^3/3! + 5 L^5/5! - ...  with b(n) = (-1)^n A180874(n+1).
%F A121448 Let CP(n,t) = P(n+1,t) with CP(0,t) = 0. Then the infinitesimal generator for CP(n,t) is g(x) d/dx with g(x) = 1 /[dOGinv(x,t)/dx] = x^2 / [(OGinv(x,t))^2 (1 - x^2)] = (1 + 2t x + x^2)^2 / (1 - x^2) so that [g(x)d/dx]^n/n! x evaluated at x = 0 gives the row polynomial CP(n,t), i.e., exp[x g(u)d/du] u |_(u=0) = OG(x,t) = 1 /[1 - x P(.,t)]. Cf. A145271.
%F A121448 g(x) = 1 + 4t x + (3+4t) x^2 + 8t x^3 + 4(1+t^2) x^4 + 8t x^5 + 4(1+t^2) x^6 + 8t x^7 + ... has the repeating coefficients of the vector V = (1, 4t, 3+4t, 8t, 4(1+t^2), 8t, 4(1+t^2), 8t, ...). Form the lower triangular matrix U with all ones on the diagonal and below. Multiply the n-th diagonal of U by V(n), giving the matrix VU with VU(n,k) = V(n-k). Then (1,0,0,0,..) [VU * DM]^n/n! (0,1,0,0,..)^T = CP(n,t) = P(n-1,t) for n>0 with DM being the matrix A218272 representing differentiation of a power series.
%F A121448 (End)
%e A121448 T(2,2)=4 because, denoting by L (R) an edge going from a vertex to a left (right) child, we have the paths: LL, LR, RL and RR.
%e A121448 Triangle starts:
%e A121448   1;
%e A121448   0,2;
%e A121448   1,0,4;
%e A121448   0,6,0,8;
%e A121448   2,0,24,0,16;
%p A121448 T:=proc(n,k) if n-k mod 2 = 0 then 2^k*binomial(n+1,k)*binomial(n+1-k,(n-k)/2)/(n+1) else 0 fi end: for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form
%t A121448 nn=10;Drop[CoefficientList[Series[(1-2x y - ((-4x^2+(1-2x y)^2))^(1/2))/(2 x),{x,0,nn}],{x,y}],1]//Grid  (* _Geoffrey Critzer_, Feb 20 2013 *)
%Y A121448 Cf. A000108, A000079, A001791, A091894.
%Y A121448 Cf. A038207, A053117, A097610, A126120, A145271, A180874, A218272.
%Y A121448 Cf. A008316.
%K A121448 nonn,tabl
%O A121448 0,3
%A A121448 _Emeric Deutsch_, Jul 31 2006