|
%I #185 May 21 2022 14:50:54
%S 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 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 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 Catalan triangle (with 0's) read by rows.
%C Inverse lower triangular matrix of A049310(n,m) (coefficients of Chebyshev's S polynomials).
%C 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 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 "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 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 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 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 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 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^2 = triangle A145973. Convolved with A001405 = triangle A153585. - _Gary W. Adamson_, Dec 28 2008
%C 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 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 From _Mark Dols_, Aug 17 2010: (Start)
%C As an upper right triangle, rows represent powers of 5-sqrt(24):
%C 5 - sqrt(24)^1 = 0.101020514...
%C 5 - sqrt(24)^2 = 0.010205144...
%C 5 - sqrt(24)^3 = 0.001030928...
%C (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 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 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 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 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 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 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 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 From _Roger Ford_, Jan 22 2018: (Start)
%C 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 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 .
%C top UuUdUddd c=3 top UdUuUddd c=1 top UdUdUudd c=1
%C /\ /\
%C //\\ / \
%C // \\ / /\ \ /\
%C // \\ / / \ \ / \
%C ///\ /\\\ /\ / / /\ \ \ /\ /\ / /\ \
%C \\\ \/ /// \ \ \ \/ / / / \ \ \ \/ / / /
%C \\\ /// \ \ \ / / / \ \ \ / / /
%C \\\/// \ \ \/ / / \ \ \/ / /
%C \\// \ \ / / \ \ / /
%C \/ \ \/ / \ \/ /
%C \ / \ /
%C \/ \/
%C 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 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 A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.
%H Reinhard Zumkeller, <a href="/A053121/b053121.txt">Rows n=0..150 of triangle, flattened</a>
%H I. Bajunaid et al., <a href="http://www.jstor.org/stable/30037599">Function series, Catalan numbers and random walks on trees</a>, Amer. Math. Monthly 112 (2005), 765-785.
%H C. Banderier and D. Merlini, <a href="http://algo.inria.fr/banderier/Papers/infjumps.ps">Lattice paths with an infinite set of jumps</a>
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry1/barry97r2.html">Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms</a>, J. Int. Seq. 14 (2011) # 11.2.2, example 3.
%H Paul Barry, <a href="https://arxiv.org/abs/2101.06713">On the inversion of Riordan arrays</a>, arXiv:2101.06713 [math.CO], 2021.
%H Paul Barry and A. Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry5/barry96s.html">Meixner-Type Results for Riordan Arrays and Associated Integer Sequences</a>, J. Int. Seq. 13 (2010) # 10.9.4, example 3.
%H Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p8">Combinatorial proofs of addition formulas</a>, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
%H J. Cigler, <a href="http://homepage.univie.ac.at/johann.cigler/preprints/cheb-survey.pdf">Some q-analogues of Fibonacci, Lucas and Chebyshev polynomials with nice moments</a>, 2013.
%H J. Cigler, <a href="http://homepage.univie.ac.at/Johann.Cigler/preprints/chebyshev-survey.pdf">Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results</a>, 2013.
%H J. Cigler, <a href="http://homepage.univie.ac.at/Johann.Cigler/preprints/gould.pdf">Some notes on q-Gould polynomials</a>, 2013.
%H E. Deutsch, A. Robertson and D. Saracino, <a href="http://dx.doi.org/10.1016/j.ejc.2004.09.006">Refined restricted involutions</a>, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 486 and 498).
%H J. East and R. D. Gray, <a href="http://arxiv.org/abs/1404.2359">Idempotent generators in finite partition monoids and related semigroups</a>, arXiv preprint arXiv:1404.2359, 2014
%H D. Gouyou-Beauchamps, <a href="https://doi.org/10.1007/BFb0072513">Chemins sous-diagonaux et tableau de Young</a>, 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 Aoife Hennessy, <a href="http://repository.wit.ie/1693">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H V. E. Hoggatt, Jr. and M. Bicknell, <a href="http://www.fq.math.ca/Scanned/14-5/hoggatt1.pdf">Catalan and related sequences arising from inverses of Pascal's triangle matrices</a>, Fib. Quart., 14 (1976), 395-405.
%H W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, <a href="http://www.fq.math.ca/Scanned/35-4/klostermeyer.pdf">A Pascal rhombus</a>, Fibonacci Quarterly, 35 (1997), 318-328.
%H Wolfdieter Lang, <a href="/A049310/a049310appl.pdf ">Chebyshev S-polynomials: ten applications.</a>
%H Wolfdieter Lang, <a href="http://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38,5 (2000) 408-419; Note 4, pp. 414-415.
%H MathOverflow, <a href="http://mathoverflow.net/questions/207681">Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?</a>
%H A. Nkwanta and A. Tefera, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Nkwanta/nkwanta4.html">Curious Relations and Identities Involving the Catalan Generating Function and Numbers</a>, Journal of Integer Sequences, 16 (2013), #13.9.5.
%H Frank Ruskey and Mark Weston, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p191">Spherical Venn Diagrams with Involutory Isometries</a>, Electronic Journal of Combinatorics, 18 (2011), #P191.
%H L. W. Shapiro, S. Getu, Wen-Jin Woan and L. C. Woodson, <a href="http://dx.doi.org/10.1016/0166-218X(91)90088-E">The Riordan Group</a>, Discrete Appl. Maths. 34 (1991) 229-239.
%H Yidong Sun and Luping Ma, <a href="https://doi.org/10.1016/j.ejc.2014.01.004">Minors of a class of Riordan arrays related to weighted partial Motzkin paths</a>. Eur. J. Comb. 39, 157-169 (2014).
%H Mark C. Wilson, <a href="http://www.cs.auckland.ac.nz/~mcw/Research/Outputs/Wils2013.pdf">Diagonal asymptotics for products of combinatorial classes</a>.
%H W.-J. Woan, <a href="http://dx.doi.org/10.1016/S0012-365X(00)00162-X">Area of Catalan Paths</a>, Discrete Math., 226 (2001), 439-444.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%F 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);
%F 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.
%F G.f. for m-th column: c(x^2)*(x*c(x^2))^m, where c(x) = g.f. for Catalan numbers A000108.
%F 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
%F 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
%F Sum_{k>=0} T(m,k)^2 = A000108(m). - _Paul D. Hanna_, Apr 23 2005
%F 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 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 Sum_{k=0..n} T(n,k)*(k+1) = 2^n. - _Philippe Deléham_, Mar 22 2007
%F Sum_{j>=0} T(n,j)*binomial(j,k) = A054336(n,k). - _Philippe Deléham_, Mar 30 2007
%F 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 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 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 Sum_{k=0..n} T(n,k)*A000045(k+1) = A098615(n). - _Philippe Deléham_, Feb 03 2012
%F 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 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 Sum_{m=1..n} a(n,m) = A037952(n). - _R. J. Mathar_, Sep 23 2021
%e Triangle a(n,m) begins:
%e n\m 0 1 2 3 4 5 6 7 8 9 10 ...
%e 0: 1
%e 1: 0 1
%e 2: 1 0 1
%e 3: 0 2 0 1
%e 4: 2 0 3 0 1
%e 5: 0 5 0 4 0 1
%e 6: 5 0 9 0 5 0 1
%e 7: 0 14 0 14 0 6 0 1
%e 8: 14 0 28 0 20 0 7 0 1
%e 9: 0 42 0 48 0 27 0 8 0 1
%e 10: 42 0 90 0 75 0 35 0 9 0 1
%e ... (Reformatted by _Wolfdieter Lang_, Sep 20 2013)
%e E.g., the fourth row corresponds to the polynomial p(3,x)= 2*x + x^3.
%e From _Paul Barry_, May 29 2009: (Start)
%e Production matrix is
%e 0, 1,
%e 1, 0, 1,
%e 0, 1, 0, 1,
%e 0, 0, 1, 0, 1,
%e 0, 0, 0, 1, 0, 1,
%e 0, 0, 0, 0, 1, 0, 1,
%e 0, 0, 0, 0, 0, 1, 0, 1,
%e 0, 0, 0, 0, 0, 0, 1, 0, 1,
%e 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 (End)
%e 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 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 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 r:=n->[seq( F(n,p),p=0..n)]; [seq(r(n),n=0..15)]; # _N. J. A. Sloane_, Jan 29 2011
%p A053121 := proc(n,k) option remember; `if`(k>n or k<0,0,`if`(n=k,1,
%p procname(n-1,k-1)+procname(n-1,k+1))) end proc:
%p seq(print(seq(A053121(n,k), k=0..n)),n=0..12); # _Peter Luschny_, May 01 2011
%t 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 (Haskell)
%o a053121 n k = a053121_tabl !! n !! k
%o a053121_row n = a053121_tabl !! n
%o a053121_tabl = iterate
%o (\row -> zipWith (+) ([0] ++ row) (tail row ++ [0,0])) [1]
%o -- _Reinhard Zumkeller_, Feb 24 2012
%o (Sage)
%o def A053121_triangle(dim):
%o M = matrix(ZZ,dim,dim)
%o for n in (0..dim-1): M[n,n] = 1
%o for n in (1..dim-1):
%o for k in (0..n-1):
%o M[n,k] = M[n-1,k-1] + M[n-1,k+1]
%o return M
%o A053121_triangle(13) # _Peter Luschny_, Sep 19 2012
%o (PARI) T(n, m)=if(n<m||(n-m)%2, return(0)); (m+1)*binomial(n+1, (n-m)/2)/(n+1)
%o for(n=0,9, for(m=0,n, print1(T(n,m)", "))) \\ _Charles R Greathouse IV_, Mar 09 2016
%Y Cf. A008315, A049310, A000108, A001405 (row sums), A145973, A153585, A108786, A037952. Another version: A008313. A039598 and A039599 without zeros, and odd and even numbered rows).
%Y Variant without zero-diagonals: A033184 and with rows reversed: A009766.
%K easy,nice,tabl,nonn
%O 0,8
%A _Wolfdieter Lang_
%E Edited by _N. J. A. Sloane_, Jan 29 2011
|
