A026726 -id:A026726 - cp's OEIS frontend

A039599 Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).

1, 1, 1, 2, 3, 1, 5, 9, 5, 1, 14, 28, 20, 7, 1, 42, 90, 75, 35, 9, 1, 132, 297, 275, 154, 54, 11, 1, 429, 1001, 1001, 637, 273, 77, 13, 1, 1430, 3432, 3640, 2548, 1260, 440, 104, 15, 1, 4862, 11934, 13260, 9996, 5508, 2244, 663, 135, 17, 1

Offset: 0

N. J. A. Sloane

T(n,k) is the number of lattice paths from (0,0) to (n,n) with steps E = (1,0) and N = (0,1) which touch but do not cross the line x - y = k and only situated above this line; example: T(3,2) = 5 because we have EENNNE, EENNEN, EENENN, ENEENN, NEEENN. - Philippe Deléham, May 23 2005
The matrix inverse of this triangle is the triangular matrix T(n,k) = (-1)^(n+k)* A085478(n,k). - Philippe Deléham, May 26 2005
Essentially the same as A050155 except with a leading diagonal A000108 (Catalan numbers) 1, 1, 2, 5, 14, 42, 132, 429, .... - Philippe Deléham, May 31 2005
Number of Grand Dyck paths of semilength n and having k downward returns to the x-axis. (A Grand Dyck path of semilength n is a path in the half-plane x>=0, starting at (0,0), ending at (2n,0) and consisting of steps u=(1,1) and d=(1,-1)). Example: T(3,2)=5 because we have u(d)uud(d),uud(d)u(d),u(d)u(d)du,u(d)duu(d) and duu(d)u(d) (the downward returns to the x-axis are shown between parentheses). - Emeric Deutsch, May 06 2006
Riordan array (c(x),x*c(x)^2) where c(x) is the g.f. of A000108; inverse array is (1/(1+x),x/(1+x)^2). - Philippe Deléham, Feb 12 2007
The triangle may also be generated from M^n*[1,0,0,0,0,0,0,0,...], where M is the infinite tridiagonal matrix with all 1's in the super and subdiagonals and [1,2,2,2,2,2,2,...] in the main diagonal. - Philippe Deléham, Feb 26 2007
Inverse binomial matrix applied to A124733. Binomial matrix applied to A089942. - Philippe Deléham, Feb 26 2007
Number of standard tableaux of shape (n+k,n-k). - Philippe Deléham, Mar 22 2007
From Philippe Deléham, Mar 30 2007: (Start)
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. (End)
The table U(n,k) = Sum_{j=0..n} T(n,j)*k^j is given in A098474. - Philippe Deléham, Mar 29 2007
Sequence read mod 2 gives A127872. - Philippe Deléham, Apr 12 2007
Number of 2n step walks from (0,0) to (2n,2k) and consisting of step u=(1,1) and d=(1,-1) and the path stays in the nonnegative quadrant. Example: T(3,0)=5 because we have uuuddd, uududd, ududud, uduudd, uuddud; T(3,1)=9 because we have uuuudd, uuuddu, uuudud, ududuu, uuduud, uduudu, uudduu, uduuud, uududu; T(3,2)=5 because we have uuuuud, uuuudu, uuuduu, uuduuu, uduuuu; T(3,3)=1 because we have uuuuuu. - Philippe Deléham, Apr 16 2007, Apr 17 2007, Apr 18 2007
Triangular matrix, read by rows, equal to the matrix inverse of triangle A129818. - Philippe Deléham, Jun 19 2007
Let Sum_{n>=0} a(n)*x^n = (1+x)/(1-mx+x^2) = o.g.f. of A_m, then Sum_{k=0..n} T(n,k)*a(k) = (m+2)^n. Related expansions of A_m are: A099493, A033999, A057078, A057077, A057079, A005408, A002878, A001834, A030221, A002315, A033890, A057080, A057081, A054320, A097783, A077416, A126866, A028230, A161591, for m=-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, respectively. - Philippe Deléham, Nov 16 2009
The Kn11, Kn12, Fi1 and Fi2 triangle sums link the triangle given above with three sequences; see the crossrefs. For the definitions of these triangle sums, see A180662. - Johannes W. Meijer, Apr 20 2011
4^n = (n-th row terms) dot (first n+1 odd integer terms). Example: 4^4 = 256 = (14, 28, 20, 7, 1) dot (1, 3, 5, 7, 9) = (14 + 84 + 100 + 49 + 9) = 256. - Gary W. Adamson, Jun 13 2011
The linear system of n equations with coefficients defined by the first n rows solve for diagonal lengths of regular polygons with N= 2n+1 edges; the constants c^0, c^1, c^2, ... are on the right hand side, where c = 2 + 2*cos(2*Pi/N). Example: take the first 4 rows relating to the 9-gon (nonagon), N = 2*4 + 1; with c = 2 + 2*cos(2*Pi/9) = 3.5320888.... The equations are (1,0,0,0) = 1; (1,1,0,0) = c; (2,3,1,0) = c^2; (5,9,5,1) = c^3. The solutions are 1, 2.53208..., 2.87938..., and 1.87938...; the four distinct diagonal lengths of the 9-gon (nonagon) with edge = 1. (Cf. comment in A089942 which uses the analogous operations but with c = 1 + 2*cos(2*Pi/9).) - Gary W. Adamson, Sep 21 2011
Also called the Lobb numbers, after Andrew Lobb, are a natural generalization of the Catalan numbers, given by L(m,n)=(2m+1)*Binomial(2n,m+n)/(m+n+1), where n >= m >= 0. For m=0, we get the n-th Catalan number. See added reference. - Jayanta Basu, Apr 30 2013
From Wolfdieter Lang, Sep 20 2013: (Start)
T(n, k) = A053121(2*n, 2*k). T(n, k) appears in the formula for the (2*n)-th power of the algebraic number rho(N):= 2*cos(Pi/N) = R(N, 2) in terms of the odd-indexed diagonal/side length ratios R(N, 2*k+1) = S(2*k, rho(N)) in the regular N-gon inscribed in the unit circle (length unit 1). S(n, x) are Chebyshev's S polynomials (see A049310):
  rho(N)^(2*n) = Sum_{k=0..n} T(n, k)*R(N, 2*k+1), n >= 0, identical in N > = 1. For a proof see the Sep 21 2013 comment under A053121. Note that this is the unreduced version if R(N, j) with j > delta(N), the degree of the algebraic number rho(N) (see A055034), appears.
  For the odd powers of rho(n) see A039598. (End)
Unsigned coefficients of polynomial numerators of Eqn. 2.1 of the Chakravarty and Kodama paper, defining the polynomials of A067311. - Tom Copeland, May 26 2016
The triangle is the Riordan square of the Catalan numbers in the sense of A321620. - Peter Luschny, Feb 14 2023

			Triangle T(n, k) begins:
  n\k     0     1     2     3     4     5    6   7   8  9
  0:      1
  1:      1     1
  2:      2     3     1
  3:      5     9     5     1
  4:     14    28    20     7     1
  5:     42    90    75    35     9     1
  6:    132   297   275   154    54    11    1
  7:    429  1001  1001   637   273    77   13   1
  8:   1430  3432  3640  2548  1260   440  104  15   1
  9:   4862 11934 13260  9996  5508  2244  663 135  17  1
  ... Reformatted by _Wolfdieter Lang_, Dec 21 2015
From _Paul Barry_, Feb 17 2011: (Start)
Production matrix begins
  1, 1,
  1, 2, 1,
  0, 1, 2, 1,
  0, 0, 1, 2, 1,
  0, 0, 0, 1, 2, 1,
  0, 0, 0, 0, 1, 2, 1,
  0, 0, 0, 0, 0, 1, 2, 1 (End)
From _Wolfdieter Lang_, Sep 20 2013: (Start)
Example for rho(N) = 2*cos(Pi/N) powers:
n=2: rho(N)^4 = 2*R(N,1) + 3*R(N,3) + 1*R(N, 5) =
  2 + 3*S(2, rho(N)) + 1*S(4, rho(N)), identical in N >= 1. For N=4 (the square with only one distinct diagonal), the degree delta(4) = 2, hence R(4, 3) and R(4, 5) can be reduced, namely to R(4, 1) = 1 and R(4, 5) = -R(4,1) = -1, respectively. Therefore, rho(4)^4 =(2*cos(Pi/4))^4 = 2 + 3 -1 = 4. (End)

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.
T. Myers and L. Shapiro, Some applications of the sequence 1, 5, 22, 93, 386, ... to Dyck paths and ordered trees, Congressus Numerant., 204 (2010), 93-104.

