0,3

Dropping the first term and changing the boundary conditions to T(n,1)=n, T(n,n-1)=2 (n>=2), T(n,n)=1 yields the number of nonterminal symbols (which generate strings of length k) in a certain context-free grammar in Chomsky normal form that generates all permutations of n symbols. Summation over k (1<=k<=n) results in A003945. For the number of productions of this grammar: see A090327. Example: 1; 2, 1; 3, 2, 1; 4, 5, 2, 1; 5, 9, 7, 2, 1; 6, 14, 16, 9, 2, 1; In addition to the example of A090327 we have T(3,3)=#{S}=1, T(3,2)=#{D,E}=2 and T(3,1)=#{A,B,C}=3. - Peter R. J. Asveld (infprja(AT)cs.utwente.nl), Jan 29 2004

B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 25.

P. R. J. Asveld, Generating all permutations by context-free grammars in Chomsky normal form, Theoretical Computer Science 354 (2006) 118-130.

T(n, k) =T(n-1, k-1)+T(n-1, k) =C(n, k)+C(n-1, k-1) =C(n, k)*(n+k)/n =A007318(n, k)+A007318(n-1, k-1) =A061896(n+k, k) but with T(0, 0)=1 and T(1, 1)=2. Row sum is floor[3^2(n-1)] i.e. A003945. - Henry Bottomley (se16(AT)btinternet.com), Apr 26 2002

G.f.: (1+xy)/(1-x-xy). - Michael Somos, Jul 15 2003

G.f. for n-th row: (x+2*y)*(x+y)^(n-1).

1; 1 2; 1 3 2; 1 4 5 2; 1 5 9 7 2; ...

(PARI) T(n, k)=if(k<0|k>n, 0, binomial(n, k)+binomial(n-1, k-1))

Cf. A007318, A034807, A061896.

Sums along ascending diagonals give Lucas numbers, n>0.

Cf. A090327, A003945.

Adjacent sequences: A029632 A029633 A029634 this_sequence A029636 A029637 A029638

Sequence in context: A049280 A108786 A008315 this_sequence A104741 A089353 A136451

nonn,tabl,nice,easy

Mohammad K. Azarian (ma3(AT)evansville.edu)

More terms from David W. Wilson (davidwwilson(AT)comcast.net)