A064310 -id:A064310 - 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

A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.

Original entry on oeis.org

0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 2892818244, 10786724388, 40347919626, 151355847012, 569274150156, 2146336125648, 8110508473252, 30711521221376

Offset: 0

N. J. A. Sloane

Row-sum of signed Catalan triangle A009766. - Wouter Meeussen
There are two schools of thought about the best indexing for these numbers. Deutsch and Shapiro have a(4) = 6 whereas here a(5) = 6. The formulas given here use both labelings.
From D. G. Rogers, Oct 18 2005: (Start)
I notice that you have some other zero-one evaluations of binary bracketings (such as A055395). But if you have an operation # with 0#0 = 1#0 = 1, 0#1 = 1#1 = 0, and look at the number of bracketings of a string of n 0's that come out 0, you get another instance of the Fine numbers.
For Z = 1 + x(ZW + WW) = 1 + x CW and W = x(ZZ + ZW) = xZC. Hence Z = 1 + xxCCZ, the functional equational for the g.f. of the Fine numbers. Indeed, C = Z + W = Z + xCZ.
In terms of rooted planar trees with root of even degree, this says that of all rooted planar trees, some have root of even degree (Z) and some have root of odd degree (xCZ). (End)
Hankel transform of a(n+1) = [1,0,1,2,6,18,57,186,...] is A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Starting with offset 3 = iterates of M * [1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,1,...] as the super and subdiagonals. - Gary W. Adamson, Jan 09 2009
Starting with 1 and convolved with A068875 = the Catalan numbers with offset 1. - Gary W. Adamson, May 01 2009
For a relation to non-crossing partitions of the root system A_n, see A100754. - Tom Copeland, Oct 19 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)] = (x-2x^2)/(1-x)^2, and Fin(Cinv(x)) = P(x).
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
a(n+1) is the number of Dyck paths of semilength n avoiding UD at Level 0. For n = 3 the a(4) = 2 such Dyck paths are UUUDDD and UUDUDD. - Ran Pan, Sep 23 2015
For n >= 3, a(n) is the number of permutations pi of [n-2] such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - Colin Defant, Sep 16 2018
Named after the American scientist Terrence Leon Fine (1939-2021). - Amiram Eldar, Jun 08 2021

			G.f. = x + x^3 + 2*x^4 + 6*x^5 + 18*x^6 + 57*x^7 + 186*x^8 + 622*x^9 + 2120*x^10 + ...

Emeric Deutsch and Louis W. Shapiro, Seventeen Catalan identities, Bull. Instit. Combin. Applic., Vol. 31 (2001), pp. 31-38.
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). - N. J. A. Sloane, Jun 05 2012
Louis W. Shapiro and Carol J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1670 (first 201 terms from T. D. Noe)
Francesca Aicardi, Fuss-Catalan Triangles, arXiv:2310.07317 [math.CO], 2023.
Martin Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb., Vol. 12 (2005), R31.
Elena Barcucci, Elisa Pergola, Renzo Pinzani and Simone Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, 46 (2001).
Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, Vol. 18 (2011), #P178.
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 4.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry, Series reversion with Jacobi and Thron continued fractions, arXiv:2107.14278 [math.NT], 2021.
Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 6, 10.
George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
Rachael Boyd and Richard Hepworth, Combinatorics of injective words for Temperley-Lieb algebras, arXiv:2006.04261 [math.AT], 2020.
Naiomi Tuere Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi T. Cameron and Jillian E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19 (2016), #16.6.1.
Peter J. Cameron, Some sequences of integers, Discrete Math., Vol. 75, No. 1-3 (1989), pp. 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., Vol. 43 (1989), pp. 89-102.
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
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. See p. 13.
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, A bijection between the triangulations of convex polygons and ordered trees, Integers, Vol. 20 (2020), Article #A8.
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Emeric Deutsch and Louis W. Shapiro, A survey of the Fine numbers, Discrete Math., Vol. 241 (2001), pp. 241-265.
Filippo Disanto, Andrea Frosini and Simone Rinaldi and Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics, Vol. 32 (2008), pp. 883-912.
R. R. X. Du, J. He, and X. Yun, Counting vertices in plane and k-ary trees with given outdegree, arXiv preprint arXiv:1501.07468 [math.CO], 2015.
Shalosh B. Ekhad, Mingjia Yang and Doron Zeilberger, Automated proofs of many conjectured recurrences in the OEIS made by R. J. Mathar, arXiv:1707.04654 [math.HO], 2017.
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.
Terrence Fine, Extrapolation when very little is known about the source, Information and Control, Vol. 16 (1970), pp. 331-359.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 27.
Taras Goy and Mark Shattuck, Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries, arXiv:2303.10223 [math.CO], 2023.
Taras Goy and Mark Shattuck, Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries, Carpathian Math. Publ. 15 (2023), No. 2, 420-436.
Candice Jean-Louis and Asamoah Nkwanta, Some algebraic structure of the Riordan group, Linear Algebra and its Applications, Vol. 438, No. 5 (2013), pp. 2018-2035. - _N. J. A. Sloane_, Jan 03 2013
Sergey Kitaev, Anna de Mier, Marc Noy, On the number of self-dual rooted maps, European J. Combin., Vol. 35 (2014), pp. 377-387. MR3090510. See page 827.
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, Vol. 4 (2001), Article 01.1.5.
Toufik Mansour and Mark Shattuck, Chebyshev Polynomials and Statistics on a New Collection of Words in the Catalan Family, arXiv:1407.3516 [math.CO], 2014.
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
Asamoah Nkwanta and Akalu Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, Vol. 16 (2013), Article 13.9.5.
Paul Peart and Wen-Jin Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), Article 00.2.1.
Paul Peart and Wen-Jin Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, Vol. 4 (2001), Article 01.1.3.
Aaron Robertson, Dan Saracino and Doron Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
D. G. Rogers, Similarity relations on finite ordered sets, J. Combin. Theory, Series A, Vol. 23, No. 1 (1977), pp. 88-98. Erratum, loc. cit., Vol. 25 (1978), pp. 95-96.
Louis W. Shapiro and Carol J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS, Vol. 12 (2009), Article 09.3.2.
Volker Strehl, A note on similarity relations, Discr. Math., Vol. 19, No. 1 (1977), pp. 99-102.
Hua Sun and Yi Wang, A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers, J. Int. Seq., Vol. 17 (2014), Article 14.5.2
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, M.Sc. Thesis, Reykjavik Univ., May 2016.
Index entries for sequences related to rooted trees