T. D. Noe, Rows n=0..50 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].
Quang T. Bach and Jeffrey B. Remmel, Generating functions for descents over permutations which avoid sets of consecutive patterns, arXiv:1510.04319 [math.CO], 2015 (see p.25).
M. Barnabei, F. Bonetti and M. Silimbani, Two permutation classes enumerated by the central binomial coefficients, arXiv preprint arXiv:1301.1790 [math.CO], 2013 and J. Int. Seq. 16 (2013) #13.3.8
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010), Article 10.8.2, example 15.
Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.
Paul Barry, Comparing two matrices of generalized moments defined by continued fraction expansions, arXiv preprint arXiv:1311.7161 [math.CO], 2013 and J. Int. Seq. 17 (2014) # 14.5.1.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry, Notes on the Hankel transform of linear combinations of consecutive pairs of Catalan numbers, arXiv:2011.10827 [math.CO], 2020.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 15, 29.
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 12.
Jonathan E. Beagley and Paul Drube, Combinatorics of Tableau Inversions, Electron. J. Combin., 22 (2015), #P2.44.
S. Chakravarty and Y. Kodama, A generating function for the N-soliton solutions of the Kadomtsev-Petviashvili II equation, arXiv preprint arXiv:0802.0524v2 [nlin.SI], 2008.
Wun-Seng Chou, Tian-Xiao He, and Peter J.-S. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, J. Int. Seqs., Vol. 21 (2018), #18.2.1.
Johann Cigler, Some elementary observations on Narayana polynomials and related topics, arXiv:1611.05252 [math.CO], 2016. See p. 11.
Paul Drube, Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers, arXiv:1606.04869 [math.CO], 2016.
Paul Drube, Generalized Path Pairs and Fuss-Catalan Triangles, arXiv:2007.01892 [math.CO], 2020. See Figure 4 p. 8.
T.-X. He and L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 25-41, example p 32.
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.
Thomas Koshy, Lobb's generalization of Catalan's parenthesization problem, The College Mathematics Journal 40 (2), March 2009, 99-107, DOI:10.1080/07468342.2009.11922344.
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 11.
Andrew Lobb, Deriving the n-th Catalan number, Mathematical Gazette, Vol. 83, No. 496 (March 1999), 109-110.
Donatella Merlini and Renzo Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, Discrete Mathematics 340.2 (2017): 160-174. See page 161.
Pedro J. Miana, Hideyuki Ohtsuka, and Natalia Romero, Sums of powers of Catalan triangle numbers, arXiv:1602.04347 [math.NT], 2016 (see 2.8).
A. Papoulis, A new method of inversion of the Laplace transform, Quart. Appl. Math 14 (1957), 405-414. [Annotated scan of selected pages]
Athanasios Papoulis, A new method of inversion of the Laplace transform, Quart. Appl. Math., Vol. 14, No. 4 (1957), 405-414: 124. [Note: there is a typo]
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp. 29 (129) (1975) 215-222
Yidong Sun and Fei Ma, Some new binomial sums related to the Catalan triangle, Electronic Journal of Combinatorics 21(1) (2014), #P1.33
Yidong Sun and Fei Ma, Four transformations on the Catalan triangle, arXiv preprint arXiv:1305.2017 [math.CO], 2013.
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), Table 2.2.
Wikipedia, Lobb number
W.-J. Woan, L. Shapiro and D. G. Rogers, The Catalan numbers, the Lebesgue integral and 4^{n-2}, Amer. Math. Monthly, 104 (1997), 926-931.
Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017), 3081-3091.

Columns give: A000108, A000245, A000344, A000588, A001392, A000589, A000590, A000012, A005408, A014107(n>1).
Row sums: A000984.
Triangle sums (see the comments): A000958 (Kn11), A001558 (Kn12), A088218 (Fi1, Fi2).
Cf. A008313, A039598, A084938, A000007, A067311, A321620.

