A103484 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, 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, 26, 1, 7, 30, 95, 228, 438, 656, 794, 786, 662, 448, 248, 108, 36, 8, 1, 1, 8, 42, 171, 560, 1534, 3532, 6950, 11670, 16630, 19760, 19252, 14860, 8604, 3336, 677

Offset

1,6

Comments

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.

Links

Table of n, a(n) for n=1..62.

W. Duke, Stephen J. Greenfield and Eugene R. Speer, Properties of a Quadratic Fibonacci Recurrence, J. Integer Sequences, 1998, #98.1.8.

Formula

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

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

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

Example

P[3,t] = t^2 + t;
P[4,t] = 2t^2 + t;
P[5,t] = t^4 + 2t^3 + 3t^2 + t;
therefore T(5,1)=1, T(5,2)=3, T(5,3)=2, T(5,4)=1.
Triangle begins:
  1;
  1;
  1,  1;
  1,  2;
  1,  3,  2,  1;
  1,  4,  6,  5;
  1,  5, 12, 18, 14, 10,  4,  1;

Maple

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

Crossrefs

Cf. A000278.

Sequence in context: A300441 A375378 A295665 * A016444 A280831 A166948

Adjacent sequences: A103481 A103482 A103483 * A103485 A103486 A103487

Keyword

nonn,tabf

Author

Emeric Deutsch, Mar 21 2005

Status

approved