

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.


3



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, 70, 0, 560, 0, 672, 0, 128, 14, 0, 560, 0, 2240, 0, 1792, 0, 256, 0, 252, 0, 3360, 0, 8064, 0, 4608, 0, 512, 42, 0, 2520, 0, 16800, 0, 26880, 0, 11520, 0, 1024, 0, 924, 0, 18480, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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,n1)=2*A001791(n). After deleting the zeros, reflection of A091894.
From Tom Copeland, Feb 07 2016: (Start)
A shifted o.g.f. is OG(x,t) = [1  2tx  sqrt[(12tx)^24x^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).
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).
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.
(End)
From Tom Copeland, Feb 09 2016: (Start)
z1 = OG(x,t) is the zero that vanishes for x=0 for the quadratic polynomial Q(z;z1(x,t),z2(x,t)) =(zz1)(zz2) = z^2  (z1+z2) z + (z1*z2) = z^2  e1 z + e2 = z^2  [(12tx)/x] z + 1, where e1 and e2 are the elementary symmetric polynomials for two indeterminates.
The other zero is given by z2(x,t) = [1  2tx + sqrt[(12tx)^24x^2]] / (2x) = (1  2tx)/x  z1(x,t).
The two are zeros of the elliptic curve in Legendre normal form y^2 = z (zz1)(zz2). (Added Feb 13 2016. See Landweber et al., p 14. Cf. A097610.)
(End)


LINKS

Table of n, a(n) for n=0..70.
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
FindStat  Combinatorial Statistic Finder, The number of vertices with outdegree 1 in a binary tree.
P. Landweber, D. Ravenel, R. Stong, Periodic cohomology theories defined by elliptic curves


FORMULA

T(n,k) = 2^k*binomial(n+1,k)binomial(n+1k,(nk)/2)/(n+1) if nk is even; otherwise, T(n,k) = 0. G.f. G=G(t,z) satisfies G=1+2tzG+z^2*G^2.
T(n,k) = 2^k*A097610(n,k).  Philippe Deléham, Aug 17 2006
From Tom Copeland, Feb 09 2016: (Start)
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.
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.
P(n,t) = MT(n,2t,1) = (c. + 2t)^n = Sum_{k=0..n} binomial(n,k) c(nk) (2t)^k with c(k) = A126120(k). P(n,t+s) = (c. + 2t + 2s)^n = (P(.,t) + 2s)^n.
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.
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).
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.
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 nth diagonal of U by V(n), giving the matrix VU with VU(n,k) = V(nk). Then (1,0,0,0,..) [VU * DM]^n/n! (0,1,0,0,..)^T = CP(n,t) = P(n1,t) for n>0 with DM being the matrix A218272 representing differentiation of a power series.
(End)


EXAMPLE

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.
Triangle starts:
1;
0,2;
1,0,4;
0,6,0,8;
2,0,24,0,16;


MAPLE

T:=proc(n, k) if nk mod 2 = 0 then 2^k*binomial(n+1, k)*binomial(n+1k, (nk)/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


MATHEMATICA

nn=10; Drop[CoefficientList[Series[(12x y  ((4x^2+(12x y)^2))^(1/2))/(2 x), {x, 0, nn}], {x, y}], 1]//Grid (* Geoffrey Critzer, Feb 20 2013 *)


CROSSREFS

Cf. A000108, A000079, A001791, A091894.
Cf. A038207, A053117, A097610, A126120, A145271, A180874, A218272.
Cf. A008316.
Sequence in context: A137336 A115322 A053117 * A019094 A134082 A185740
Adjacent sequences: A121445 A121446 A121447 * A121449 A121450 A121451


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jul 31 2006


STATUS

approved