/* As triangle */ [[Binomial(2*n, k+n)*(2*k+1)/(k+n+1): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 16 2015

T:=(n,k)->(2*k+1)*binomial(2*n,n-k)/(n+k+1): for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form # Emeric Deutsch, May 06 2006
T := proc(n, k) option remember; if k = n then 1 elif k > n then 0 elif k = 0 then T(n-1, 0) + T(n-1,1) else T(n-1, k-1) + 2*T(n-1, k) + T(n-1, k+1) fi end:
seq(seq(T(n, k), k = 0..n), n = 0..9) od; # Peter Luschny, Feb 14 2023

Table[Abs[Differences[Table[Binomial[2 n, n + i], {i, 0, n + 1}]]], {n, 0,7}] // Flatten (* Geoffrey Critzer, Dec 18 2011 *)
Join[{1},Flatten[Table[Binomial[2n-1,n-k]-Binomial[2n-1,n-k-2],{n,10},{k,0,n}]]] (* Harvey P. Dale, Dec 18 2011 *)
Flatten[Table[Binomial[2*n,m+n]*(2*m+1)/(m+n+1),{n,0,9},{m,0,n}]] (* Jayanta Basu, Apr 30 2013 *)

a(n, k) = (2*n+1)/(n+k+1)*binomial(2*k, n+k)
trianglerows(n) = for(x=0, n-1, for(y=0, x, print1(a(y, x), ", ")); print(""))
trianglerows(10) \\ Felix Fröhlich, Jun 24 2016

# Algorithm of L. Seidel (1877)
# Prints the first n rows of the triangle
def A039599_triangle(n) :
    D = [0]*(n+2); D[1] = 1
    b = True ; h = 1
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        if b : print([D[z] for z in (1..h-1)])
        b = not b
A039599_triangle(10)  # Peter Luschny, May 01 2012

T(n,k) = C(2*n-1, n-k) - C(2*n-1, n-k-2), n >= 1, T(0,0) = 1.
From Emeric Deutsch, May 06 2006: (Start)
T(n,k) = (2*k+1)*binomial(2*n,n-k)/(n+k+1).
G.f.: G(t,z)=1/(1-(1+t)*z*C), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function. (End)
The following formulas were added by Philippe Deléham during 2003 to 2009: (Start)
Triangle T(n, k) read by rows; given by A000012 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
T(n, k) = C(2*n, n-k)*(2*k+1)/(n+k+1). Sum(k>=0; T(n, k)*T(m, k) = A000108(n+m)); A000108: numbers of Catalan.
T(n, 0) = A000108(n); T(n, k) = 0 if k>n; for k>0, T(n, k) = Sum_{j=1..n} T(n-j, k-1)*A000108(j).
T(n, k) = A009766(n+k, n-k) = A033184(n+k+1, 2k+1).
G.f. for column k: Sum_{n>=0} T(n, k)*x^n = x^k*C(x)^(2*k+1) where C(x) = Sum_{n>=0} A000108(n)*x^n is g.f. for Catalan numbers, A000108.
T(0, 0) = 1, T(n, k) = 0 if n<0 or n=1, T(n, k) = T(n-1, k-1) + 2*T(n-1, k) + T(n-1, k+1).
a(n) + a(n+1) = 1 + A000108(m+1) if n = m*(m+3)/2; a(n) + a(n+1) = A039598(n) otherwise.
T(n, k) = A050165(n, n-k).
Sum_{j>=0} T(n-k, j)*A039598(k, j) = A028364(n, k).
Matrix inverse of the triangle T(n, k) = (-1)^(n+k)*binomial(n+k, 2*k) = (-1)^(n+k)*A085478(n, k).
Sum_{k=0..n} T(n, k)*x^k = A000108(n), A000984(n), A007854(n), A076035(n), A076036(n) for x = 0, 1, 2, 3, 4.
Sum_{k=0..n} (2*k+1)*T(n, k) = 4^n.
T(n, k)*(-2)^(n-k) = A114193(n, k).
Sum_{k>=h} T(n,k) = binomial(2n,n-h).
Sum_{k=0..n} T(n,k)*5^k = A127628(n).
Sum_{k=0..n} T(n,k)*7^k = A115970(n).
T(n,k) = Sum_{j=0..n-k} A106566(n+k,2*k+j).
Sum_{k=0..n} T(n,k)*6^k = A126694(n).
Sum_{k=0..n} T(n,k)*A000108(k) = A007852(n+1).
Sum_{k=0..floor(n/2)} T(n-k,k) = A000958(n+1).
Sum_{k=0..n} T(n,k)*(-1)^k = A000007(n).
Sum_{k=0..n} T(n,k)*(-2)^k = (-1)^n*A064310(n).
T(2*n,n) = A126596(n).
Sum_{k=0..n} T(n,k)*(-x)^k = A000007(n), A126983(n), A126984(n), A126982(n), A126986(n), A126987(n), A127017(n), A127016(n), A126985(n), A127053(n) for x=1,2,3,4,5,6,7,8,9,10 respectively.
Sum_{j>=0} T(n,j)*binomial(j,k) = A116395(n,k).
T(n,k) = Sum_{j>=0} A106566(n,j)*binomial(j,k).
T(n,k) = Sum_{j>=0} A127543(n,j)*A038207(j,k).
Sum_{k=0..floor(n/2)} T(n-k,k)*A000108(k) = A101490(n+1).
T(n,k) = A053121(2*n,2*k).
Sum_{k=0..n} T(n,k)*sin((2*k+1)*x) = sin(x)*(2*cos(x))^(2*n).
T(n,n-k) = Sum_{j>=0} (-1)^(n-j)*A094385(n,j)*binomial(j,k).
Sum_{j>=0} A110506(n,j)*binomial(j,k) = Sum_{j>=0} A110510(n,j)*A038207(j,k) = T(n,k)*2^(n-k).
Sum_{j>=0} A110518(n,j)*A027465(j,k) = Sum_{j>=0} A110519(n,j)*A038207(j,k) = T(n,k)*3^(n-k).
Sum_{k=0..n} T(n,k)*A001045(k) = A049027(n), for n>=1.
Sum_{k=0..n} T(n,k)*a(k) = (m+2)^n if Sum_{k>=0} a(k)*x^k = (1+x)/(x^2-m*x+1).
Sum_{k=0..n} T(n,k)*A040000(k) = A001700(n).
Sum_{k=0..n} T(n,k)*A122553(k) = A051924(n+1).
Sum_{k=0..n} T(n,k)*A123932(k) = A051944(n).
Sum_{k=0..n} T(n,k)*k^2 = A000531(n), for n>=1.
Sum_{k=0..n} T(n,k)*A000217(k) = A002457(n-1), for n>=1.
Sum{j>=0} binomial(n,j)*T(j,k)= A124733(n,k).
Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A000984(n), A089022(n), A035610(n), A130976(n), A130977(n), A130978(n), A130979(n), A130980(n), A131521(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively.
Sum_{k=0..n} T(n,k)*A005043(k) = A127632(n).
Sum_{k=0..n} T(n,k)*A132262(k) = A089022(n).
T(n,k) + T(n,k+1) = A039598(n,k).
T(n,k) = A128899(n,k)+A128899(n,k+1).
Sum_{k=0..n} T(n,k)*A015518(k) = A076025(n), for n>=1. Also Sum_{k=0..n} T(n,k)*A015521(k) = A076026(n), for n>=1.
Sum_{k=0..n} T(n,k)*(-1)^k*x^(n-k) = A033999(n), A000007(n), A064062(n), A110520(n), A132863(n), A132864(n), A132865(n), A132866(n), A132867(n), A132869(n), A132897(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 respectively.
Sum_{k=0..n} T(n,k)*(-1)^(k+1)*A000045(k) = A109262(n), A000045:= Fibonacci numbers.
Sum_{k=0..n} T(n,k)*A000035(k)*A016116(k) = A143464(n).
Sum_{k=0..n} T(n,k)*A016116(k) = A101850(n).
Sum_{k=0..n} T(n,k)*A010684(k) = A100320(n).
Sum_{k=0..n} T(n,k)*A000034(k) = A029651(n).
Sum_{k=0..n} T(n,k)*A010686(k) = A144706(n).
Sum_{k=0..n} T(n,k)*A006130(k-1) = A143646(n), with A006130(-1)=0.
T(n,2*k)+T(n,2*k+1) = A118919(n,k).
Sum_{k=0..j} T(n,k) = A050157(n,j).
Sum_{k=0..2} T(n,k) = A026012(n); Sum_{k=0..3} T(n,k)=A026029(n).
Sum_{k=0..n} T(n,k)*A000045(k+2) = A026671(n).
Sum_{k=0..n} T(n,k)*A000045(k+1) = A026726(n).
Sum_{k=0..n} T(n,k)*A057078(k) = A000012(n).
Sum_{k=0..n} T(n,k)*A108411(k) = A155084(n).
Sum_{k=0..n} T(n,k)*A057077(k) = 2^n = A000079(n).
Sum_{k=0..n} T(n,k)*A057079(k) = 3^n = A000244(n).
Sum_{k=0..n} T(n,k)*(-1)^k*A011782(k) = A000957(n+1).
(End)
T(n,k) = Sum_{j=0..k} binomial(k+j,2j)*(-1)^(k-j)*A000108(n+j). - Paul Barry, Feb 17 2011
Sum_{k=0..n} T(n,k)*A071679(k+1) = A026674(n+1). - Philippe Deléham, Feb 01 2014
Sum_{k=0..n} T(n,k)*(2*k+1)^2 = (4*n+1)*binomial(2*n,n). - Werner Schulte, Jul 22 2015
Sum_{k=0..n} T(n,k)*(2*k+1)^3 = (6*n+1)*4^n. - Werner Schulte, Jul 22 2015
Sum_{k=0..n} (-1)^k*T(n,k)*(2*k+1)^(2*m) = 0 for 0 <= m < n (see also A160562). - Werner Schulte, Dec 03 2015
T(n,k) = GegenbauerC(n-k,-n+1,-1) - GegenbauerC(n-k-1,-n+1,-1). - Peter Luschny, May 13 2016
T(n,n-2) = A014107(n). - R. J. Mathar, Jan 30 2019
T(n,n-3) = n*(2*n-1)*(2*n-5)/3. - R. J. Mathar, Jan 30 2019
T(n,n-4) = n*(n-1)*(2*n-1)*(2*n-7)/6. - R. J. Mathar, Jan 30 2019
T(n,n-5) = n*(n-1)*(2*n-1)*(2*n-3)*(2*n-9)/30. - R. J. Mathar, Jan 30 2019

Corrected by Philippe Deléham, Nov 26 2009, Dec 14 2009

A009766 Catalan's triangle T(n,k) (read by rows): each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0..k} T(n-1,j).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 5, 1, 4, 9, 14, 14, 1, 5, 14, 28, 42, 42, 1, 6, 20, 48, 90, 132, 132, 1, 7, 27, 75, 165, 297, 429, 429, 1, 8, 35, 110, 275, 572, 1001, 1430, 1430, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 4862, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934

Offset: 0

Wouter Meeussen

The entries in this triangle (in its many forms) are often called ballot numbers.
T(n,k) = number of standard tableaux of shape (n,k) (n > 0, 0 <= k <= n). Example: T(3,1) = 3 because we have 134/2, 124/3 and 123/4. - Emeric Deutsch, May 18 2004
T(n,k) is the number of full binary trees with n+1 internal nodes and jump-length k. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given ordered tree is called the jump-length. - Emeric Deutsch, Jan 18 2007
The k-th diagonal from the right (k=1, 2, ...) gives the sequence obtained by asking in how many ways can we toss a fair coin until we first get k more heads than tails. The k-th diagonal has formula k(2m+k-1)!/(m!(m+k)!) and g.f. (C(x))^k where C(x) is the generating function for the Catalan numbers, (1-sqrt(1-4*x))/(2*x). - Anthony C Robin, Jul 12 2007
T(n,k) is also the number of order-decreasing and order-preserving full transformations (of an n-element chain) of waist k (waist (alpha) = max(Im(alpha))). - Abdullahi Umar, Aug 25 2008
Formatted as an upper right triangle (see tables) a(c,r) is the number of different triangulated planar polygons with c+2 vertices, with triangle degree c-r+1 for the same vertex X (c=column number, r=row number, with c >= r >= 1). - Patrick Labarque, Jul 28 2010
The triangle sums, see A180662 for their definitions, link Catalan's triangle, its mirror is A033184, with several sequences, see crossrefs. - Johannes W. Meijer, Sep 22 2010
The m-th row of Catalan's triangle consists of the unique nonnegative differences of the form binomial(m+k,m)-binomial(m+k,m+1) with 0 <= k <= m (See Links). - R. J. Cano, Jul 22 2014
T(n,k) is also the number of nondecreasing parking functions of length n+1 whose maximum element is k+1. For example T(3,2) = 5 because we have (1,1,1,3), (1,1,2,3), (1,2,2,3), (1,1,3,3), (1,2,3,3). - Ran Pan, Nov 16 2015
T(n,k) is the number of Dyck paths from (0,0) to (n+2,n+2) which start with n-k+2 east steps and touch the diagonal y=x only on the last north step. - Felipe Rueda, Sep 18 2019
T(n-1,k) for k < n is number of well-formed strings of n parenthesis pairs with prefix of exactly n-k opening parenthesis; T(n,n) = T(n,n-1). - Hermann Stamm-Wilbrandt, May 02 2021

			Triangle begins in row n=0 with 0 <= k <= n:
  1;
  1, 1;
  1, 2,  2;
  1, 3,  5,   5;
  1, 4,  9,  14,  14;
  1, 5, 14,  28,  42,   42;
  1, 6, 20,  48,  90,  132,  132;
  1, 7, 27,  75, 165,  297,  429,  429;
  1, 8, 35, 110, 275,  572, 1001, 1430, 1430;
  1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 4862;

William Feller, Introduction to Probability Theory and its Applications, vol. I, ed. 2, chap. 3, sect. 1,2.
Ki Hang Kim, Douglas G. Rogers, and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013).
D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6, Eq. 22, p. 451.
C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146.
M. Bellon, Query 5467, L'Intermédiaire des Mathématiciens, 4 (1925), 11; H. Ory, 4 (1925), 120. - N. J. A. Sloane, Mar 09 2022
Andrzej Proskurowski and Ekaputra Laiman, Fast enumeration, ranking, and unranking of binary trees. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982). Congr. Numer. 35 (1982), 401-413.MR0725898 (85a:68152).
M. Welsch, Note #371, L'Intermédiaire des Mathématiciens, 2 (1895), pp. 235-237. - N. J. A. Sloane, Mar 02 2022

T. D. Noe, Rows n = 0..100 of triangle, flattened
Erik Aas, Arvind Ayyer, Svante Linusson and Samu Potka, The exact phase diagram for a semipermeable TASEP with nonlocal boundary jumps, arXiv:1902.02019 [cond-mat.stat-mech], 2019.
Ron M. Adin, E. Bagno, and Y. Roichman, Block decomposition of permutations and Schur-positivity, arXiv:1611.06979 [math.CO], 2016-2017.
Kassie Archer, Abigail Bishop, Alexander Diaz-Lopez, Luis David Garcia Puente, Darren Glass, and Joel Louwsma, Arithmetical structures on bidents, arXiv:1903.01393 [math.CO], 2019.
J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles, arXiv:math/0109108 [math.NT], 2001.
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906 [math.CO], 2007.
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, Discrete Math., 308 (2008), 4660-4669.
Axel Bacher, Antonio Bernini, Luca Ferrari, Benjamin Gunby, Renzo Pinzani, and Julian West, The Dyck pattern poset Discrete Math. 321 (2014), 12--23. MR3154009.
D. F. Bailey, Counting arrangements of 1's and-1's, Mathematics Magazine, 69 (1996): 128-131. See table on p. 129.
Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and Renzo Pinzani, A methodology for plane tree enumeration, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). Discrete Math. 180 (1998), no. 1-3, 45--64. MR1603693 (98m:05090).
E. Barcucci and M. C. Verri, Some more properties of Catalan numbers, Discrete Math., 102 (1992), 229-237.
J.-L. Baril, C. Khalil, and V. Vajnovszki, Catalan and Schröder permutations sortable by two restricted stacks, arXiv:2004.01812 [cs.DM], 2020.
Paul Barry, Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms, J. Int. Seq. 14 (2011) # 11.2.2, example 3.
Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
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.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
A. Bernini, L. Ferrari, R. Pinzani, and J. West, The Dyck pattern poset, arXiv:1303.3785 [math.CO], 2013.
N. Borie, Combinatorics of simple marked mesh patterns in 132-avoiding permutations, arXiv:1311.6292 [math.CO], 2013.
M. Bousquet-Mélou and M. Petkovsek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (2000), 51-75.
Jasper Bown, Peter Kagey, Alan Kappler, Michael E. Orrison, and Jayden Thadani, Preference-restricted parking functions, arXiv:2507.11701 [math.CO], 2025. See p. 11.
Benjamin Braun, Hugo Corrales, Scott Corry, Luis David García Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, Gregg Musiker, and Carlos E. Valencia, Counting Arithmetical Structures on Paths and Cycles. arXiv:1701.06377 [math.CO], 2017.
E. H. M. Brietzke, An identity of Andrews and a new method for the Riordan array proof of combinatorial identities, Discrete Math., 308 (2008), 4246-4262.
S. Brlek, E. Duchi, E. Pergola, and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
Hong Duc Bui, Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials, arXiv:2504.09615 [cs.CG], 2025. See p. 4.
Steve Butler, R. Graham, and C. H. Yan, Parking distributions on trees, European Journal of Combinatorics 65 (2017), 168-185.
R. J. Cano, Catalan's books
L. Carlitz, Sequences, paths, ballot numbers
Douglas M. Chen, On the Structure of Permutation Invariant Parking, arXiv:2311.15699 [math.CO], 2023. See p. 16.
Lapo Cioni and Luca Ferrari, Preimages under the Queuesort algorithm, arXiv preprint arXiv:2102.07628 [math.CO], 2021; Discrete Math., 344 (2021), #112561.
Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, On some discrete statistics of parking functions, arXiv:2312.16786 [math.CO], 2023.
Italo J. Dejter, A new approach to the middle levels via a Catalan-number system of numeration, 2015.
Italo J. Dejter, A numeral system for the middle levels, preprint, 2014. [See Section 2. - _N. J. A. Sloane_, Apr 06 2014]
Italo J. Dejter, Dihedral-symmetry middle-levels problem via a Catalan system of numeration, preprint, 2015.
Italo J. Dejter, The role of restricted growth strings in the two middle levels of the Boolean lattice B_(2k+1), University of Puerto Rico, 2018.
Italo J. Dejter, Reinterpreting Mütze's Theorem via Natural Enumeration of Ordered Rooted Trees, arXiv:1911.02100 [math.CO], 2019.
Italo J. Dejter, A numeral system for the middle-levels graphs, Elec. J. Graph Theory and Applications (2021) Vol. 9, No. 1, 137-156. See p. 139.
B. Derrida, E. Domany, and D. Mukamel, An exact solution of a one-dimensional asymmetric exclusion model with open boundaries, J. Stat. Phys. 69, 1992, 667-687; eqs. (20), (21), p. 672. (Y_{N}(K) = A009766(N+1,K-1), 1 <= K <= N+1, N >=0 if alpha = 1 = beta).
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Filippo Disanto, Some Statistics on the Hypercubes of Catalan Permutations, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.
Paul Drube, Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers, arXiv:1606.04869 [math.CO], 2016.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Classification of uniform flag triangulations of the Legendre polytope, arXiv:1901.07113 [math.CO], 2019.
R. Ehrenborg, S. Kitaev, and E. Steingrimsson, Number of cycles in the graph of 312-avoiding permutations, arXiv:1310.1520 [math.CO], 2013.
W. J. R. Eplett, A note about the Catalan triangle, Discrete Math. 25(1979), no. 3, 289--291. MR0534947 (80i:05007)
Jackson Evoniuk, Steven Klee, and Van Magnan, Enumerating Minimal Length Lattice Paths, J. Int. Seq., Vol. 21 (2018), Article 18.3.6.
G. Feinberg and K.-H. Lee, Homogeneous representations of KLR-algebras and fully commutative elements, arXiv:1401.0845 [math.RT], 2014.
I. Fanti, A. Frosini, E. Grazzini, R. Pinzani, and S. Rinaldi, Characterization and enumeration of some classes of permutominoes, PU. M. A., Vol. 18 (2007), No. 3-4, pp. 265-290.
Dominique Foata and Guo-Niu Han, The doubloon polynomial triangle, Ram. J. 23 (2010), 107-126.
Dominique Foata and Guo-Niu Han, Doubloons and new q-tangent numbers, Quart. J. Math. 62 (2) (2011) 417-432.
H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.
C. A. Francisco, J. Mermin, and J. Schweig, Catalan numbers, binary trees, and pointed pseudotriangulations, preprint 2013; European Journal of Combinatorics, Volume 45, April 2015, Pages 85-96.
Shishuo Fu, Zhicong Lin, and Yaling Wang, A combinatorial bijection on di-sk trees, arXiv:2011.11302 [math.CO], 2020.
Ling Gao, Graph assembly for spider and tadpole graphs, Master's Thesis, Cal. State Poly. Univ. (2023). See p. 12.
Ira Gessel, Super ballot numbers.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Claude Godrèche and Jean-Marc Luck, On the first positive position of a random walker, arXiv:2501.17268 [cond-mat.stat-mech], 2025.
Niket Gowravaram, A Variation of the nil-Temperley-Lieb algebras of type A, Preprint, 2015.
J. M. Hammersley, An undergraduate exercise in manipulation, Math. Scientist, 14 (1989), 1-23.
J. M. Hammersley, An undergraduate exercise in manipulation, Math. Scientist, 14 (1989), 1-23. (Annotated scanned copy)
Pamela E. Harris, Thiago Holleben, J. Carlos Martínez Mori, Amanda Priestley, Keith Sullivan, and Per Wagenius, A Probabilistic Parking Process and Labeled IDLA, arXiv:2501.11718 [math.PR], 2025. See pp. 8, 28.
David He and Daniel Tubbenhauer, Tensor powers of representations of (diagram) monoids, arXiv:2508.04054 [math.RT], 2025. See p. 7.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
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.
F. Hivert, J.-C. Novelli, and J.-Y. Thibon, The Algebra of Binary Search Trees, Theoretical Computer Science, 339 (2005), 129-165.
R. L. Hudson and Y. Pei, On a causal quantum stochastic double product integral related to Lévy area, Research Gate, 2015.
R. L. Hudson and Y. Pei, On a quantum causal stochastic double product integral related to Levy area, arXiv:1506.04294 [math-ph], 2015.
Brant Jones, Avoiding patterns and making the best choice, arXiv:1812.00963 [math.CO], 2018.
Cemil Karaçam and Alper Vural, Enumerating 2D and 3D lattice paths with arbitrary steps, Mathematica Bohemica, pp. 1-13 (2025). See p. 12.
Antii Karttunen, Some notes on Catalan's Triangle.
Lord C. Kavi and Michael W. Newman, Counting closed walks in infinite regular trees using Catalan and Borel's triangles, arXiv:2212.08795 [math.CO], 2022.
Dongsu Kim and Zhicong Lin, Refined restricted inversion sequences, arXiv:1706.07208 [math.CO], 2017.
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146. [Annotated scanned copy]
A. Laradji and A. Umar, On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.
Jeong-Yup Lee, Dong-il Lee, and Sungsoon Kim, Gröbner-Shirshov bases for Temperley-Lieb algebras of the complex reflection group of type G(d,1,n), arXiv:1808.06523 [math.RA], 2018.
Kyu-Hwan Lee and Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
Shao-Hua Liu, The operators F_i on permutations, 132-avoiding permutations and inversions, Discrete Math., 342 (2019), 2402-2414.
Jiaxi Lu and Yuanzhe Ding, A skeleton model to enumerate standard puzzle sequences, arXiv:2106.09471 [math.CO], 2021.
D. Merlini et al., Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math., 91 (1999), 197-213.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table I).
Andrew Misseldine, Counting Schur Rings over Cyclic Groups, arXiv:1508.03757 [math.RA], 2015.
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.
M. A. A. Obaid, S. K. Nauman, W. M. Fakieh, and C. M. Ringel, The numbers of support-tilting modules for a Dynkin algebra, 2014 and J. Int. Seq. 18 (2015) 15.10.6.
P. Pagacz and M. Wojtylak, On the spectral properties of a class of H-selfadjoint random matrices and the underlying combinatorics, arXiv:1310.2122 [math.PR], 2013.
R. Parviainen, Permutations, cycles and the pattern 2-13, arXiv:math/0607793 [math.CO], 2006.
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 261
Planet Math, Lattice Paths and ballot numbers.
L. Pudwell, Avoiding an Ordered Partition of Length 3, 2013.
C. M. Ringel, The Catalan combinatorics of the hereditary artin algebras, arXiv:1502.06553 [math.RT], 2015.
Gabriel Bravo Rios and Agustin Moreno Cañadas, Dyck Paths in Representation Theory of Algebras, National University of Colombia (2020).
A. Robertson, D. Saracino, and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
L. W. Shapiro, A Catalan triangle, Discrete Math., 14, 83-90, 1976.
T. Sillke, Catalan's numbers
Hermann Stamm-Wilbrandt, Visualization for all well-formed strings of 4 parenthesis pairs and relation to T(n,k).
R. A. Sulanke, Guessing, ballot numbers and refining Pascal's triangle
Yidong Sun, A simple bijection between binary trees and colored ternary trees, El. J. Combinat. 17 (2010) #N20
Paweł J. Szabłowski, Yet another way of calculating moments of the Kesten's distribution and its consequences, arXiv:2106.10461 [math.CO], 2021.
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See pp. 9, 29.
Rafael Vazquez and M. Krstic, Boundary control of a singular reaction-diffusion equation on a disk, arXiv:1601.02010 [math.OC], 2016.
Luis Verde-Star, A Matrix Approach to Generalized Delannoy and Schröder Arrays, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.
Eric Weisstein's World of Mathematics, Catalan's Triangle
Eric Weisstein's World of Mathematics, Nonnegative Partial Sum
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 17.
Martha Yip, Rook Placements and Jordan Forms of Upper-Triangular Nilpotent Matrices, arXiv:1703.00057 [math.CO], 2017; The Electronic Journal of Combinatorics 25(1) (2018), #P1.68.

