login
Triangle read by rows: T(n,k) is the coefficient of t^k (k >= 1) in the polynomial P[n,t] defined by P[1,t] = P[2,t] = t, P[n,t] = P[n-1,t] + P^2[n-2,t].
1

%I #10 Nov 27 2019 01:30:16

%S 1,1,1,1,1,2,1,3,2,1,1,4,6,5,1,5,12,18,14,10,4,1,1,6,20,46,72,86,64,

%T 26,1,7,30,95,228,438,656,794,786,662,448,248,108,36,8,1,1,8,42,171,

%U 560,1534,3532,6950,11670,16630,19760,19252,14860,8604,3336,677

%N Triangle read by rows: T(n,k) is the coefficient of t^k (k >= 1) in the polynomial P[n,t] defined by P[1,t] = P[2,t] = t, P[n,t] = P[n-1,t] + P^2[n-2,t].

%C T(n,k) is the number of certain types of trees (see the Duke et al. reference) of height n and having k leaves. Row n contains 2^(ceiling(n/2)-1) terms. Row sums yield A000278.

%H W. Duke, Stephen J. Greenfield and Eugene R. Speer, <a href="https://cs.uwaterloo.ca/journals/JIS/green2/qf.html">Properties of a Quadratic Fibonacci Recurrence</a>, J. Integer Sequences, 1998, #98.1.8.

%F T(n, k) = T(n-1, k) + Sum_{j=1..k-1} T(n-2, j)*T(n-2, k-j);

%F T(1, 1) = T(2, 1) = 1;

%F T(1, k) = T(2, k) = 0 for k > 1.

%e P[3,t] = t^2 + t;

%e P[4,t] = 2t^2 + t;

%e P[5,t] = t^4 + 2t^3 + 3t^2 + t;

%e therefore T(5,1)=1, T(5,2)=3, T(5,3)=2, T(5,4)=1.

%e Triangle begins:

%e 1;

%e 1;

%e 1, 1;

%e 1, 2;

%e 1, 3, 2, 1;

%e 1, 4, 6, 5;

%e 1, 5, 12, 18, 14, 10, 4, 1;

%p P[1]:=t:P[2]:=t:for n from 3 to 10 do P[n]:=sort(expand(P[n-1]+P[n-2]^2)) od:for n from 1 to 10 do seq(coeff(P[n],t^k),k=1..2^(ceil(n/2)-1)) od;# yields sequence in triangular form

%Y Cf. A000278.

%K nonn,tabf

%O 1,6

%A _Emeric Deutsch_, Mar 21 2005