# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a053121
Showing 1-1 of 1
%I A053121 #189 Aug 13 2024 05:03:52
%S A053121 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,
%T A053121 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,
%U A053121 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
%N A053121 Catalan triangle (with 0's) read by rows.
%C A053121 Inverse lower triangular matrix of A049310(n,m) (coefficients of Chebyshev's S polynomials).
%C A053121 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.
%C A053121 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
%C A053121 "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]
%C A053121 G.f. for row polynomials p(n,x) := Sum_{m=0..n} (a(n,m)*x^m): c(z^2)/(1-x*z*c(z^2)). Row sums (x=1): A001405 (central binomial).
%C A053121 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.
%C A053121 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
%C A053121 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
%C A053121 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
%C A053121 A053121^2 = triangle A145973. Convolved with A001405 = triangle A153585. - _Gary W. Adamson_, Dec 28 2008
%C A053121 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
%C A053121 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
%C A053121 From _Mark Dols_, Aug 17 2010: (Start)
%C A053121 As an upper right triangle, rows represent powers of 5-sqrt(24):
%C A053121 5 - sqrt(24)^1 = 0.101020514...
%C A053121 5 - sqrt(24)^2 = 0.010205144...
%C A053121 5 - sqrt(24)^3 = 0.001030928...
%C A053121 (Divided by sqrt(96) these powers give a decimal representation of the columns of A007318, with 1/sqrt(96) being the middle column.) (End)
%C A053121 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
%C A053121 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
%C A053121 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:
%C A053121 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
%C A053121 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
%C A053121 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
%C A053121 The Riordan row polynomials p(n, x) belong to the Boas-Buck class (see a comment and references in A046521), hence they satisfy the Boas-Buck identity: (E_x - n*1)*p(n, x) = (E_x + 1)*Sum_{j=0..n-1} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)*p(n-1-j, x), for n >= 0, where E_x = x*d/dx (Euler operator). For the triangle a(n, m) this entails a recurrence for the sequence of column m, given in the formula section. - _Wolfdieter Lang_, Aug 11 2017
%C A053121 From _Roger Ford_, Jan 22 2018: (Start)
%C A053121 For row n, the nonzero values represent the odd components (loops) formed by n+1 nonintersecting arches above and below the x-axis with the following constraints: The top has floor((n+3)/2) starting arches at position 1 and the next consecutive odd positions. All other starting top arches are in even positions. The bottom arches are a rainbow of arches. If the component=1 then the arch configuration is a semimeander solution.
%C A053121 Examples: For row 3 {0, 2, 0, 1} there are 3 arch configurations: 2 arch configurations have a component=1; 1 has a component=3. c=components, U=top arch starting in odd position, u=top arch starting in an even position, d=ending top arch:
%C A053121 .
%C A053121 top UuUdUddd c=3 top UdUuUddd c=1 top UdUdUudd c=1
%C A053121 /\ /\
%C A053121 //\\ / \
%C A053121 // \\ / /\ \ /\
%C A053121 // \\ / / \ \ / \
%C A053121 ///\ /\\\ /\ / / /\ \ \ /\ /\ / /\ \
%C A053121 \\\ \/ /// \ \ \ \/ / / / \ \ \ \/ / / /
%C A053121 \\\ /// \ \ \ / / / \ \ \ / / /
%C A053121 \\\/// \ \ \/ / / \ \ \/ / /
%C A053121 \\// \ \ / / \ \ / /
%C A053121 \/ \ \/ / \ \/ /
%C A053121 \ / \ /
%C A053121 \/ \/
%C A053121 For row 4 {2, 0, 3, 0, 1} there are 6 arch configurations: 2 have a component=1; 3 have a component=3: 1 has a component=1. (End)
%D A053121 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 A053121 A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.
%H A053121 Reinhard Zumkeller, Rows n=0..150 of triangle, flattened
%H A053121 I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.
%H A053121 C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps
%H A053121 Paul Barry, Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms, J. Int. Seq. 14 (2011) # 11.2.2, example 3.
%H A053121 Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
%H A053121 Paul Barry and A. Hennessy, Meixner-Type Results for Riordan Arrays and Associated Integer Sequences, J. Int. Seq. 13 (2010) # 10.9.4, example 3.
%H A053121 Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
%H A053121 J. Cigler, Some q-analogues of Fibonacci, Lucas and Chebyshev polynomials with nice moments, 2013.
%H A053121 J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, 2013.
%H A053121 J. Cigler, Some notes on q-Gould polynomials, 2013.
%H A053121 E. Deutsch, A. Robertson and D. Saracino, Refined restricted involutions, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 486 and 498).
%H A053121 J. East and R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014
%H A053121 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
%H A053121 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.
%H A053121 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.
%H A053121 W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1997), 318-328.
%H A053121 Wolfdieter Lang, Chebyshev S-polynomials: ten applications.
%H A053121 Wolfdieter 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.
%H A053121 MathOverflow, Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?
%H A053121 A. Nkwanta and A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.
%H A053121 Frank Ruskey and Mark Weston, Spherical Venn Diagrams with Involutory Isometries, Electronic Journal of Combinatorics, 18 (2011), #P191.
%H A053121 L. W. Shapiro, S. Getu, Wen-Jin Woan and L. C. Woodson, The Riordan Group, Discrete Appl. Maths. 34 (1991) 229-239.
%H A053121 Yidong Sun and Luping Ma, Minors of a class of Riordan arrays related to weighted partial Motzkin paths. Eur. J. Comb. 39, 157-169 (2014).
%H A053121 Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes.
%H A053121 W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.
%H A053121 Index entries for sequences related to Chebyshev polynomials.
%F A053121 a(n, m) := 0 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
%F A053121 Sum_{k>=0} T(m,k)^2 = A000108(m). - _Paul D. Hanna_, Apr 23 2005
%F A053121 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
%F A053121 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
%F A053121 Sum_{k=0..n} T(n,k)*(k+1) = 2^n. - _Philippe Deléham_, Mar 22 2007
%F A053121 Sum_{j>=0} T(n,j)*binomial(j,k) = A054336(n,k). - _Philippe Deléham_, Mar 30 2007
%F A053121 T(2*n+1,2*k+1) = A039598(n,k), T(2*n,2*k) = A039599(n,k). - _Philippe Deléham_, Apr 16 2007
%F A053121 Sum_{k=0..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
%F A053121 Sum_{k=0..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
%F A053121 Sum_{k=0..n} T(n,k)*A000045(k+1) = A098615(n). - _Philippe Deléham_, Feb 03 2012
%F A053121 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 otherwise. 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
%F A053121 The Boas-Buck recurrence (see a comment above) for the sequence of column m is: a(n, m) = ((m+1)/(n-m))*Sum_{j=0..n-1-m} (1/2)*(1 - (-1)^j)*binomial(j+1, (j+1)/2)* a(n-1-j, k), for n > m >= 0 and input a(m, m) = 1. - _Wolfdieter Lang_, Aug 11 2017
%F A053121 Sum_{m=1..n} a(n,m) = A037952(n). - _R. J. Mathar_, Sep 23 2021
%e A053121 Triangle a(n,m) begins:
%e A053121 n\m 0 1 2 3 4 5 6 7 8 9 10 ...
%e A053121 0: 1
%e A053121 1: 0 1
%e A053121 2: 1 0 1
%e A053121 3: 0 2 0 1
%e A053121 4: 2 0 3 0 1
%e A053121 5: 0 5 0 4 0 1
%e A053121 6: 5 0 9 0 5 0 1
%e A053121 7: 0 14 0 14 0 6 0 1
%e A053121 8: 14 0 28 0 20 0 7 0 1
%e A053121 9: 0 42 0 48 0 27 0 8 0 1
%e A053121 10: 42 0 90 0 75 0 35 0 9 0 1
%e A053121 ... (Reformatted by _Wolfdieter Lang_, Sep 20 2013)
%e A053121 E.g., the fourth row corresponds to the polynomial p(3,x)= 2*x + x^3.
%e A053121 From _Paul Barry_, May 29 2009: (Start)
%e A053121 Production matrix is
%e A053121 0, 1,
%e A053121 1, 0, 1,
%e A053121 0, 1, 0, 1,
%e A053121 0, 0, 1, 0, 1,
%e A053121 0, 0, 0, 1, 0, 1,
%e A053121 0, 0, 0, 0, 1, 0, 1,
%e A053121 0, 0, 0, 0, 0, 1, 0, 1,
%e A053121 0, 0, 0, 0, 0, 0, 1, 0, 1,
%e A053121 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 (End)
%e A053121 Boas-Buck recurrence for column k = 2, n = 6: a(6, 2) = (3/4)*(0 + 2*a(4 ,2) + 0 + 6*a(2, 2)) = (3/4)*(2*3 + 6) = 9. - _Wolfdieter Lang_, Aug 11 2017
%p A053121 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
%p A053121 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;
%p A053121 r:=n->[seq( F(n,p),p=0..n)]; [seq(r(n),n=0..15)]; # _N. J. A. Sloane_, Jan 29 2011
%p A053121 A053121 := proc(n,k) option remember; `if`(k>n or k<0,0,`if`(n=k,1,
%p A053121 procname(n-1,k-1)+procname(n-1,k+1))) end proc:
%p A053121 seq(print(seq(A053121(n,k), k=0..n)),n=0..12); # _Peter Luschny_, May 01 2011
%t A053121 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 *)
%o A053121 (Haskell)
%o A053121 a053121 n k = a053121_tabl !! n !! k
%o A053121 a053121_row n = a053121_tabl !! n
%o A053121 a053121_tabl = iterate
%o A053121 (\row -> zipWith (+) ([0] ++ row) (tail row ++ [0,0])) [1]
%o A053121 -- _Reinhard Zumkeller_, Feb 24 2012
%o A053121 (Sage)
%o A053121 def A053121_triangle(dim):
%o A053121 M = matrix(ZZ,dim,dim)
%o A053121 for n in (0..dim-1): M[n,n] = 1
%o A053121 for n in (1..dim-1):
%o A053121 for k in (0..n-1):
%o A053121 M[n,k] = M[n-1,k-1] + M[n-1,k+1]
%o A053121 return M
%o A053121 A053121_triangle(13) # _Peter Luschny_, Sep 19 2012
%o A053121 (PARI) T(n, m)=if(n