The following are all versions of (essentially) the same Catalan triangle: A009766, A008315, A028364, A030237, A047072, A053121, A059365, A062103, A099039, A106566, A130020, A140344.
Cf. A062745, A214292.
Sums of the shallow diagonals give A001405, central binomial coefficients: 1=1, 1=1, 1+1=2, 1+2=3, 1+3+2=6, 1+4+5=10, 1+5+9+5=20, ...
Row sums as well as the sums of the squares of the shallow diagonals give Catalan numbers (A000108).
Reflected version of A033184.
Diagonals give A000108, A000108, A000245, A002057, A000344, A003517, A000588, A003518, A003519, A001392, ...
Triangle sums (see the comments): A000108 (Row1), A000957 (Row2), A001405 (Kn11), A014495 (Kn12), A194124 (Kn13), A030238 (Kn21), A000984 (Kn4), A000958 (Fi2), A165407 (Ca1), A026726 (Ca4), A081696 (Ze2).

Flat(List([0..10],n->List([0..n],m->Binomial(n+m,n)*(n-m+1)/(n+1)))); # Muniru A Asiru, Feb 18 2018

a009766 n k = a009766_tabl !! n !! k
a009766_row n = a009766_tabl !! n
a009766_tabl = iterate (\row -> scanl1 (+) (row ++ [0])) [1]
-- Reinhard Zumkeller, Jul 12 2012

