|
| |
|
|
A029635
|
|
The (1,2)-Pascal triangle (or Lucas triangle) read by rows.
|
|
54
|
|
|
|
2, 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;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
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, Jan 29 2004
With T(0,0)=1 : Triangle T(n,k), read by rows, given by (1,0,0,0,0,0,0,0,) DELTA (2,-1,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - From Philippe Deléham, Oct 10 2011.
For n > 0: T(n,k) = A097207(n-1,k), 0 <= k < n. [Reinhard Zumkeller, Mar 12 2012]
Much as the original Pascal triangle gives the Fibonacci numbers as sums of its diagonals, this triangle gives the Lucas numbers (A000032) as sums of its diagonals; see Posamentier & Lehmann (2007). [Alonso del Arte, Apr 09 2012]
For n > 0: T(n,k) = A029600(n,k) - A007318(n,k), 0 <= k <= n. [Reinhard Zumkeller, Apr 16 2012]
Riordan array ((2-x)/(1-x), x/(1-x)). - Philippe Deléham, Mar 15 2013
|
|
|
REFERENCES
|
P. R. J. Asveld, Generating all permutations by context-free grammars in Chomsky normal form, Theoretical Computer Science 354 (2006) 118-130.
Mohammad K. Azarian, Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227.
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.
S. Falcon, On the Lucas triangle and its relationship with the k-Lucas numbers, Journal of Mathematical and Computational Science, 2 (2012), No. 3, 425-434. Available online at http://scik.org. - From N. J. A. Sloane, Sep 20 2012
Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers. New York: Prometheus Books (2007): 97 - 105.
|
|
|
LINKS
|
Vincenzo Librandi, Rows n = 0..102, flattened
Arthur T. Benjamin, The Lucas triangle recounted
Neville Robbins, The Lucas triangle revisited, Fibonacci Quarterly 43, May 2005, pp. 142-148.
Y. Yang and J. Leida, Pascal decompositions of geometric arrays in matrices, The Fibonacci Quarterly 42.3 (2004)
|
|
|
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, 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, Aug 14 2008
T(2n,n)-T(2n,n+1)= Catalan(n)= A000108(n). [From Philippe DELEHAM, Mar 19 2009]
With T(0,0) = 1, as in the Example section below, this is known as Vieta's array. The LU factorization of the square array is given by Yang and Leida, equation 20. - Peter Bala, Feb 11 2012
|
|
|
EXAMPLE
|
Triangle begins:
2;
1 2;
1 3 2;
1 4 5 2;
1 5 9 7 2;
...
Comment from Peter Bala, Aug 14 2008: Read as a square, the array begins
===================================
n\k|...0...1....2.....3.....4.....5
===================================
0..|...2...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
...
|
|
|
MATHEMATICA
|
t[0, 0] = 2; t[n_, k_] := If[k < 0 || k > n, 0, Binomial[n, k] + Binomial[n-1, k-1]]; Flatten[Table[t[n, k], {n, 0, 11}, {k, 0, n}]] (* From Jean-François Alcover, May 03 2011 *)
(* The next program cogenerates A029635 and A029638. *)
u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := u[n - 1, x] + v[n - 1, x]
v[n_, x_] := x*u[n - 1, x] + x*v[n - 1, x] + 1
Table[Factor[u[n, x]], {n, 1, z}]
Table[Factor[v[n, x]], {n, 1, z}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%] (* A029638 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%] (* A029635 *)
(* Clark Kimberling, Feb 20 2012 *)
|
|
|
PROG
|
(PARI) T(n, k)=if(k<0|k>n, 0, binomial(n, k)+binomial(n-1, k-1))
(Haskell)
a029635 n k = a029635_tabl !! n !! k
a029635_row n = a029635_tabl !! n
a029635_tabl = [2] : iterate
(\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1, 2]
-- Reinhard Zumkeller, Mar 12 2012, Feb 23 2012
|
|
|
CROSSREFS
|
Cf. A007318, A034807, A061896, A029653 (row-reversed), A157000.
Sums along ascending diagonals give Lucas numbers, n>0.
Cf. A090327, A003945, A029638.
Sequence in context: A087467 A128118 A205696 * A203301 A107456 A165112
Adjacent sequences: A029632 A029633 A029634 * A029636 A029637 A029638
|
|
|
KEYWORD
|
nonn,tabl,nice,easy
|
|
|
AUTHOR
|
Mohammad K. Azarian
|
|
|
EXTENSIONS
|
More terms from David W. Wilson
Changed a(0) to 2 (was 1), Daniel Forgues, Jul 06 2010
|
|
|
STATUS
|
approved
|
| |
|
|