A column of A065600.
Sequence with signs: A064310.
Bisections: A138413, A138414.
Logarithmic derivative: A072547.
Cf. A068875, A000108, A000045, A005043, A057078, A007317, A091867, A104597.
Cf. A000012, A009766, A039598, A055395, A064306, A100754, A126093.

a000957 n = a000957_list !! n
a000957_list = 0 : 1 :
   (map (`div` 2) $ tail $ zipWith (-) a000108_list a000957_list)
-- Reinhard Zumkeller, Nov 12 2011

[0,1] cat  [n le 1 select n-1 else (Catalan(n)-Self(n-1))/2: n in [1..30]]; // Vincenzo Librandi, Nov 17 2016

t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1,x,90); A000957 := n- coeff(t2,x,n);
A000957 := proc(n): if n = 0 then 0 else add((-1)^(n+k-1)*binomial(n+k-1, n-1)*(n-k)/n, k=0..n-1) fi: end: seq(A000957(n), n=0..28); # Johannes W. Meijer, Jul 22 2013
# third Maple program:
a:= proc(n) option remember; `if`(n<3, n*(2-n),
      ((7*n-12)*a(n-1)+(4*n-6)*a(n-2))/(2*n))
    end:
seq(a(n), n=0..32);  # Alois P. Heinz, Apr 23 2020

Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} ], {n, 0, 36} ] (* Wouter Meeussen *)
a[0] = 0; a[n_] := (1/2)*(-3*(-1/2)^n + 2^(n+1)*(2n-1)!!* Hypergeometric2F1Regularized[2, 2n+1, n+2, -1]); (* Jean-François Alcover, Feb 22 2012 *)
Table[2^n (n-2) (2n-1)!! (3 (n-1) Hypergeometric2F1[1, 3-n, 3+n, 2] - n - 2)/(n+2)! + KroneckerDelta[n], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)

C(n):=binomial(2*n,n)/(n+1);
a(n):=if n<=0 then 0 else if n=1 then 1 else  sum(C(n-i-1)*(a(i)+a(i-1)),i,2,n-1);
/* Vladimir Kruchinin, Apr 23 2020 */

{a(n) = if( n<1, 0, polcoeff( 1 / (1 + 2 / (1 - sqrt(1 - 4*x + x*O(x^n)))), n))}; /* Michael Somos, Sep 17 2006 */

