|
| |
|
|
A053121
|
|
Catalan triangle (with 0's) read by rows.
|
|
95
| |
|
|
1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 2, 0, 3, 0, 1, 0, 5, 0, 4, 0, 1, 5, 0, 9, 0, 5, 0, 1, 0, 14, 0, 14, 0, 6, 0, 1, 14, 0, 28, 0, 20, 0, 7, 0, 1, 0, 42, 0, 48, 0, 27, 0, 8, 0, 1, 42, 0, 90, 0, 75, 0, 35, 0, 9, 0, 1, 0, 132, 0, 165, 0, 110, 0, 44, 0, 10, 0, 1, 132, 0, 297, 0, 275, 0, 154, 0, 54, 0, 11, 0
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,8
|
|
|
COMMENTS
| Inverse lower triangular matrix of A049310(n,m) (coefficients of Chebyshev's S polynomials).
Walks with a wall: triangle of number of n-step walks from (0,0) to (n,m) where each step goes from (a,b) to (a+1,b+1) or (a+1,b-1) and the path stays in the nonnegative quadrant.
T(n,m) is the number of left factors of Dyck paths of length n ending at height m. Example: T(4,2)=3 because we have UDUU, UUDU, and UUUD, where U=(1,1) and D=(1,-1). (This is basically a different formulation of the previous - walks with a wall - property). [Emeric Deutsch, June 16, 2011].
"The Catalan triangle is formed in the same manner as Pascal's triangle, except that no number may appear on the left of the vertical bar." [Conway and Smith]
G.f. for row polynomials p(n,x) := sum(a(n,m)*x^m,m=0..n): c(z^2)/(1-x*z*c(z^2)). Row sums (x=1): A001405 (central binomial).
In the language of the Shapiro et al. reference such a lower triangular (ordinary) convolution array, considered as a matrix, belongs to the Bell-subgroup of the Riordan-group. The g.f. Ginv(x) of the m=0 column of the inverse of a given Bell-matrix (here A049310) is obtained from its g.f. of the m=0 column (here G(x)=1/(1+x^2)) by Ginv(x)=(f^{(-1)}(x))/x, with f(x) := x*G(x) and f^{(-1)}is the compositional inverse function of f (here one finds, with Ginv(0)=1, c(x^2)). See the Shapiro et al. reference.
Row sums of squares equals the Catalan sequence (A000108); for row 6: A000108(6) = 5^2 + 0^2 + 9^2 + 0^2 + 5^2 + 0^2 + 1^2 = 132. - Paul D. Hanna (pauldhanna(AT)juno.com), Apr 23 2005
Number of involutions of {1,2,...,n} that avoid the patterns 132 and have exactly k fixed points. Example: T(4,2)=3 because we have 2134, 4231 and 3214. Number of involutions of {1,2,...,n} that avoid the patterns 321 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. Number of involutions of {1,2,...,n} that avoid the patterns 213 and have exactly k fixed points. Example: T(4,2)=3 because we have 1243, 1432 and 4231. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 12 2006
Triangle T(n,k), 0<=k<=n, read by rows given by : T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=T(n-1,1), T(n,k)=T(n-1,k-1)+T(n-1,k+1) for k>=1 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 30 2007
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=x*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+y*T(n-1,k)+T(n-1,k+1) for k>=1 . Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; ((1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Sep 25 2007
Riordan array (c(x^2),xc(x^2)), where c(x) is the g.f. of Catalan numbers A000108 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 25 2007
A053121^2 = triangle A145973. Convolved with A001405 = triangle A153585. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 28 2008]
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 13 2009: (Start)
By columns without the zeros, n-th row = A000108 convolved with itself
n times; equivalent to A = (1 + x + 2x^2 + 5x^3 + 14x^4 + ...), then
n-th row = coefficients of A^(n+1). (End)
Triangle read by rows,product of A130595 and A064189 considered as infinite lower triangular arrays; A053121 = A130595*A064189 = B^(-1)*A097609*B where B = A007318. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Dec 07 2009]
Contribution from M. Dols (markdols99(AT)yahoo.com), Aug 17 2010: (Start)
As an upper right triangle, rows represent powers of 5-sqrt(24):
5-sqrt(24)^1=0,101020514..
5-sqrt(24)^2=0,010205144..
5-sqrt(24)^3=0,001030928..
(Divided by sqrt(96) these powers give a decimal representation of the columns of A007318, with 1/sqrt(96) being the middle column). (End)
T(n,k) is the number of dispersed Dyck paths of length n (i.e. Motzkin paths of length n with no (1,0) steps at positive heights) having k (1,0)-steps. Example: T(5,3)=4 because, denoting U=(1,1), D=(1,-1), H=1,0), we have HHHUD, HHUDH, HUDHH, and UDHHH. [Emeric Deutsch, Jun 1 2011]
|
|
|
REFERENCES
| I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.
J. H. Conway and D. A. Smith, On Quaternions and Octonions, A K Peters, Ltd., Natick, MA, 2003. See p. 60. MR1957212 (2004a:17002)
E. Deutsch, A. Robertson and D. Saracino, Refined restricted involutions, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 486 and 498).
D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986 (see |F_{l,p}| on page 114). - N. J. A. Sloane, Jan 29 2011
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011; http://repository.wit.ie/1693/1/AoifeThesis.pdf
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and Related Sequences Arising from Inverses of Pascal's Triangle Matrices, Fibonacci Quart. 14 (1976) 395-405.
W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fibonacci Quart. 38,5 (2000) 408-419; Note 4, pp. 414-415.
A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.
Frank Ruskey and Mark Weston, Spherical Venn Diagrams with Involutory Isometries, Electronic Journal of Combinatorics, 18 (2011), #P191; http://www.combinatorics.org/Volume_18/PDF/v18i1p191.pdf
L. W. Shapiro, S. Getu, Wen-Jin Woan and L. C. Woodson, The Riordan Group, Discrete Appl. Maths. 34 (1991) 229-239.
W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.
|
|
|
LINKS
| C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps
W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1997), 318-328.
Index entries for sequences related to Chebyshev polynomials.
|
|
|
FORMULA
| a(n, m) := 0 if n<m or n-m odd, else a(n, m) = (m+1)*binomial(n+1, (n-m)/2)/(n+1);
a(n, m) = (4*(n-1)*a(n-2, m) + 2*(m+1)*a(n-1, m-1))/(n+m+2), a(n, m)=0 if n<m, a(n, -1) := 0, a(0, 0)=1=a(1, 1), a(1, 0)=0.
G.f. for m-th column: c(x^2)*(x*c(x^2))^m, where c(x) = g.f. for Catalan numbers A000108.
G.f.: G(t,z) = c(z^2)/(1 - t*z*c(z^2)), where c(z) = (1 - sqrt(1-4*z))/(2*z) is the g.f. for the Catalan numbers (A000108). [Emeric Deutsch, June 16, 2011].
a(n, m)=a(n-1, m-1)+a(n-1, m+1) if n>0 and m >= 0, a(0, 0)=1, a(0, m)=0 if m>0, a(n, m)=0 if m<0 - Henry Bottomley (se16(AT)btinternet.com), Jan 25 2001
Sum_{k>=0} T(m, k)*T(n, k) = 0 if m+n is odd; Sum_{k>=0} T(m, k)*T(n, k) = A000108((m+n)/2) if m+n is even . - Philippe DELEHAM, May 26 2005
T(n,k)=sum{i=0..n, (-1)^(n-i)*C(n,i)*sum{j=0..i, C(i,j)*(C(i-j,j+k)-C(i-j,j+k+2))}}; Column k has e.g.f. BesselI(k,2x)-BesselI(k+2,2x); - Paul Barry (pbarry(AT)wit.ie), Feb 16 2006
Sum_{k, 0<=k<=n}T(n,k)*(k+1)=2^n . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 22 2007
Sum_{j, j>=0}T(n,j)*binomial(j,k)= A054336(n,k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 30 2007
T(2*n+1,2*k+1)=A039598(n,k), T(2*n,2*k)=A039599(n,k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Apr 16 2007
Sum_{k, 0<=k<=n} T(n,k)^x = A000027(n+1), A001405(n), A000108(n), A003161(n), A129123(n) for x = 0,1,2,3,4 respectively. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 22 2009]
Sum_{k, 0<=k<=n} T(n,k)*x^k = A126930(n), A126120(n), A001405(n), A054341(n), A126931(n) for x = -1, 0, 1, 2, 3 respectively. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 28 2009]
Sum_{k, 0<=k<=n} T(n,k)*A000045(k+1) = A098615(n). - DELEHAM Philippe, Feb 03 2012
|
|
|
EXAMPLE
| Triangle begins:
[1]
[0, 1]
[1, 0, 1]
[0, 2, 0, 1]
[2, 0, 3, 0, 1]
[0, 5, 0, 4, 0, 1]
[5, 0, 9, 0, 5, 0, 1]
[0, 14, 0, 14, 0, 6, 0, 1]
[14, 0, 28, 0, 20, 0, 7, 0, 1]
[0, 42, 0, 48, 0, 27, 0, 8, 0, 1]
[42, 0, 90, 0, 75, 0, 35, 0, 9, 0, 1]
[0, 132, 0, 165, 0, 110, 0, 44, 0, 10, 0, 1]
[132, 0, 297, 0, 275, 0, 154, 0, 54, 0, 11, 0, 1]
...
E.g. fourth row corresponds to polynomial p(3,x)= 2*x+x^3.
Contribution from Paul Barry (pbarry(AT)wit.ie), May 29 2009: (Start)
Production matrix is
0, 1,
1, 0, 1,
0, 1, 0, 1,
0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 0, 1, 0, 1 (End)
|
|
|
MAPLE
| T:=proc(n, k): if n+k mod 2 = 0 then (k+1)*binomial(n+1, (n-k)/2)/(n+1) else 0 fi end: for n from 0 to 13 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 12 2006
F:=proc(l, p) if ((l-p) mod 2) = 1 then 0 else (p+1)*l!/( ( (l-p)/2 )! * ( (l+p)/2 +1)! ); fi; end;
r:=n->[seq( F(n, p), p=0..n)]; [seq(r(n), n=0..15)]; - N. J. A. Sloane, Jan 29 2011
A053121 := proc(n, k) option remember; `if`(k>n or k<0, 0, `if`(n=k, 1,
A053121(n-1, k-1)+A053121(n-1, k+1))) end: seq(print(seq(A053121(n, k), k=0..n)), n=0..12); - Peter Luschny, May 01 2011
|
|
|
MATHEMATICA
| a[n_, m_] /; n < m || OddQ[n-m] = 0; a[n_, m_] = (m+1) Binomial[n+1, (n-m)/2]/(n+1); Flatten[Table[a[n, m], {n, 0, 12}, {m, 0, n}]] [[1 ;; 90]] (* From Jean-François Alcover, May 18 2011 *)
|
|
|
CROSSREFS
| Cf. A008315, A049310, A033184, A000108, A001405. Another version: A008313.
Variant without zero-diagonals: A033184 and with rows reversed: A009766.
A145973, A153585 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 28 2008]
Cf. A108786 [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 22 2009]
Sequence in context: A125921 A029299 A049803 * A113408 A191530 A173863
Adjacent sequences: A053118 A053119 A053120 * A053122 A053123 A053124
|
|
|
KEYWORD
| easy,nice,tabl,nonn,changed
|
|
|
AUTHOR
| Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de)
|
|
|
EXTENSIONS
| Edited by N. J. A. Sloane, Jan 29 2011
|
| |
|
|