[[Binomial(n+k,n)*(n-k+1)/(n+1): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Mar 07 2019

A009766 := proc(n,k) binomial(n+k,n)*(n-k+1)/(n+1); end proc:
seq(seq(A009766(n,k), k=0..n), n=0..10); # R. J. Mathar, Dec 03 2010

Flatten[NestList[Append[Accumulate[#], Last[Accumulate[#]]] &, {1}, 9]] (* Birkas Gyorgy, May 19 2012 *)
T[n_, k_] := T[n, k] = Which[k == 0, 1, k>n, 0, True, T[n-1, k] + T[n, k-1] ]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 07 2016 *)

{T(n, k) = if( k<0 || k>n, 0, binomial(n+1+k, k) * (n+1-k) / (n+1+k) )}; /* Michael Somos, Oct 17 2006 */

b009766=(n1=0,n2=100)->{my(q=if(!n1,0,binomial(n1+1,2)));for(w=n1,n2,for(k=0,w,write("b009766.txt",1*q" "1*(binomial(w+k,w)-binomial(w+k,w+1)));q++))} \\ R. J. Cano, Jul 22 2014

from math import comb, isqrt
def A009766(n): return comb((a:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)))+(b:=n-comb(a+1,2)),b)*(a-b+1)//(a+1) # Chai Wah Wu, Nov 12 2024

@CachedFunction
def ballot(p,q):
    if p == 0 and q == 0: return 1
    if p < 0 or p > q: return 0
    S = ballot(p-2, q) + ballot(p, q-2)
    if q % 2 == 1: S += ballot(p-1, q-1)
    return S
A009766 = lambda n, k: ballot(2*k, 2*n)
for n in (0..7): [A009766(n, k) for k in (0..n)]  # Peter Luschny, Mar 05 2014

[[binomial(n+k,n)*(n-k+1)/(n+1) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Mar 07 2019

T(n, m) = binomial(n+m, n)*(n-m+1)/(n+1), 0 <= m <= n.
G.f. for column m: (x^m)*N(2; m-1, x)/(1-x)^(m+1), m >= 0, with the row polynomials from triangle A062991 and N(2; -1, x) := 1.
G.f.: C(t*x)/(1-x*C(t*x)) = 1 + (1+t)*x + (1+2*t+2*t^2)*x^2 + ..., where C(x) = (1-sqrt(1-4*x))/(2*x) is the Catalan function. - Emeric Deutsch, May 18 2004
Another version of triangle T(n, k) given by [1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 1, 1, 1, 1, 1, ...] = 1; 1, 0; 1, 1, 0; 1, 2, 2, 0; 1, 3, 5, 5, 0; 1, 4, 9, 14, 14, 0; ... where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 16 2005
O.g.f. (with offset 1) is the series reversion of x*(1+x*(1-t))/(1+x)^2 = x - x^2*(1+t) + x^3*(1+2*t) - x^4*(1+3*t) + ... . - Peter Bala, Jul 15 2012
Sum_{k=0..floor(n/2)} T(n-k+p-1, k+p-1) = A001405(n+2*p-2) - C(n+2*p-2, p-2), p >= 1. - Johannes W. Meijer, Oct 03 2013
Let A(x,t) denote the o.g.f. Then 1 + x*d/dx(A(x,t))/A(x,t) = 1 + (1 + t)*x + (1 + 2*t + 3*t^2)*x^2 + (1 + 3*t + 6*t^2 + 10*t^3)*x^3 + ... is the o.g.f. for A059481. - Peter Bala, Jul 21 2015
The n-th row polynomial equals the n-th degree Taylor polynomial of the function (1 - 2*x)/(1 - x)^(n+2) about 0. For example, for n = 4, (1 - 2*x)/(1 - x)^6 = 1 + 4*x + 9*x^2 + 14*x^3 + 14*x^4 + O(x^5). - Peter Bala, Feb 18 2018
T(n,k) = binomial(n + k + 1, k) - 2*binomial(n + k, k - 1), for 0 <= k <= n. - David Callan, Jun 15 2022

A106566 Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 1, 1, 1, 1, 1, 1, 1, ... ] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ... ] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 5, 3, 1, 0, 14, 14, 9, 4, 1, 0, 42, 42, 28, 14, 5, 1, 0, 132, 132, 90, 48, 20, 6, 1, 0, 429, 429, 297, 165, 75, 27, 7, 1, 0, 1430, 1430, 1001, 572, 275, 110, 35, 8, 1, 0, 4862, 4862, 3432, 2002, 1001, 429, 154, 44, 9, 1

Offset: 0

Philippe Deléham, May 30 2005

Catalan convolution triangle; g.f. for column k: (x*c(x))^k with c(x) g.f. for A000108 (Catalan numbers).
Riordan array (1, xc(x)), where c(x) the g.f. of A000108; inverse of Riordan array (1, x*(1-x)) (see A109466).
Diagonal sums give A132364. - Philippe Deléham, Nov 11 2007

			Triangle begins:
  1;
  0,   1;
  0,   1,   1;
  0,   2,   2,  1;
  0,   5,   5,  3,  1;
  0,  14,  14,  9,  4,  1;
  0,  42,  42, 28, 14,  5, 1;
  0, 132, 132, 90, 48, 20, 6, 1;
From _Paul Barry_, Sep 28 2009: (Start)
Production array is
  0, 1,
  0, 1, 1,
  0, 1, 1, 1,
  0, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1 (End)

Alois P. Heinz, Rows n = 0..140, flattened
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
D. Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
FindStat - Combinatorial Statistic Finder, The number of touch points of a Dyck path, The number of initial rises of a Dyck paths, The number of nodes on the left branch of the tree, The number of subtrees.
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
L. W. Shapiro, S. Getu, W.-J. Woan and L. C. Woodson, The Riordan group, Discrete Applied Math., 34 (1991), 229-239.

Column k for k = 0, 1, 2, ..., 13: A000007, A000108, A000108, A000245, A002057, A000344, A003517, A000588, A003517, A001392, A003518, A000589, A003519, A000590
The three triangles A059365, A106566 and A099039 are the same except for signs and the leading term.
Diagonals: A000012, A001477, A000096, A005586, A005587, A005557, A064059, A064061
See also A009766, A033184, A059365 for other versions.
Generalized Catalan numbers C(x, n) for -11 <= x <= 10: A064333, A064332, A064331, A064330, A064329, A064328, A064327, A064326, A064325, A064311, A064310, A000012, A000108, A064062, A064063, A064087, A064088, A064089, A064090, A064091, A064092, A064093.
The following are all versions of (essentially) the same Catalan triangle: A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Diagonals give A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392, ...

A106566:= func< n,k | n eq 0 select 1 else (k/n)*Binomial(2*n-k-1, n-k) >;
[A106566(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 06 2021

A106566 := proc(n,k)
    if n = 0 then
        1;
    elif k < 0 or k > n then
        0;
    else
        binomial(2*n-k-1,n-k)*k/n ;
    end if;
end proc: # R. J. Mathar, Mar 01 2015

T[n_, k_] := Binomial[2n-k-1, n-k]*k/n; T[0, 0] = 1; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 18 2017 *)
(* The function RiordanArray is defined in A256893. *)
RiordanArray[1&, #(1-Sqrt[1-4#])/(2#)&, 11] // Flatten (* Jean-François Alcover, Jul 16 2019 *)

{T(n, k) = if( k<=0 || k>n, n==0 && k==0, binomial(2*n - k, n) * k/(2*n - k))}; /* Michael Somos, Oct 01 2022 */

def A106566(n, k): return 1 if (n==0) else (k/n)*binomial(2*n-k-1, n-k)
flatten([[A106566(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Sep 06 2021

T(n, k) = binomial(2n-k-1, n-k)*k/n for 0 <= k <= n with n > 0; T(0, 0) = 1; T(0, k) = 0 if k > 0.
T(0, 0) = 1; T(n, 0) = 0 if n > 0; T(0, k) = 0 if k > 0; for k > 0 and n > 0: T(n, k) = Sum_{j>=0} T(n-1, k-1+j).
Sum_{j>=0} T(n+j, 2j) = binomial(2n-1, n), n > 0.
Sum_{j>=0} T(n+j, 2j+1) = binomial(2n-2, n-1), n > 0.
Sum_{k>=0} (-1)^(n+k)*T(n, k) = A064310(n). T(n, k) = (-1)^(n+k)*A099039(n, k).
Sum_{k=0..n} T(n, k)*x^k = A000007(n), A000108(n), A000984(n), A007854(n), A076035(n), A076036(n), A127628(n), A126694(n), A115970(n) for x = 0,1,2,3,4,5,6,7,8 respectively.
Sum_{k>=0} T(n, k)*x^(n-k) = C(x, n); C(x, n) are the generalized Catalan numbers.
Sum_{j=0..n-k} T(n+k,2*k+j) = A039599(n,k).
Sum_{j>=0} T(n,j)*binomial(j,k) = A039599(n,k).
Sum_{k=0..n} T(n,k)*A000108(k) = A127632(n).
Sum_{k=0..n} T(n,k)*(x+1)^k*x^(n-k) = A000012(n), A000984(n), A089022(n), A035610(n), A130976(n), A130977(n), A130978(n), A130979(n), A130980(n), A131521(n) for x= 0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Aug 25 2007
Sum_{k=0..n} T(n,k)*A000108(k-1) = A121988(n), with A000108(-1)=0. - Philippe Deléham, Aug 27 2007
Sum_{k=0..n} T(n,k)*(-x)^k = A000007(n), A126983(n), A126984(n), A126982(n), A126986(n), A126987(n), A127017(n), A127016(n), A126985(n), A127053(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Oct 27 2007
T(n,k)*2^(n-k) = A110510(n,k); T(n,k)*3^(n-k) = A110518(n,k). - Philippe Deléham, Nov 11 2007
Sum_{k=0..n} T(n,k)*A000045(k) = A109262(n), A000045: Fibonacci numbers. - Philippe Deléham, Oct 28 2008
Sum_{k=0..n} T(n,k)*A000129(k) = A143464(n), A000129: Pell numbers. - Philippe Deléham, Oct 28 2008
Sum_{k=0..n} T(n,k)*A100335(k) = A002450(n). - Philippe Deléham, Oct 30 2008
Sum_{k=0..n} T(n,k)*A100334(k) = A001906(n). - Philippe Deléham, Oct 30 2008
Sum_{k=0..n} T(n,k)*A099322(k) = A015565(n). - Philippe Deléham, Oct 30 2008
Sum_{k=0..n} T(n,k)*A106233(k) = A003462(n). - Philippe Deléham, Oct 30 2008
Sum_{k=0..n} T(n,k)*A151821(k+1) = A100320(n). - Philippe Deléham, Oct 30 2008
Sum_{k=0..n} T(n,k)*A082505(k+1) = A144706(n). - Philippe Deléham, Oct 30 2008
Sum_{k=0..n} T(n,k)*A000045(2k+2) = A026671(n). - Philippe Deléham, Feb 11 2009
Sum_{k=0..n} T(n,k)*A122367(k) = A026726(n). - Philippe Deléham, Feb 11 2009
Sum_{k=0..n} T(n,k)*A008619(k) = A000958(n+1). - Philippe Deléham, Nov 15 2009
Sum_{k=0..n} T(n,k)*A027941(k+1) = A026674(n+1). - Philippe Deléham, Feb 01 2014
G.f.: Sum_{n>=0, k>=0} T(n, k)*x^k*z^n = 1/(1 - x*z*c(z)) where c(z) the g.f. of A000108. - Michael Somos, Oct 01 2022

Formula corrected by Philippe Deléham, Oct 31 2008
Corrected by Philippe Deléham, Sep 17 2009
Corrected by Alois P. Heinz, Aug 02 2012

A236830 Riordan array (1/(1-xC(x)^3), xC(x)), C(x) the g.f. of A000108.

Original entry on oeis.org

1, 1, 1, 4, 2, 1, 16, 7, 3, 1, 65, 27, 11, 4, 1, 267, 108, 43, 16, 5, 1, 1105, 440, 173, 65, 22, 6, 1, 4597, 1812, 707, 267, 94, 29, 7, 1, 19196, 7514, 2917, 1105, 398, 131, 37, 8, 1, 80380, 31307, 12111, 4597, 1680, 575, 177, 46, 9, 1, 337284, 130883, 50503, 19196, 7085, 2488, 808, 233, 56, 10, 1

Offset: 0

Philippe Deléham, Feb 01 2014

T(n+3,n) = A011826(n+5).

			Triangle begins:
      1;
      1,    1;
      4,    2,    1;
     16,    7,    3,    1;
     65,   27,   11,    4,   1;
    267,  108,   43,   16,   5,   1;
   1105,  440,  173,   65,  22,   6,  1;
   4597, 1812,  707,  267,  94,  29,  7, 1;
  19196, 7514, 2917, 1105, 398, 131, 37, 8, 1;
Production matrix is:
   1  1
   3  1   1
   6  1   1   1
  10  1   1   1   1
  15  1   1   1   1   1
  21  1   1   1   1   1   1
  28  1   1   1   1   1   1   1
  36  1   1   1   1   1   1   1   1
  45  1   1   1   1   1   1   1   1   1
  55  1   1   1   1   1   1   1   1   1   1
  66  1   1   1   1   1   1   1   1   1   1   1
  78  1   1   1   1   1   1   1   1   1   1   1   1
  91  1   1   1   1   1   1   1   1   1   1   1   1   1
  ...

G. C. Greubel, Rows n= 0..100 of triangle, flattened

Cf. (columns): A165201, A026726, A026671, A026674, A026672, A026675, A026673, A026843, A026842 or A026846 or A026849, A026844, A026841 or A026848.

Flat(List([0..12], n-> List([0..n], k-> Sum([0..n-k], j-> Binomial(2*n-k-j-2, n-k-j)*Fibonacci(2*j-1) )))); # G. C. Greubel, Jul 18 2019

[(&+[Binomial(2*n-k-j-2, n-k-j)*Fibonacci(2*j-1): j in [0..n-k]]): k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 18 2019

A236830 := (n,k) -> add(combinat:-fibonacci(2*i-1)*binomial(2*n-2-k-i,n-k-i), i = 0..n-k): seq(seq(A236830(n, k), k = 0..n), n = 0..10); # Peter Bala, Feb 18 2018

(* The function RiordanArray is defined in A256893. *)
c[x_] := (1 - Sqrt[1 - 4 x])/(2 x);
RiordanArray[1/(1 - # c[#]^3)&, # c[#]&, 11] // Flatten (* Jean-François Alcover, Jul 16 2019 *)
Table[Sum[Binomial[2*n-k-j-2, n-k-j]*Fibonacci[2*j-1], {j,0,n-k}], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Jul 18 2019 *)

T(n,k) = sum(j=0,n-k, binomial(2*n-k-j-2, n-k-j)*fibonacci(2*j -1));
for(n=0,12, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 18 2019

[[sum( binomial(2*n-k-j-2, n-k-j)*fibonacci(2*j -1) for j in (0..n-k) ) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jul 18 2019

Sum_{k=0..n} T(n,k) = A026726(n).
G.f.: 1/((x^2*C(x)^4-x*C(x))*y-x*C(x)^3+1), where C(x) the g.f. of A000108. - Vladimir Kruchinin, Apr 22 2015
From Peter Bala, Feb 18 2018: (Start)
T(n,k) = Sum_{i = 0..n-k} Fibonacci(2*i-1)*binomial(2*n-2-k-i,n-k-i).
The n-th row polynomial of row reverse triangle is the n-th degree Taylor polynomial of the rational function (1 - 3*x + 2*x^2)/(1 - 3*x + x^2) * 1/(1 - x)^n about 0. For example, for n = 4, (1 - 3*x + 2*x^2)/(1 - 3*x + x^2) * 1/(1 - x)^4 = 1 + 4*x + 11*x^2 + 27*x^3 + 65*x^4 + O(x^5), giving row 4 as (65, 27, 11, 4, 1). (End)

A165407 Expansion of 1/(1-x-x^3*c(x^3)), c(x) the g.f. of A000108.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 7, 11, 16, 27, 43, 65, 108, 173, 267, 440, 707, 1105, 1812, 2917, 4597, 7514, 12111, 19196, 31307, 50503, 80380, 130883, 211263, 337284, 548547, 885831, 1417582, 2303413, 3720995, 5965622, 9686617, 15652239, 25130844, 40783083, 65913927

Offset: 0

Paul Barry, Sep 17 2009

Hankel transform is A010892(n+1).
Row sums of A165408.
Number of UF-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are UF-equivalent iff the positions of pattern UF are identical in these paths. This also works for the pattern FU. - Sergey Kirgizov, Apr 08 2018
a(n) is the total number of lattice paths from (0,0) to (n-2*i,i) that do not go above the diagonal x=y using steps in {(1,0), (0,1)}. - Alois P. Heinz, Sep 20 2022

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
J.-L. Baril and A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1.

Cf. A000045, A000108, A001622, A010892, A165408.

Trisections give: A026726, A026671, A026674.

R:=PowerSeriesRing(Rationals(), 50); Coefficients(R!( (Sqrt(1-4*x^3) -1+2*x)/(2*x*(1-x-x^2)) )); // G. C. Greubel, Nov 09 2022

b:= proc(x, y) option remember; `if`(y<=x, `if`(x=0, 1,
      b(x-1, y)+`if`(y>0, b(x, y-1), 0)), 0)
    end:
a:= n-> add(b(n-2*i, i), i=0..n/3):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 20 2022

b[x_, y_]:= b[x, y]= If[y<=x, If[x==0, 1, b[x-1, y] +If[y>0, b[x, y-1], 0]], 0];
a[n_] := Sum[b[n-2*i, i], {i, 0, n/3}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 08 2022, after Alois P. Heinz *)
CoefficientList[Series[(Sqrt[1-4*x^3] -1+2*x)/(2*x*(1-x-x^2)), {x,0,50}], x] (* G. C. Greubel, Nov 09 2022 *)

def A165407_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 2/(1-2*x+sqrt(1-4*x^3)) ).list()
A165407_list(50) # G. C. Greubel, Nov 09 2022

G.f.: 2/(1 - 2*x + sqrt(1-4*x^3)) = 1/(1-x-x^3/(1-x^3/(1-x^3/(1-x^3/(1-.... (continued fraction).
a(n) = Sum_{k=ceiling(n/3)..n} C((n+k)/2,k)*((3*k-n)/2 + 1)*(1+(-1)^(n-k))/(2*(k+1)).
a(n) = Sum_{k=0..n+1} Fibonacci(n-k+1)*(0^k - A000108((k-2)/3)*(1+2*cos(2*Pi*(k-2)/3))/3).
(n+1)*a(n) = (n+1)*a(n-1) + (n+1)*a(n-2) +2*(2*n-7)*a(n-3) -2*(2*n-7)*a(n-4) -2*(2*n-7)*a(n-5). - R. J. Mathar, Nov 15 2011
a(3*n) = A026726(n); a(3*n+1) = A026671(n); a(3*n+2) = A026674(n+1). - Philippe Deléham, Feb 01 2014
Limit_{n->oo} a(n+1)/a(n) = A001622. - Alois P. Heinz, Sep 15 2022

A125187 Number of Dumont permutations of the first kind of length 2n avoiding the patterns 1423 and 4132.

Original entry on oeis.org

1, 1, 3, 12, 52, 232, 1049, 4777, 21845, 100159, 460023, 2115350, 9735205, 44829766, 206526972, 951759621, 4387156587, 20226421380, 93264500832, 430091815527, 1983549213861, 9148582037193, 42197572190160, 194643215702835

Offset: 0

Emeric Deutsch, Dec 19 2006

nonn

[1, 3, 12, 52, 232, ...] is INVERT transform of [1, 2, 27, 108, 440, ...] A026726. - Michael Somos, Apr 15 2012
HANKEL transform of sequence and the sequence omitting a(0) is the odd and even bisections of Fibonacci numbers respectively. This is the unique sequence with that property. - Michael Somos, Apr 15 2012
Bisection (even part) of A224747. - Alois P. Heinz, Jul 29 2013

			G.f. = 1 + x + 3*x^2 + 12*x^3 + 52*x^4 + 232*x^5 + 1049*x^6 + 4777*x^7 + 21845*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Cyril Banderier, Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
A. Burstein, Restricted Dumont permutations, arXiv:math/0402378 [math.CO], 2004
A. Burstein, Restricted Dumont permutations, Annals of Combinatorics, 9, 2005, 269-280 (Theorem 3.12).

Cf. A125188, A224747.

C:=(1-sqrt(1-4*x))/2/x: G:=(2-(1+x)*C)/(2-x-(1+x)*C): Gser:=series(G,x=0,30): seq(coeff(Gser,x,n),n=0..26);

a[ n_] := SeriesCoefficient[ (2 - 9 x + x^2 + (x + x^2) Sqrt[1 - 4 x]) / (2 (1 - 5 x + 2 x^2 - x^3)), {x, 0, n}]; (* Michael Somos, Jan 14 2014 *)

{a(n) = if( n<0, 0, polcoeff( (2 - 9*x + x^2 + (x + x^2) * sqrt(1 - 4*x + x * O(x^n)) ) / (2 * (1 - 5*x + 2*x^2 - x^3)), n))}; /* Michael Somos, Jan 14 2014 */

G.f.: [2-(1+x)C(x)]/[2-x-(1+x)C(x)], where C(x)=(1-sqrt(1-4x))/(2x) is the Catalan function.
From Gary W. Adamson, Jul 11 2011: (Start)
a(n) = upper left term in M^n, where M is an infinite square production matrix in which two columns of (1,2,3,...) are prepended to an infinite lower triangular matrix of all 1's and the rest zeros, as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 2, 1, 0, 0, 0, ...
  3, 3, 1, 1, 0, 0, ...
  4, 4, 1, 1, 1, 0, ...
  5, 5, 1, 1, 1, 1, ...
  ... (End)
Given g.f. A(x), then 0 = A(x)^2 * (x^3 - 2*x^2 + 5*x - 1) + A(x) *(x^2 - 9*x + 2) + (x^2 + 4*x -1). - Michael Somos, Jan 14 2014
0 = a(n)*(16*a(n+1) +6*a(n+2) -14*a(n+3) +210*a(n+4) -128*a(n+5) +18*a(n+6)) +a(n+1)*(-46*a(n+1) +143*a(n+2) -173*a(n+3) -283*a(n+4) +202*a(n+5) -29*a(n+6)) +a(n+2)*(-63*a(n+2) +386*a(n+3) +765*a(n+4) -529*a(n+5) +75*a(n+6)) +a(n+3)*(-559*a(n+3) +509*a(n+4) -149*a(n+5) +19*a(n+6)) +a(n+4)*(-108*a(n+4) +71*a(n+5) -12*a(n+6)) +a(n+5)*(-4*a(n+5) +a(n+6)). - Michael Somos, Jan 14 2014
G.f.: ( 2 - 9*x + x^2 + (x + x^2) * sqrt(1 - 4*x) ) / (2 - 10*x + 4*x^2 - 2*x^3). - Michael Somos, Apr 15 2012
G.f. = (1 - 3*y + y^2) / (1 - 4*y + 3*y^2 - y^3) = 1 / (1 - y / (1 - y / (1 - 2*y / (1 + y / (2 - y))))) where y = (1 - sqrt(1 - 4*x)) / 2. - Michael Somos, Apr 12 2012
D-finite with recurrence (-n+1)*a(n) +4*(2*n-3)*a(n-1) +(-13*n+19)*a(n-2) +(-13*n+75)*a(n-3) +(5*n-29)*a(n-4) +2*(-2*n+9)*a(n-5)=0. - R. J. Mathar, Jul 27 2013

A236843 Triangle read by rows related to the Catalan transform of the Fibonacci numbers.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 5, 9, 4, 1, 14, 28, 14, 6, 1, 42, 90, 48, 27, 7, 1, 132, 297, 165, 110, 35, 9, 1, 429, 1001, 572, 429, 154, 54, 10, 1, 1430, 3432, 2002, 1638, 637, 273, 65, 12, 1, 4862, 11934, 7072, 6188, 2548, 1260, 350, 90, 13, 1, 16796, 41990, 25194, 23256, 9996, 5508, 1700, 544, 104, 15, 1

Offset: 0

Philippe Deléham, Feb 01 2014

Row sums are A109262(n+1).

			Triangle begins:
    1;
    1,   1;
    2,   3,   1;
    5,   9,   4,   1;
   14,  28,  14,   6,  1;
   42,  90,  48,  27,  7, 1;
  132, 297, 165, 110, 35, 9, 1;
Production matrix is:
  1...1
  1...2...1
  0...1...1...1
  0...1...1...2...1
  0...0...0...1...1...1
  0...0...0...1...1...2...1
  0...0...0...0...0...1...1...1
  0...0...0...0...0...1...1...2...1
  0...0...0...0...0...0...0...1...1...1
  0...0...0...0...0...0...0...1...1...2...1
  0...0...0...0...0...0...0...0...0...1...1...1
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Columns: A000108 (k=0), A000245 (k=1), A002057 (k=2), A003517 (k=3), A000588 (k=4), A001392 (k=5), A003519 (k=6), A090749 (k=7), A000590 (k=8).
Cf. A026674, A026726, A032766, A109262.
Cf. A000045, A039599, A106566.

F:=Factorial;
A236843:= func< n,k | (1/4)*(6*k+5-(-1)^k)*F(2*n-Floor(k/2))/(F(n-k)*F(n+Floor((k+1)/2)+1)) >;
[A236843(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jun 13 2022

T[n_, k_]:= (1/4)*(6*k+5-(-1)^k)*(2*n-Floor[k/2])!/((n-k)!*(n+Floor[(k+1)/2]+1)!);
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jun 13 2022 *)

T(n, k) = (1/4)*(6*k + 5 - (-1)^k)*(2*n - (k\2))!/((n-k)!*(n + (k+1)\2 + 1)!) \\ Andrew Howroyd, Jan 04 2023

F=factorial
def A236843(n,k): return (1/2)*(3*k+2+(k%2))*F(2*n-(k//2))/(F(n-k)*F(n+((k+1)//2)+1))
flatten([[A236843(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Jun 13 2022

G.f. for the column k (with zeros omitted): C(x)^A032766(k+1) where C(x) is g.f. for Catalan numbers (A000108).
Sum_{k=0..n} T(n,k) = A109262(n+1).
Sum_{k=0..n} T(n+k,2k) = A026726(n).
Sum_{k=0..n} T(n+1+k,2k+1) = A026674(n+1).
T(n, k) = (1/4)*(6*k + 5 - (-1)^k)*(2*n - floor(k/2))!/((n-k)!*(n + floor((k+1)/2) + 1)!). - G. C. Greubel, Jun 13 2022

A276472 Modified Pascal's triangle read by rows: T(n,k) = T(n-1,k) + T(n-1,k-1), 12. T(n,n) = T(n,n-1) + T(n-1,n-1), n>1. T(1,1) = 1, T(2,1) = 1. n>=1.

Original entry on oeis.org

1, 1, 2, 4, 3, 5, 11, 7, 8, 13, 29, 18, 15, 21, 34, 76, 47, 33, 36, 55, 89, 199, 123, 80, 69, 91, 144, 233, 521, 322, 203, 149, 160, 235, 377, 610, 1364, 843, 525, 352, 309, 395, 612, 987, 1597, 3571, 2207, 1368, 877, 661, 704, 1007, 1599, 2584, 4181

Offset: 1

Yuriy Sibirmovsky, Sep 12 2016

The recurrence relations for the border terms are the only way in which this differs from Pascal's triangle.
Column T(2n,n+1) appears to be divisible by 4 for n>=2; T(2n-1,n) divisible by 3 for n>=2; T(2n,n-2) divisible by 2 for n>=3.
The symmetry of T(n,k) can be observed in a hexagonal arrangement (see the links).
Consider T(n,k) mod 3 = q. Terms with q = 0 show reflection symmetry with respect to the central column T(2n-1,n), while q = 1 and q = 2 are mirror images of each other (see the link).

			Triangle T(n,k) begins:
n\k 1    2    3    4   5    6    7    8    9
1   1
2   1    2
3   4    3    5
4   11   7    8    13
5   29   18   15   21   34
6   76   47   33   36   55   89
7   199  123  80   69   91   144 233
8   521  322  203  149  160  235 377  610
9   1364 843  525  352  309  395 612  987  1597
...
In another format:
__________________1__________________
_______________1_____2_______________
____________4_____3_____5____________
________11_____7_____8_____13________
____29_____18_____15____21_____34____
_76_____47____33_____36____55_____89_

Yuriy Sibirmovsky, T(n,k), read by rows as a linear sequence a(j) for j = 1..5050
Yuriy Sibirmovsky, Symmetrical hexagonal arrangement for initial terms of T(n,k)
Yuriy Sibirmovsky, T(n,k) compared with Pascal's triangle
Yuriy Sibirmovsky, Illustration for T(n,k) mod 3

Cf. A000045, A000204, A001519, A001906, A002878, A005248, A054441, A088305, A122367, A258109, A026671, A026726, A026732, A004187, A049685, A033891, A206351, A092521, A081018, A049684, A058038, A081016, A003482, A049629, A133273, A049664, A049683, A119032, A023039, A007805, A033889.

Nm=12;
T=Table[0,{n,1,Nm},{k,1,n}];
T[[1,1]]=1;
T[[2,1]]=1;
T[[2,2]]=2;
Do[T[[n,1]]=T[[n-1,1]]+T[[n,2]];
T[[n,n]]=T[[n-1,n-1]]+T[[n,n-1]];
If[k!=1&&k!=n,T[[n,k]]=T[[n-1,k]]+T[[n-1,k-1]]],{n,3,Nm},{k,1,n}];
{Row[#,"\t"]}&/@T//Grid

T(n,k) = if (k==1, if (n==1, 1, if (n==2, 1, T(n-1,1) + T(n,2))), if (kMichel Marcus, Sep 14 2016

Conjectures:
Relations with other sequences:
T(n+1,1) = A002878(n-1), n>=1.
T(n,n) = A001519(n) = A122367(n-1), n>=1.
T(n+1,2) = A005248(n-1), n>=1.
T(n+1,n) = A001906(n) = A088305(n), n>=1.
T(2n-1,n) = 3*A054441(n-1), n>=2. [the central column].
Sum_{k=1..n} T(n,k) = 3*A105693(n-1), n>=2. [row sums].
Sum_{k=1..n} T(n,k)-T(n,1)-T(n,n) = 3*A258109(n), n>=2.
T(2n,n+1) - T(2n,n) = A026671(n), n>=1.
T(2n,n-1) - T(2n,n) = 2*A026726(n-1), n>=2.
T(n,ceiling(n/2)) - T(n-1,floor(n/2)) = 2*A026732(n-3), n>=3.
T(2n+1,2n) = 3*A004187(n), n>=1.
T(2n+1,2) = 3*A049685(n-1), n>=1.
T(2n+1,2n) + T(2n+1,2) = 3*A033891(n-1), n>=1.
T(2n+1,3) = 5*A206351(n), n>=1.
T(2n+1,2n)/3 - T(2n+1,3)/5 = 4*A092521(n-1), n>=2.
T(2n,1) = 1 + 5*A081018(n-1), n>=1.
T(2n,2) = 2 + 5*A049684(n-1), n>=1.
T(2n+1,2) = 3 + 5*A058038(n-1), n>=1.
T(2n,3) = 3 + 5*A081016(n-2), n>=2.
T(2n+1,1) = 4 + 5*A003482(n-1), n>=1.
T(3n,1) = 4*A049629(n-1), n>=1.
T(3n,1) = 4 + 8*A119032(n), n>=1.
T(3n+1,3) = 8*A133273(n), n>=1.
T(3n+2,3n+2) = 2 + 32*A049664(n), n>=1.
T(3n,3n-2) = 4 + 32*A049664(n-1), n>=1.
T(3n+2,2) = 2 + 16*A049683(n), n>=1.
T(3n+2,2) = 2*A023039(n), n>=1.
T(2n-1,2n-1) = A033889(n-1), n>=1.
T(3n-1,3n-1) = 2*A007805(n-1), n>=1.
T(5n-1,1) = 11*A097842(n-1), n>=1.
T(4n+5,3) - T(4n+1,3) = 15*A000045(8n+1), n>=1.
T(5n+4,3) - T(5n-1,3) = 11*A000204(10n-2), n>=1.
Relations between left and right sides:
T(n,1) = T(n,n) - T(n-2,n-2), n>=3.
T(n,2) = T(n,n-1) - T(n-2,n-3), n>=4.
T(n,1) + T(n,n) = 3*T(n,n-1), n>=2.

A333378 a(n) = F(n) * (-1)^(n*(n-1)/2) where F(n) = A000045(n) Fibonacci numbers.

Original entry on oeis.org

0, 1, -1, -2, 3, 5, -8, -13, 21, 34, -55, -89, 144, 233, -377, -610, 987, 1597, -2584, -4181, 6765, 10946, -17711, -28657, 46368, 75025, -121393, -196418, 317811, 514229, -832040, -1346269, 2178309, 3524578, -5702887, -9227465, 14930352, 24157817, -39088169

Offset: 0

Michael Somos, Mar 17 2020

This is a strong elliptic divisibility sequence t_n as given in [Kimberling, p. 16] where x = -1, y = -2, z = -3.
The Hankel transform of -A026726(n+k) is a(2*n+2+k) for k = 0, 1.
Let a(n) := F(n) * (-1)^binomial(n, 2). Then a(m - n) * a(m + n) = a(m + 1) * a(m - 1) * a(n)^2 - a(n + 1) * a(n - 1) * a(m)^2. This plus gcd(f[n], f[m]) = |f[gcd(n, m)]| makes a[] a strong elliptic divisibility sequence. Likewise F(n) * (-1)^binomial(n - 1, 2), but no other asSIGNation (mod scaling). - Bill Gosper, May 28 2008

			G.f. = x - x^2 - 2*x^3 + 3*x^4 + 5*x^5 - 8*x^6 - 13*x^7 + 21*x^8 + ...

Clark Kimberling, Strong divisibility sequences and some conjectures, Fib. Quart., 17 (1979), 13-17.
Index entries for linear recurrences with constant coefficients, signature (0,-3,0,-1).

Cf. A000045, A026726.

a[ n_] := Fibonacci[n] (-1)^(n (n - 1) / 2);
a[ n_] := With[{m=n-1}, I^m^2 ChebyshevU[m, I/2]]; (* Michael Somos, Mar 19 2020 *)

{a(n) = fibonacci(n) * (-1)^(n*(n-1)/2)};

def A333378():
    a, b, c, d = False, True, True, False
    x, y = 0, 1
    while True:
        yield x if a else -x
        x, y = y, x - y
        a, b, c, d = b, c, d, a
a = A333378()
print([next(a) for  in range(39)]) # _Peter Luschny, Mar 19 2020

G.f.: (x^3 - x^2 + x)/(x^4 + 3*x^2 + 1).
a(n) = -a(-n) = -3*a(n+2) -a(n+4) for all n in Z.
0 = a(n)^2 -a(n+1)^2 +a(n+2)^2 +2*a(n)*a(n+2) for all n in Z.
0 = a(n)*(+a(n+2)) +a(n+1)*(+a(n+1) +a(n+3)) +a(n+2)*(+a(n+2)) for all n in Z.
0 = a(n)*a(n+4) - a(n+1)*a(n+3) - 2*a(n+2)^2 for all n in Z.
0 = a(n)*a(n+5) + 2*a(n+1)*a(n+4) - 3*a(n+2)*a(n+3) for all n in Z.
a(n+1) = i^(n^2) * U(n, i/2) for all n in Z [From Gosper, Mar 19 2020]. - Michael Somos, Mar 19 2020

A026731 Greatest number in row n of array T given by A026725.

Original entry on oeis.org

1, 1, 2, 4, 7, 16, 27, 65, 108, 267, 440, 1105, 1812, 4597, 7514, 19196, 31307, 80380, 130883, 337284, 548547, 1417582, 2303413, 5965622, 9686617, 25130844, 40783083, 105954110, 171868037, 447015744, 724837891, 1886996681

Offset: 0

Clark Kimberling

nonn

Cf. A026674, A026726

a(2*n) = A026726(n); a(2*n+1) = A026674(n+1). - Philippe Deléham, Feb 01 2014

cp's OEIS Frontend

A039599 Triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials U_n(x).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A009766 Catalan's triangle T(n,k) (read by rows): each term is the sum of the entries above and to the left, i.e., T(n,k) = Sum_{j=0..k} T(n-1,j).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Sage

Formula

A106566 Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 1, 1, 1, 1, 1, 1, 1, ... ] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ... ] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A236830 Riordan array (1/(1-x*C(x)^3), x*C(x)), C(x) the g.f. of A000108.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A165407 Expansion of 1/(1-x-x^3*c(x^3)), c(x) the g.f. of A000108.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

A236830 Riordan array (1/(1-xC(x)^3), xC(x)), C(x) the g.f. of A000108.