{a(n) = if( n<1, 0, polcoeff( 1 / (1 + 1 / serreverse(x - x^2 + x*O(x^n))), n))}; /* Michael Somos, Sep 30 2006 */

from itertools import count, islice
def A000957_gen(): # generator of terms
    yield from (0,1,0)
    a, c = 0, 1
    for n in count(1):
        yield (a:=(c:=c*((n<<2)+2)//(n+2))-a>>1)
A000957_list = list(islice(A000957_gen(),20)) # Chai Wah Wu, Apr 26 2023

def Fine():
    f, c, n = 1, 1, 1
    yield 0
    while True:
        yield f
        n += 1
        c = c * (4*n - 6) // n
        f = (c - f) // 2
a = Fine()
print([next(a) for  in range(29)])  # _Peter Luschny, Nov 30 2016

Catalan(n) = 2*a(n+1) + a(n), n >= 1. [Corrected by Pontus von Brömssen, Jul 23 2022]
a(n) = (A064306(n-1) + (-1)^(n-1))/2^n, n >= 1.
G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) (compare g.f. for Catalan numbers, A000108). - Emeric Deutsch
a(n) ~ 4^n/(9*n*sqrt(n*Pi)). (Corrected by Peter Luschny, Oct 26 2015.)
a(n) = (2/(n-1))*Sum_{j=0..n-3}(-2)^j*(j+1)*binomial(2n-1, n-3-j), n>=2. - Emeric Deutsch, Dec 26 2003
a(n) = 3*Sum_{j=0..floor((n-1)/2)} binomial(2n-2j-2, n-1) - binomial(2n, n) for n>0. - Emeric Deutsch, Jan 28 2004
Reversion of g.f. (x-2x^2)/(1-x)^2. - Ralf Stephan, Mar 22 2004
a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, C(1/2, k)8^k})+0^n; a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, (-1)^(k-1)*2^k*(2k)!/((k!)^2*(2k-1))})+0^n. - Paul Barry, Jun 10 2005
Hankel determinant transform is 1-n. - Michael Somos, Sep 17 2006
a(n+1) = A126093(n,0). - Philippe Deléham, Mar 05 2007
a(n+1) has g.f. 1/(1-0*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(..... (continued fraction). - Paul Barry, Dec 02 2008
From Paul Barry, Jan 17 2009: (Start)
G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;
a(n+1) = Sum_{k=0..n} (-1)^k*C(2n-k,n-k)*(k+1)/(n+1). (End)
a(n) = 3*(-1/2)^(n+1) + Gamma(n+1/2)*4^n*hypergeom([1, n+1/2],[n+2],-8) /(sqrt(Pi)*(n+1)!) (for n>0). - Mark van Hoeij, Nov 11 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n>=1, a(n+1) = (-1)^n*charpoly(A,1). - Milan Janjic, Jul 08 2010
a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
0, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011
a(n+1) = Sum_{k=0..n} A039598(n,k)*(-2)^k. - Philippe Deléham, Nov 04 2011
D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar, Nov 15 2011
a(n) = sum(sum(2^(s-2n-2k)*(n/n+2k)binomial(n+2k, k)*binomial(s-n-1, s-2n-2k), (k=0, ..., floor((s-2n)/2)), (n=1, ..., s) with s>=2. - José Luis Ramírez Ramírez, Mar 22 2012
0 = a(n)*(16*a(n+1) + 22*a(n+2) - 20*a(n+3)) + a(n+1)*(34*a(n+1) + 53*a(n+2) - 38*a(n+3)) + a(n+2)*(10*a(n+2) + 4*a(n+3)) for all n in Z if we extend by a(0)=-1, a(-n) = -3/4 * (-2)^n if n>0. - Michael Somos, Jan 31 2014 [Corrected by Pontus von Brömssen, Aug 04 2022]
G.f. A(x) satisfies x*A'(x)/A(x) = x + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for A072547. - Peter Bala, Oct 01 2015
a(n) = 2^n*(n-2)*(2*n-1)!!*(3*(n-1)*hypergeom([1,3-n], [3+n], 2)-n-2)/(n+2)! + 0^n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = binomial(2*n,n)*(hypergeom([1,(1-n)/2,1-n/2],[1-n,3/2-n],1)*3/(4-2/n)-1) for n>=2. - Peter Luschny, Oct 26 2015
O.g.f. A(x) satisfies 1 + A(x) = (1 + 3*Sum_{n >= 1} Catalan(n)*x^n)/(1 + 2*Sum_{n >= 1} Catalan(n)*x^n) = (1 + 2*Sum_{n >= 1} binomial(2*n,n)*x^n )/(1 + 3/2*Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016
a(n) = Sum_{i=2..n-1} C(n-i-1)*(a(i)+a(i-1)), a(0)=0, a(1)=1, where C(n) = A000108(n). - Vladimir Kruchinin, Apr 23 2020

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

A064062 Generalized Catalan numbers C(2; n).

Original entry on oeis.org

1, 1, 3, 13, 67, 381, 2307, 14589, 95235, 636925, 4341763, 30056445, 210731011, 1493303293, 10678370307, 76957679613, 558403682307, 4075996839933, 29909606989827, 220510631755773, 1632599134961667, 12133359132082173

Offset: 0

Wolfdieter Lang, Sep 13 2001

a(n+1) = Y_{n}(n+1) = Z_{n}, n >= 0, in the Derrida et al. 1992 reference (see A064094) for alpha=2, beta=1 (or alpha=1, beta=2).
a(n) = number of Dyck n-paths (A000108) in which each upstep (U) not at ground level is colored red (R) or blue (B). For example, a(3)=3 counts URDD, UBDD, UDUD (D=downstep). - David Callan, Mar 30 2007
The Hankel transform of this sequence is A002416. - Philippe Deléham, Nov 19 2007
The sequence a(n)/2^n, with g.f. 1/(1-xc(x)/2), has Hankel transform 1/2^n. - Paul Barry, Apr 14 2008
The REVERT transform of the odd numbers [1,3,5,7,9,...] is [1, -3, 13, -67, 381, -2307, 14589, -95235, 636925, ...] - N. J. A. Sloane, May 26 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..200
J. Abate and W. Whitt, Brownian Motion and the Generalized Catalan Numbers, J. Int. Seq. 14 (2011) # 11.2.6, example section 3.
Jean-Luc Baril, Sergey Kirgizov, and Mehdi Naima, A lattice on Dyck paths close to the Tamari lattice, arXiv:2309.00426 [math.CO], 2023.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - From _N. J. A. Sloane_, Oct 08 2012
J. Bloom and S. Elizalde, Pattern avoidance in matchings and partitions, arXiv:1211.3442 [math.CO] (2012) Theorem 6.1.
N. Bonichon, C. Gavoille and N. Hanusse, Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation, In Proceedings of WG'03, volume 2880 of LNCS, pp. 81-92, 2003.
Alexander Burstein, Sergi Elizalde and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv:math/0610234 [math.CO], 2006.
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.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).
Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari, Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem, arXiv:2407.07765 [cs.LG], 2024. See p. 44.
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
N. J. A. Sloane, Transforms
A. Vieru, Agoh's conjecture: its proof, its generalizations, its analogues, arXiv preprint arXiv:1107.2938 [math.NT], 2011-2012.

Generalized Catalan numbers C(m; n): A000012 (m = 0), A000108 (m = 1), A064063 (m = 3) and A064087 - A064093 (m = 4 thru 10); A064310 (m = -1), A064311 (m = -2) and A064325 - A064333 (m = -3 thru -11).

Cf. A064334, A119529.

R:=PowerSeriesRing(Rationals(), 30);
Coefficients(R!( (3 - Sqrt(1-8*x))/(2*(1+x)) )); // G. C. Greubel, Sep 27 2024

1, seq(simplify(hypergeom([1-n,n],[-n],2)), n=1..100); # Robert Israel, Nov 30 2014

a[0]=1; a[1]=1; a[n_]/;n>=2 := a[n] = a[n-1] + Sum[(a[k] + a[k-1])a[n-k],{k,n-1}]; Table[a[n],{n,0,10}] (* David Callan, Aug 27 2009 *)
a[n_] := 2*Sum[ (-1)^j*2^(n-j-1)*Binomial[2*(n-j-1), n-j-1]/(n-j), {j, 0, n-1}] + (-1)^n; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 03 2013 *)

{a(n)=polcoeff((3-sqrt(1-8*x+x*O(x^n)))/(2+2*x),n)}

{a(n)=local(A=1+x); for(i=1, n, A=1+A^4*intformal(1/(A^2+x*O(x^n)))); polcoeff(A, n)} \\ Paul D. Hanna, Dec 24 2013
for(n=0, 25, print1(a(n), ", "))

{a(n)=polcoeff(1/(1 - serreverse(x-2*x^2 +x^2*O(x^n))),n)}
for(n=0,30,print1(a(n),", ")) \\ Paul D. Hanna, Nov 30 2014

def a(n):
    if n==0: return 1
    return hypergeometric([1-n, n], [-n], 2).simplify()
[a(n) for n in range(22)] # Peter Luschny, Dec 01 2014

G.f.: (1 + 2*x*C(2*x)) / (1+x) = 1/(1 - x*C(2*x)) with C(x) g.f. of Catalan numbers A000108.
a(n) = A062992(n-1) = Sum_{m = 0..n-1} (n-m)*binomial(n-1+m, m)*(2^m)/n, n >= 1, a(0) = 1.
a(n) = Sum_{k = 0..n} A059365(n, k)*2^(n-k). - Philippe Deléham, Jan 19 2004
G.f.: 1/(1-x/(1-2x/(1-2x/(1-2x/(1-.... = 1/(1-x-2x^2/(1-4x-4x^2/(1-4x-4x^2/(1-.... (continued fractions). - Paul Barry, Jan 30 2009
a(n) = (32/Pi)*Integral_{x = 0..1} (8*x)^(n-1)*sqrt(x*(1-x)) / (8*x+1). - Groux Roland, Dec 12 2010
a(n+2) = 8^(n+2)*( c(n+2)-c(1)*c(n+1) - Sum_{i=0..n-1} 8^(-i-2)*c(n-i)*a(i+2) ) with c(n) = Catalan(n+2)/2^(2*n+1). - Groux Roland, Dec 12 2010
a(n) = the upper left term in M^n, M = the production matrix:
  1, 1
  2, 2, 1
  4, 4, 2, 1
  8, 8, 4, 2, 1
  ... - Gary W. Adamson, Jul 08 2011
D-finite with recurrence: n*a(n) + (12-7n)*a(n-1) + 4*(3-2n)*a(n-2) = 0. - R. J. Mathar, Nov 16 2011 (This follows easily from the generating function. - Robert Israel, Nov 30 2014)
G.f. satisfies: A(x) = 1 + A(x)^4 * Integral 1/A(x)^2 dx. - Paul D. Hanna, Dec 24 2013
G.f. satisfies: Integral 1/A(x)^2 dx = x - x^2*G(x), where G(x) is the o.g.f. of A000257, the number of rooted bicubic maps. - Paul D. Hanna, Dec 24 2013
G.f. A(x) satisfies: A(x - 2*x^2) = 1/(1-x). - Paul D. Hanna, Nov 30 2014
a(n) = hypergeometric([1-n, n], [-n], 2) for n > 0. - Peter Luschny, Nov 30 2014
G.f.: (3 - sqrt(1-8*x))/(2*(x+1)). - Robert Israel, Nov 30 2014
a(n) ~ 2^(3*n+1) / (9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 22 2014
O.g.f. A(x) =  1 + series reversion of (x*(1 - x)/(1 + x)^2). Logarithmically differentiating (A(x) - 1)/x gives 3 + 17*x + 111*x^2 + ..., essentially a g.f for A119259. - Peter Bala, Oct 01 2015
From Peter Bala, Jan 06 2022: (Start)
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 6*x^3 + 23*x^4 + ... is a g.f. for A022558.
The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. (End)

Row sums are generalized Catalan numbers A064310. Diagonal sums are 0^n+(-1)^n*A030238(n-2). Inverse is A026729, as number triangle. Columns have g.f. (xc(-x))^k=((sqrt(1+4x)-1)/2)^k.

Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, ... ] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... ] where DELTA is the operator defined in A084938. - Philippe Deléham, May 31 2005

The sequence for column m (m >= 1) (without leading zeros and the first 1) appears in the Derrida et al. 1992 reference as Z_{N}=:Y_{N}(N+1), N >=0, for (unphysical) alpha = -m, beta = 1 (or alpha = 1, beta = -m). In the Derrida et al. 1993 reference the formula in eq. (39) gives Z_{N}(alpha,beta)/(alpha*beta)^N for N>=1. See also Liggett reference, proposition 3.19, p. 269, with lambda for alpha and rho for 1-beta.

The rows of this triangle are symmetric up to sign. Row sums = 2 after row 0. Unsigned row sums = A116466. Row squared sums = A116467. Central terms of odd rows: T(2*n+1,n+1) = |A064310(n)|.

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

A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

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

A064062 Generalized Catalan numbers C(2; n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A099039 Riordan array (1,c(-x)), where c(x) = g.f. of Catalan numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A104629 Expansion of (1-2x-sqrt(1-4x))/(x^2 * (1+2x+sqrt(1-4x))).