cp's OEIS Frontend

A138157 Triangle read by rows: T(n,k) is the number of binary trees with n edges and path length k; 0<=k<=n*(n+1)/2.

%I A138157 #20 May 06 2025 21:52:00
%S A138157 1,0,2,0,0,1,4,0,0,0,0,4,2,8,0,0,0,0,0,0,6,8,8,4,16,0,0,0,0,0,0,0,0,4,
%T A138157 24,4,28,16,16,8,32,0,0,0,0,0,0,0,0,0,0,1,24,36,48,24,56,40,56,32,32,
%U A138157 16,64,0,0,0,0,0,0,0,0,0,0,0,0,0,8,60,72,144,26,168,104,128,64,176,80,112
%N A138157 Triangle read by rows: T(n,k) is the number of binary trees with n edges and path length k; 0<=k<=n*(n+1)/2.
%C A138157 Row n has 1+n*(n+1)/2 terms.
%C A138157 Row sums are the Catalan numbers (A000108).
%C A138157 Column sums yield A095830.
%C A138157 Sum_{k>=0} k*T(n,k) = A138156(n).
%C A138157 The g.f. B(w,z) in the Knuth reference is related to the above G(t,z) through B(t,z)=1+zG(t,z).
%D A138157 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).
%H A138157 Alois P. Heinz, <a href="/A138157/b138157.txt">Rows n = 0..50, flattened</a>
%H A138157 Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
%F A138157 G.f.: G(t,z) satisfies G(t,z) = 1 + 2*t*z*G(t,t*z) + (t*z*G(t,t*z))^2. The row generating polynomials P[n] = P[n](t) (n=1,2,...) are given by P[n] = t^n*(2*P[n-1] + Sum_{i=0..n-2} P[i]*P[n-2-i]); P[0] = 1.
%e A138157 T(2,3) = 4 because we have the path trees LL, LR, RL and RR, where L (R) denotes a left (right) edge; each of these four trees has path length 3.
%e A138157 Triangle starts:
%e A138157   1;
%e A138157   0,2;
%e A138157   0,0,1,4;
%e A138157   0,0,0,0,4,2,8;
%e A138157   0,0,0,0,0,0,6,8,8,4,16;
%e A138157   0,0,0,0,0,0,0,0,4,24,4,28,16,16,8,32;
%p A138157 P[0]:=1: for n to 7 do P[n]:=sort(expand(t^n*(2*P[n-1]+add(P[i]*P[n-2-i],i= 0..n-2)))) end do: for n from 0 to 7 do seq(coeff(P[n],t,j),j=0..(1/2)*n*(n+1)) end do; # yields sequence in triangular form
%t A138157 p[n_] := p[n] = t^n*(2p[n-1] + Sum[p[i]*p[n-2-i], {i, 0, n-2}]); p[0] = 1; Flatten[ Table[ CoefficientList[ p[n], t], {n, 0, 7}]] (* _Jean-François Alcover_, Jul 22 2011, after Maple prog. *)
%Y A138157 Cf. A000108, A095830, A138156.
%K A138157 nonn,tabf
%O A138157 0,3
%A A138157 _Emeric Deutsch_, Mar 20 2008