login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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,n-1)=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[(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).
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)) =(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.
The other zero is given by z2(x,t) = [1 - 2tx + sqrt[(1-2tx)^2-4x^2]] / (2x) = (1 - 2tx)/x - z1(x,t).
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.)
(End)
LINKS
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
FindStat - Combinatorial Statistic Finder, The number of vertices with out-degree 1 in a binary tree.
FORMULA
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.
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(n-k) (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 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.
(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 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
MATHEMATICA
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 *)
CROSSREFS
Cf. A008316.
Sequence in context: A137336 A115322 A053117 * A019094 A134082 A185740
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 31 2006
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:09 EDT 2024. Contains 370951 sequences. (Running on oeis4.)