OFFSET
1,1
COMMENTS
FORMULA
T(n, k)=2T(n-1, k-1) + sum(T(n-1, j)T(n-1, k-2-j), j=1..k-3) (n, k>=2); T(1, 1)=2, T(1, 2)=1, T(1, k)=0 for k>=3, T(n, 1)=0 for n>=2. Generating polynomial P[n](t) of row n is given by rec. eq. P[n]=2tP[n-1]+(t*P[n-1])^2, P[0]=1.
EXAMPLE
T(3,3)=8 because we have eight paths of length 3 (each edge can have two orientations).
Triangle begins:
2,1;
0,4,2,4,4,1;
0,0,8,4,8,24,18,36,48,40,36,24,8,1;
MAPLE
P[0]:=1: for n from 1 to 5 do P[n]:=sort(expand(2*t*P[n-1]+t^2*P[n-1]^2)) od: for n from 1 to 5 do seq(coeff(P[n], t^k), k=1..2^(n+1)-2) od; # yields sequence in triangular form
MATHEMATICA
T[n_, k_] := T[n, k] = Which[
n == 1 && k == 1, 2,
n == 1 && k == 2, 1,
n == 1 || k == 1, 0,
True, 2*T[n-1, k-1] + Sum[T[n-1, j]*T[n-1, k-2-j], {j, 1, k-3}]];
Table[T[n, k], {n, 1, 5}, {k, 1, 2^(n+1)-2}] // Flatten (* Jean-François Alcover, Sep 21 2024, after Maple program for A106376 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 05 2005
STATUS
approved