login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A053121 Catalan triangle (with 0's) read by rows. 103
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; text; 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, Jun 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, 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, 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 Deléham, 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 Deléham, Sep 25 2007

Riordan array (c(x^2),xc(x^2)), where c(x) is the g.f. of Catalan numbers A000108. - Philippe Deléham, Nov 25 2007

A053121^2 = triangle A145973. Convolved with A001405 = triangle A153585. - Gary W. Adamson, Dec 28 2008

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). - Gary W. Adamson, May 13 2009

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. - Philippe Deléham, Dec 07 2009

From Mark Dols, 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 01 2011

Let S(N,x) denote the N-th Chebyshev S-polynomial in x (see A049310, cf. [W. Lang]). Then x^n = sum_{k=0..n} T(n,k)*S(k,x). - L. Edson Jeffery, Sep 06 2012

This triangle a(n,m) appears also in the (unreduced) formula for the powers rho(N)^n for the algebraic number over the rationals rho(N) = 2*cos(Pi/N) = R(N, 2), the smallest diagonal/side ratio R in the regular N-gon:

  rho(N)^n = sum(a(n,m)*R(N,m+1),m=0..n), n>=0, identical in N >= 1. R(N,j) = S(j-1, x=rho(N)) (Chebyshev S (A049310)). See a comment on this under A039599 (even powers) and A039598 (odd powers). Proof: see the Sep 06 2012 comment by L. Edson Jeffery, which follows from T(n,k) (called here a(n,k)) being the inverse of the Riordan triangle A049310. - Wolfdieter Lang, Sep 21 2013

The so called A-sequence for this Riordan triangle of the Bell type (c(x^2), x*c(x^2)) (see comments above) is A(x) = 1 + x^2. This proves the recurrence given in the formula section by Henry Bottomley for a(n, m) = a(n-1, m-1) + a(n-1, m+1) for n>=1 and m>=1, with inputs. The Z-sequence for this Riordan triangle is Z(x) = x which proves the recurrence a(n,0) = a(n-1,1), n>=1, a(0,0) = 1. For A- and Z-sequences for Riordan triangles see the W. Lang link under A006232. - Wolfdieter Lang, Sep 22 2013

Rows of the triangle describe decompositions of tensor powers of the standard (2-dimensional) representation of the Lie algebra sl(2) into irreducibles. Thus a(n,m) is the multiplicity of the m-th ((m+1)-dimensional) irreducible representation in the n-th tensor power of the standard one. - Mamuka Jibladze, May 26 2015

REFERENCES

Xiang-Ke Chang, XB Hu, H Lei, YN Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.

J. H. Conway and D. A. Smith, On Quaternions and Octonions, A K Peters, Ltd., Natick, MA, 2003. See p. 60. MR1957212 (2004a:17002)

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

A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.

LINKS

Reinhard Zumkeller, Rows n=0..150 of triangle, flattened

I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps

J. Cigler, Some q-analogues of Fibonacci, Lucas and Chebyshev polynomials with nice moments, 2013.

J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, 2013.

J. Cigler, Some notes on q-Gould polynomials, 2013.

E. Deutsch, A. Robertson and D. Saracino, Refined restricted involutions, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 486 and 498).

J. East, R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014

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.

V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.

W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1997), 318-328.

W. Lang, Chebyshev S-polynomials: ten applications.

W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419; Note 4, pp. 414-415.

MathOverflow, Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

A. Nkwanta, A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.

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.

Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes.

W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.

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, Jun 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, 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 Deléham, 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, Feb 16 2006

Sum_{k, 0<=k<=n}T(n,k)*(k+1)=2^n. - Philippe Deléham, Mar 22 2007

Sum_{j, j>=0}T(n,j)*binomial(j,k)= A054336(n,k). - Philippe Deléham, Mar 30 2007

T(2*n+1,2*k+1)=A039598(n,k), T(2*n,2*k)=A039599(n,k). - Philippe Deléham, 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. - Philippe Deléham, 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. - Philippe Deléham, Nov 28 2009

Sum_{k, 0<=k<=n} T(n,k)*A000045(k+1) = A098615(n). - Philippe Deléham, Feb 03 2012

Recurrence for row polynomials C(n, x) := Sum_{m=0..n} a(n, m)*x^m  = x*Sum_{k=0..n} Chat(k)*C(n-1-k, x), n >= 0, with C(-1, 1/x) = 1/x and Chat(k) = A000108(k/2) if n is even and 0 else. From the o.g.f. of the row polynomials: G(z; x) := Sum_{n >= 0} C(n, x)*z^n = c(z^2)*(1 + x*z*G(z, x)), with the o.g.f. c of A000108. - Ahmet Zahid KÜÇÜK and Wolfdieter Lang, Aug 23 2015

EXAMPLE

Triangle a(n,m) begins:

n\m  0   1   2   3   4   5   6  7  8  9 10 ...

0:   1

1:   0   1

2:   1   0   1

3:   0   2   0   1

4:   2   0   3   0   1

5:   0   5   0   4   0   1

6:   5   0   9   0   5   0   1

7:   0  14   0  14   0   6   0  1

8:  14   0  28   0  20   0   7  0  1

9:   0  42   0  48   0  27   0  8  0  1

10: 42   0  90   0  75   0  35  0  9  0  1

... (Reformatted by Wolfdieter Lang, Sep 20 2013)

E.g., the fourth row corresponds to the polynomial p(3,x)= 2*x + x^3.

From Paul Barry, 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, 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,

procname(n-1, k-1)+procname(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]] (* Jean-François Alcover, May 18 2011 *)

PROG

(Haskell)

a053121 n k = a053121_tabl !! n !! k

a053121_row n = a053121_tabl !! n

a053121_tabl = iterate

   (\row -> zipWith (+) ([0] ++ row) (tail row ++ [0, 0])) [1]

-- Reinhard Zumkeller, Feb 24 2012

(Sage)

def A053121_triangle(dim):

    M = matrix(SR, dim, dim)

    for n in (0..dim-1): M[n, n] = 1

    for n in (1..dim-1):

        for k in (0..n-1):

            M[n, k] = M[n-1, k-1] + M[n-1, k+1]

    return M

A053121_triangle(13) # Peter Luschny, Sep 19 2012

(PARI) T(n, m)=if(n<m||(n-m)%2, return(0)); (m+1)*binomial(n+1, (n-m)/2)/(n+1)

for(n=0, 9, for(m=0, n, print1(T(n, m)", "))) \\ Charles R Greathouse IV, Mar 09 2016

CROSSREFS

Cf. A008315, A049310, A000108, A001405, A145973, A153585, A108786. Another version: A008313. A039598 and A039599 without zeros, and odd and even numbered rows).

Variant without zero-diagonals: A033184 and with rows reversed: A009766.

Sequence in context: A029299 A281666 A049803 * A113408 A242653 A191530

Adjacent sequences:  A053118 A053119 A053120 * A053122 A053123 A053124

KEYWORD

easy,nice,tabl,nonn

AUTHOR

Wolfdieter Lang

EXTENSIONS

Edited by N. J. A. Sloane, Jan 29 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 18:42 EDT 2017. Contains 286926 sequences.