|
Search: id:A029635
|
|
|
| A029635 |
|
The (1,2)-Pascal triangle (or Lucas triangle) read by rows. |
|
+0
41
|
|
| 1, 1, 2, 1, 3, 2, 1, 4, 5, 2, 1, 5, 9, 7, 2, 1, 6, 14, 16, 9, 2, 1, 7, 20, 30, 25, 11, 2, 1, 8, 27, 50, 55, 36, 13, 2, 1, 9, 35, 77, 105, 91, 49, 15, 2, 1, 10, 44, 112, 182, 196, 140, 64, 17, 2, 1, 11, 54, 156, 294, 378, 336, 204, 81, 19, 2, 1, 12, 65, 210, 450, 672, 714, 540, 285, 100
(list; table; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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
|
|
REFERENCES
|
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.
|
|
FORMULA
|
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).
O.g.f. for row n: (1+x)/(1-x)^(n+1). The entries in row n are the nonzero entries in column n of A053120 divided by 2^(n-1). - Peter Bala (pbala(AT)toucansurf.com), Aug 14 2008
T(2n,n)-T(2n,n+1)= Catalan(n)= A000108(n). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 19 2009]
|
|
EXAMPLE
|
1; 1 2; 1 3 2; 1 4 5 2; 1 5 9 7 2; ...
Comment from Peter Bala (pbala(AT)toucansurf.com), Aug 14 2008: Read as a square, the array begins
===================================
n\k|...0...1....2.....3.....4.....5
===================================
0..|...1...2....2.....2.....2.....2 A040000
1..|...1...3....5.....7.....9....11 A005408
2..|...1...4....9....16....25....36 A000290
3..|...1...5...14....30....55....91 A000330
4..|...1...6...20....50...105...196 A002415
5..|...1...7...27....77...182...378 A005585
6..|...1...8...35...112...294...672 A040977
...
|
|
PROGRAM
|
(PARI) T(n, k)=if(k<0|k>n, 0, binomial(n, k)+binomial(n-1, k-1))
|
|
CROSSREFS
|
Cf. A007318, A034807, A061896.
Sums along ascending diagonals give Lucas numbers, n>0.
Cf. A090327, A003945.
Sequence in context: A049280 A108786 A008315 this_sequence A104741 A167237 A089353
Adjacent sequences: A029632 A029633 A029634 this_sequence A029636 A029637 A029638
|
|
KEYWORD
|
nonn,tabl,nice,easy
|
|
AUTHOR
|
Mohammad K. Azarian (ma3(AT)evansville.edu)
|
|
EXTENSIONS
|
More terms from David W. Wilson (davidwwilson(AT)comcast.net)
|
|
|
Search completed in 0.003 seconds
|
