|
| |
|
|
A008315
|
|
Catalan triangle read by rows. Also triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).
|
|
20
| |
|
|
1, 1, 1, 1, 1, 2, 1, 3, 2, 1, 4, 5, 1, 5, 9, 5, 1, 6, 14, 14, 1, 7, 20, 28, 14, 1, 8, 27, 48, 42, 1, 9, 35, 75, 90, 42, 1, 10, 44, 110, 165, 132, 1, 11, 54, 154, 275, 297, 132, 1, 12, 65, 208, 429, 572, 429, 1, 13, 77, 273, 637, 1001, 1001, 429, 1, 14, 90, 350, 910, 1638, 2002, 1430, 1, 15, 104
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,6
|
|
|
COMMENTS
| There are several versions of a Catalan triangle: see A009766, A008315, A028364, A053121.
Number of standard tableaux of shape (n-k,k) (0<=k<=floor(n/2)). Example: T(4,1)=3 because in th top row we can have 124, 134, or 123 (but not 234). - Emeric Deutsch (deutsch(AT)duke.poly.edu), May 23 2004
T(n,k) is the number of n-digit binary words (length n sequences on {0,1}) containing k 1's such that no initial segment of the sequence has more 1's than 0's. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 31 2009]
T(n,k) is the number of dispersed Dyck paths (i.e. Motzkin paths with no (1,0) steps at positive heights) of length n and having k (1,1)-steps. Example: T(5,1)=4 because, denoting U=(1,1), D=(1,-1), H=1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. [Emeric Deutsch, May 30 2011]
T(n,k) is the number of length n left factors of Dyck paths having k (1,-1)-steps. Example: T(5,1)=4 because, denoting U=(1,1), D=(1,-1), we have UUUUD, UUUDU, UUDUU, and UDUUU. There is a simple bijection between length n left factors of Dyck paths and dispersed Dyck paths of length n, that takes D steps into D steps. [Emeric Deutsch, Jun 19 2011]
Triangle, with zeros omitted, given by (1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -1, 1, ...) DELTA (0, 1, -1, 0, 0, 1, -1, 0, 0, 1, -1, 0, 0, 1, ...) where DELTA is the operator defined in A084938. - DELEHAM Philippe, Dec 12 2011
|
|
|
REFERENCES
| M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 796.
K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.
P. J. Larcombe, A question of proof..., Bull. Inst. Math. Applic. (IMA), 30, Nos. 3/4, 1994, 52-54.
|
|
|
LINKS
| T. D. Noe, Rows n=0..100 of triangle, flattened
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6
Index entries for sequences related to Chebyshev polynomials.
|
|
|
FORMULA
| T(n, 0)=1 if n >= 0; T(2*k, k)=T(2*k-1, k-1) if k>0; T(n, k)=T(n-1, k-1)+T(n-1, k) if k=1, 2, ...[ n/2 ].
T(n, k) = C(n, k)-C(n, k-1) where C(n, k) is a binomial coefficient.
Rows of Catalan triangle A008313 read backwards. Sum_{k>=0} T(n, k)^2 = A000108(n); A000108 : Catalan numbers. - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 15 2004
T(n,k)=Binomial(n,k)*(n-2*k+1)/(n-k+1) [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 31 2009]
Sum_{k, 0<=k<=n} T(n,k)*x^k = A000012(n), A001405(n), A126087(n), A128386(n), A121724(n), A128387(n), A132373(n), A132374(n), A132375(n), A121725(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - DELEHAM Philippe, Dec 12 2011
|
|
|
EXAMPLE
| Triangle begins:
1;
1;
1,1;
1,2;
1,3,2;
1,4,5;
1,5,9,5;
1,6,14,14;
1,7,20,28,14;
...
T(5,2)=5 because there are 5 such sequences: {0, 0, 0, 1, 1}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 1, 0} [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 31 2009]
|
|
|
MATHEMATICA
| Table[Binomial[k, i]*(k - 2 i + 1)/(k - i + 1), {k, 0, 20}, {i, 0, Floor[k/2]}] // Grid [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 31 2009]
|
|
|
PROG
| (PARI) T(n, k)=if(k<0|k>n\2, 0, if(n==0, 1, T(n-1, k-1) + T(n-1, k))).
|
|
|
CROSSREFS
| T(2n, n) = A000108 (Catalan numbers), row sums = A001405 (central binomial coefficients).
This is also the positive half of the triangle in A008482 - Michael Somos
This is another reading (by shallow diagonals) of the triangle A009766, i.e. A008315[n] = A009766[A056536[n]].
Cf. A120730
Sequence in context: A165999 A049280 A108786 * A191318 A191395 A183917
Adjacent sequences: A008312 A008313 A008314 * A008316 A008317 A008318
|
|
|
KEYWORD
| nonn,tabf,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Expanded description from Clark Kimberling Jun 15 1997
|
| |
|
|
