A138157 - OEIS

%I #16 Jan 31 2019 19:42:02

%S 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 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 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 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 Row n has 1+n(n+1)/2 terms.

%C Row sums are the Catalan numbers (A000108).

%C Column sums yield A095830.

%C Sum(k*T(n,k),k>=0)=A138156(n).

%C 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 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).

%H Alois P. Heinz, <a href="/A138157/b138157.txt">Rows n = 0..50, flattened</a>

%H 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 G.f.=G(t,z) satisfies G(t,z)=1 + 2tzG(t,tz) + [tzG(t,tz)]^2. The row generating polynomials P[n]=P[n](t) (n=1,2,...) are given by P[n]=t^n (2P[n-1] + sum(P[i]P[n-2-i], i=0..n-2); P[0]=1.

%e 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 Triangle starts:

%e 1;

%e 0,2;

%e 0,0,1,4;

%e 0,0,0,0,4,2,8;

%e 0,0,0,0,0,0,6,8,8,4,16;

%e 0,0,0,0,0,0,0,0,4,24,4,28,16,16,8,32;

%p 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 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 Cf. A000108, A095830, A138156.

%K nonn,tabf

%O 0,3

%A _Emeric Deutsch_, Mar 20 2008