A065600 -id:A065600 - cp's OEIS frontend

A033184 Catalan triangle A009766 transposed.

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

Offset: 1

Christian G. Bower

Triangle read by rows: T(n,k) = number of Dyck n-paths (A000108) containing k returns to ground level. E.g., the paths UDUUDD, UUDDUD each have 2 returns; so T(3,2)=2. Row sums over even-indexed columns are the Fine numbers A000957. - David Callan, Jul 25 2005
Triangular array of numbers a(n,k) = number of linear forests of k planted planar trees and n non-root nodes.
Catalan convolution triangle; with offset [0,0]: a(n,m)=(m+1)*binomial(2*n-m,n-m)/(n+1), n >= m >= 0, else 0. G.f. for column m: c(x)*(x*c(x))^m with c(x) g.f. for A000108 (Catalan). - Wolfdieter Lang, Sep 12 2001
a(n+1,m+1), n >= m >= 0, a(n,m) := 0, nA030528(n,m)*(-1)^(n-m).
a(n,k)=number of Dyck paths of semilength n and having k returns to the axis. Also number of Dyck paths of semilength n and having first peak at height k. Also number of ordered trees with n edges and root degree k. Also number of ordered trees with n edges and having the leftmost leaf at level k. Also number of parallelogram polyominoes of semiperimeter n+1 and having k cells in the leftmost column. - Emeric Deutsch, Mar 01 2004
Triangle T(n,k) with 1<=k<=n given by [0, 1, 1, 1, 1, 1, 1, 1, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] = 1; 0, 1; 0, 1, 1; 0, 2, 2, 1; 0, 5, 5, 3, 1; 0, 14, 14, 9, 4, 1; ... where DELTA is the operator defined in A084938; essentially the same triangle as A059365. - Philippe Deléham, Jun 14 2004
Number of Dyck paths of semilength and having k-1 peaks at height 2. - Emeric Deutsch, Aug 31 2004
Riordan array (c(x),x*c(x)), c(x) the g.f. of A000108. Inverse of Riordan array (1-x,x*(1-x)). - Paul Barry, Jun 22 2005
Subtriangle of triangle A106566. - Philippe Deléham, Jan 07 2007
T(n, k) is also the number of order-preserving and order-decreasing full transformations (of an n-chain) with exactly k fixed points. - Abdullahi Umar, Oct 02 2008
Triangle read by rows, product of A065600 and A007318 considered as infinite lower triangular arrays; A033184 = A065600*A007318. - Philippe Deléham, Dec 07 2009
The formula stating "Column k is the k-fold convolution of column 1" is equivalent to repeatedly applying M to [1,0,0,0,...], where M is an upper triangular matrix of all 1's with an additional single subdiagonal of 1's. - Gary W. Adamson, Jun 06 2011
4^(n-1) = (n-th row terms) dot (first n terms in A001792), where A001792 = binomial transform of the natural numbers: (1, 3, 8, 20, 48, 112, ...). Example: 4^4 = 256 = (14, 14, 9, 4, 1) dot (1, 3, 8, 20, 48) = (42 + 42 + 28 + 14 + 5 + 1) = 256. - Gary W. Adamson, Jun 17 2011
The e.g.f. for the n-th subdiagonal of the triangle has the form exp(x)*P(n,x), where P(n,x) is the e.g.f. for row n of triangle A039599. For example, the third row of A039599 is [5, 9, 5, 1] and so the third subdiagonal sequence of this triangle [5, 14, 28, 48, 75, ...] has the e.g.f. exp(x)*(5 + 9*x + 5*x^2/2! + x^3/3!). - Peter Bala, Oct 15 2019
Antidiagonals of convolution matrix of Table 1.3, p. 397, of Hoggatt and Bicknell. - Tom Copeland, Dec 25 2019
Also the convolution triangle of A120588(n) = A000108(n-1) for n > 0. - Peter Luschny, Oct 07 2022

			Triangle begins:
  ---+-----------------------------------
  n\k|   1    2    3    4    5    6    7
  ---+-----------------------------------
   1 |   1
   2 |   1    1
   3 |   2    2    1
   4 |   5    5    3    1
   5 |  14   14    9    4    1
   6 |  42   42   28   14    5    1
   7 | 132  132   90   48   20    6    1
From _Peter Bala_, Feb 17 2025: (Start)
The array factorizes as an infinite product (read from right to left) of triangular arrays:
  / 1               \        / 1              \ / 1              \ / 1             \
  | 1    1           |       | 0   1          | | 0  1           | | 1  1          |
  | 2    2   1       | = ... | 0   0   1      | | 0  1   1       | | 1  1  1       |
  | 5    5   3   1   |       | 0   0   1  1   | | 0  1   1  1    | | 1  1  1  1    |
  |14   14   9   4  1|       | 0   0   1  1  1| | 0  1   1  1  1 | | 1  1  1  1  1 |
  |...               |       |...             | |...             | |...            |
See Bala, Example 2.1. (End)

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On One-Parameter Catalan Arrays, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles, arXiv:math/0109108 [math.NT], 2001.
Peter Bala, Factorisations of some Riordan arrays as infinite products
Jean-Luc Baril and Paul Barry, Two kinds of partial Motzkin paths with air pockets, arXiv:2212.12404 [math.CO], 2022.
Paul Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv preprint arXiv:1107.5490 [math.CO], 2011.
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 Central Coefficients of Bell Matrices, J. Int. Seq. 14 (2011) # 11.4.3 example 6.
Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.
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, Embedding structures associated with Riordan arrays and moment matrices, arXiv preprint arXiv:1312.0583 [math.CO], 2013.
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, 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, The second production matrix of a Riordan array, arXiv:2011.13985 [math.CO], 2020.
Paul Barry, A Riordan array family for some integrable lattice models, arXiv:2409.09547 [math.CO], 2024. See p. 9.
Paul Barry, Extensions of Riordan Arrays and Their Applications, Mathematics (2025) Vol. 13, No. 2, 242. See p. 13.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 15, 29.
Paul Barry and A. Hennessy, Meixner-Type Results for Riordan Arrays and Associated Integer Sequences, J. Int. Seq. 13 (2010) # 10.9.4.
Paul Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
A. Bernini, M. Bouvel and L. Ferrari, Some statistics on permutations avoiding generalized patterns, PU.M.A. Vol. 18 (2007), No. 3-4, pp. 223-237.
S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
Fangfang Cai, Qing-Hu Hou, Yidong Sun and Arthur L.B. Yang, Combinatorial identities related to 2X2 submatrices of recursive matrices, arXiv:1808.05736 [math.CO], 2018.
David Callan, A recursive bijective approach to counting permutations..., arXiv:math/0211380 [math.CO], 2002.
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
Matteo Cervetti and Luca Ferrari, Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse into the Matching Pattern Poset, Annals of Combinatorics (2022).
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], 2024. See p. 6.
Gi-Sang Cheon, Hana Kim and Louis W. Shapiro, Combinatorics of Riordan arrays with identical A and Z sequences, Discrete Math., 312 (2012), 2040-2049.
Gi-Sang Cheon, S.-T. Jin and L. W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Volume 491, 15 February 2016, Pages 123-137; Proceedings of the 19th ILAS Conference, Seoul, South Korea 2014.
Lapo Cioni and Luca Ferrari, Preimages under the Queuesort algorithm, arXiv preprint arXiv:2102.07628 [math.CO], 2021; Discrete Math., 344 (2021), #112561.
Emeric 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.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Peter M. Higgins, Combinatorial results for semigroups of order-preserving mappings, Math. Proc. Camb. Phil. Soc. 113 (1993), 281-296. [From _Abdullahi Umar_, Oct 02 2008]
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.
JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, On 102-avoiding inversion sequences, arXiv:2506.02985 [math.CO], 2025. See p. 13.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan numbers, The Fibonacci Quart. 38 (2000) 408-19.
P. J. Larcombe and D. R. French, The Catalan number k-fold self-convolution identity: the original formulation, Journal of Combinatorial Mathematics and Combinatorial Computing 46 (2003) 191-204.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See p. 12.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
D. Merlini, R. Sprugnoli and M. C. Verri, An algebra for proper generating trees
J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns, arXiv:math/9808080 [math.CO], 1998; Also Adv. in Appl. Math. 17 (1996), no. 4, 381--407. MR1422065 (97j:05003).
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.
J. M. Pallo, Enumerating, Ranking and Unranking Binary Trees, The Computer Journal, Volume 29, Issue 2, 1986, Pages 171-175.
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. 264.
A. Reifegerste, On the diagram of 132-avoiding permutations, arXiv:math/0208006 [math.CO], 2002.
A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
Yuriy Shablya, Dmitry Kruchinin and Vladimir Kruchinin, Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application, Mathematics (2020) Vol. 8, No. 6, 962.
Yidong Sun and Fei Ma, Four transformations on the Catalan triangle, arXiv preprint arXiv:1305.2017 [math.CO], 2013.
Yidong Sun and Fei Ma, Some new binomial sums related to the Catalan triangle, Electronic Journal of Combinatorics 21(1) (2014), #P1.33.
A. Umar, Some combinatorial problems in the theory of symmetric inverse semigroups, Algebra Disc. Math. 9 (2010) 115-126.
Sheng-Liang Yang and L. J. Wang, Taylor expansions for the m-Catalan numbers, Australasian Journal of Combinatorics, Volume 64(3) (2016), Pages 420-431.
S.-n. Zheng and S.-l. Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.

Rows of Catalan triangle A009766 read backwards.
a(n, 1) = A000108(n-1). Row sums = A000108(n) (Catalan).
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.
Cf. A116364 (row squared sums), A120588.

a033184 n k = a033184_tabl !! (n-1) !! (k-1)
a033184_row n = a033184_tabl !! (n-1)
a033184_tabl = map reverse a009766_tabl
-- Reinhard Zumkeller, Feb 19 2014

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

a := proc(n,k) if k<=n then k*binomial(2*n-k,n)/(2*n-k) else 0 fi end: seq(seq(a(n,k),k=1..n),n=1..10);
# Uses function PMatrix from A357368. Adds row and column for n, k = 0.
PMatrix(10, n -> binomial(2*(n-1), n-1) / n); # Peter Luschny, Oct 07 2022

nn = 10; c = (1 - (1 - 4 x)^(1/2))/(2 x); f[list_] := Select[list, # > 0 &]; Map[f, Drop[CoefficientList[Series[y x c/(1 - y x c), {x, 0, nn}], {x, y}],1]] //Flatten (* Geoffrey Critzer, Jan 31 2012 *)
Flatten[Reverse /@ NestList[Append[Accumulate[#], Last[Accumulate[#]]] &, {1}, 9]] (* Birkas Gyorgy, May 19 2012 *)
T[1, 1] := 1; T[n_, k_]/;1<=k<=n := T[n, k] = T[n-1, k-1]+T[n, k+1]; T[n_, k_] := 0; Flatten@Table[T[n, k], {n, 1, 10}, {k, 1, n}] (* Oliver Seipel, Dec 31 2024 *)

T(n,k)=binomial(2*(n-k)+k,n-k)*(k+1)/(n+1) \\ Paul D. Hanna, Aug 11 2008

# The simplest way to construct the triangle.
def A033184_triangle(n) :
    T = [0 for i in (0..n)]
    for k in (1..n) :
        T[k] = 1
        for i in range(k-1,0,-1) :
            T[i] = T[i-1] + T[i+1]
        print([T[i] for i in (1..k)])
A033184_triangle(10) # Peter Luschny, Jan 27 2012

Column k is the k-fold convolution of column 1. The triangle is also defined recursively by (i) entries outside triangle are 0, (ii) top left entry is 1, (iii) every other entry is sum of its east and northwest neighbor. - David Callan, Jul 25 2005
G.f.: t*x*c/(1-t*x*c), where c=(1-sqrt(1-4*x))/(2*x) is the g.f. of the Catalan numbers (A000108). - Emeric Deutsch, Mar 01 2004
T(n+1,k+1) = C(2*n-k, n-k)*(k+1)/(n+1). - Paul D. Hanna, Aug 11 2008
T((m+1)*n+r-1,m*n+r-1)*r/(m*n+r) = Sum_{k=1..n} (k/n)*T((m+1)*n-k-1,m*n-1)*T(r+k,r), n >= m > 1. - Vladimir Kruchinin, Mar 17 2011
T(n-1,m-1) = (m/n)*Sum_{k=1..n-m+1} (k*A000108(k-1)*T(n-k-1,m-2)), n >= m > 1. - Vladimir Kruchinin, Mar 17 2011
T(n,k) = C(2*n-k-1,n-k) - C(2*n-k-1,n-k-1). - Dennis P. Walsh, Mar 19 2012
T(n,k) = C(2*n-k,n)*k/(2*n-k). - Dennis P. Walsh, Mar 19 2012
T(n,k) = T(n,k-1) - T(n-1,k-2). - Dennis P. Walsh, Mar 19 2012
G.f.: 2*x*y / (1 + sqrt(1 - 4*x) - 2*x*y) = Sum_{n >= k > 0} T(n, k) * x^n * y^k. - Michael Somos, Jun 06 2016

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

A065601 Number of Dyck paths of length 2n with exactly 1 hill.

Original entry on oeis.org

0, 1, 0, 2, 4, 13, 40, 130, 432, 1466, 5056, 17672, 62460, 222853, 801592, 2903626, 10582816, 38781310, 142805056, 528134764, 1960825672, 7305767602, 27307800400, 102371942932, 384806950624, 1450038737668, 5476570993440, 20727983587220, 78606637060012

Offset: 0

N. J. A. Sloane, Dec 02 2001

Convolution of A000957(n) with itself gives a(n-1).

Alois P. Heinz, Table of n, a(n) for n = 0..500
Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
S. Kitaev, J. Remmel and M. 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, Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)

2nd column of A065600. Cf. A000957.

b:= proc(x, y, h, z) option remember;
     `if`(x<0 or y b(n$2, true$2):
seq(a(n), n=0..30);  # Alois P. Heinz, May 10 2012
# second Maple program:
series(((1-sqrt(1-4*x))/(3-sqrt(1-4*x)))^2/x, x=0, 30);  # Mark van Hoeij, Apr 18 2013

CoefficientList[Series[((1-Sqrt[1-4*x])/(3-Sqrt[1-4*x]))^2/x, {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)
Table[Sum[(-1)^j*(j+1)*(j+2)*Binomial[2*n-1-j,n],{j,0,n-1}]/(n+1),{n,0,30}] (* Vaclav Kotesovec, May 18 2015 *)

Reference gives g.f.'s.
Conjecture: 2*(n+1)*a(n) +(-3*n+2)*a(n-1) +2*(-9*n+19)*a(n-2) +4*(-2*n+3)*a(n-3)=0. - R. J. Mathar, Dec 10 2013
a(n) ~ 2^(2*n+3) / (27 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014

More terms from Emeric Deutsch, Dec 03 2001

A101371 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves at level 1.

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 7, 4, 0, 1, 34, 14, 6, 0, 1, 171, 72, 21, 8, 0, 1, 905, 370, 114, 28, 10, 0, 1, 4952, 1995, 597, 160, 35, 12, 0, 1, 27802, 11064, 3278, 852, 210, 42, 14, 0, 1, 159254, 62774, 18420, 4762, 1135, 264, 49, 16, 0, 1, 927081, 362614, 105618, 27104, 6455, 1446, 322, 56, 18, 0, 1

Offset: 0

Emeric Deutsch, Jan 14 2005

Row n has n+1 terms.

			Triangle begins:
    1;
    0,  1;
    2,  0,  1;
    7,  4,  0, 1;
   34, 14,  6, 0, 1;
  171, 72, 21, 8, 0, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

Columns k=0..2 give A023053, A374835, A374836.
Row sums give A001764.
Cf. A065600.

T:=proc(n,k) if k<=n then sum((-1)^i*(k+i+1)*binomial(k+i,i)*binomial(3*n-2*k-2*i,n-k-i)/(2*n-k-i+1),i=0..n-k) else 0 fi end: for n from 0 to 10 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

t[n_, k_] := Sum[(-1)^i*(k + i + 1)/(2n - k - i + 1)*Binomial[k + i, i]* Binomial[3n - 2k - 2i, n - k - i], {i, 0, n - k}]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 21 2013, after Maple *)

T(n, k) = sum(i=0, n-k, (-1)^i*(k+i+1)*binomial(k+i, i)*binomial(3*n-2*k-2*i, n-k-i)/(2*n-k-i+1)); \\ Andrew Howroyd, Nov 06 2017

T(n, k) = Sum_{i=0..n-k} (-1)^i*((k+i+1)/(2n-k-i+1)) binomial(k+i, i) binomial(3n-2k-2i, n-k-i) for 0 <= k <= n.

G.f.: g/(1+z*g-t*z*g), where g = 1+z*g^3.

A127543 Triangle T(n,k), 0<=k<=n, read by rows given by :[ -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, -1, 1, 0, -1, 1, -1, 1, -1, 1, -2, 0, 2, -1, 1, -6, 2, 1, 3, -1, 1, -18, 5, 7, 2, 4, -1, 1, -57, 17, 19, 13, 3, 5, -1, 1, -186, 56, 64, 36, 20, 4, 6, -1, 1, -622, 190, 212, 124, 56, 28, 5, 7, -1, 1, -2120, 654, 722, 416, 198, 79, 37, 6, 8, -1, 1, -7338, 2282, 2494, 1434, 673, 287, 105, 47, 7, 9, -1, 1

Offset: 0

Philippe Deléham, Apr 01 2007

Riordan array (2/(3-sqrt(1-4*x)), (1-sqrt(1-4*x))/(3-sqrt(1-4*x))). - Philippe Deléham, Jan 27 2014

			Triangle begins:
    1;
   -1,  1;
    0, -1,  1;
   -1,  1, -1,  1;
   -2,  0,  2, -1,  1;
   -6,  2,  1,  3, -1,  1;
  -18,  5,  7,  2,  4, -1,  1;
  -57, 17, 19, 13,  3,  5, -1, 1;

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

A065600[n_, k_]:= If[k==n, 1, Sum[j*Binomial[k+j, j]*Binomial[2*(n-k-j), n-k]/(n-k-j), {j,0, Floor[(n-k)/2]}]];
A127543[n_, k_]:= A065600[n-1,k-1] - A065600[n-1,k];
Table[A127543[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, May 17 2021 *)

def A065600(n,k): return 1 if (k==n) else sum( j*binomial(k+j, j)*binomial(2*(n-k-j), n-k)/(n-k-j) for j in (0..(n-k)//2) )
def A127543(n,k): return A065600(n-1, k-1) - A065600(n-1, k)
flatten([[A127543(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 17 2021

T(n,k) = A065600(n-1,k-1) - A065600(n-1,k).
Sum_{k=0..n} T(n,k)*x^k = A127053(n), A126985(n), A127016(n), A127017(n), A126987(n), A126986(n), A126982(n), A126984(n), A126983(n), A000007(n), A000108(n), A000984(n), A007854(n), A076035(n), A076036(n), A127628(n), A126694(n), A115970(n) for n= -8,-7,...,8,9 respectively.
Sum_{j>=0} T(n,j)*A007318(j,k) = A106566(n,k).
Sum_{j>=0} T(n,j)*A038207(j,k) = A039599(n,k).
Sum_{j>=0} T(n,j)*A027465(j,k) = A116395(n,k).

A128937 Triangle formed by reading A039598 mod 2.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1

Offset: 0

Philippe Deléham, Apr 27 2007, May 02 2007

Also triangle formed by reading triangles A052179, A053121, A124575, A126075, A126093.

Also triangle formed by reading A065600 mod 2. - Philippe Deléham, Oct 15 2007

			Triangle begins:
  1;
  0, 1;
  1, 0, 1;
  0, 0, 0, 1;
  0, 0, 1, 0, 1;
  0, 1, 0, 0, 0, 1;
  1, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 0, 0, 0, 0, 1;
  0, 0, 0, 0, 0, 0, 1, 0, 1;
  0, 0, 0, 0, 0, 1, 0, 0, 0, 1;
  0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1;
  0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1;
  0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1;
  1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1; ...

Cf. A048896 (row sums).

A039598 := proc(n,k)
        binomial(2*n,n-k)-binomial(2*n,n-k-2) ;
end proc:
A128937 := proc(n,k)
        modp(A039598(n,k),2) ;
end proc: # R. J. Mathar, Apr 21 2021

Sum_{k=0..n} T(n,k) = A048896(n).
Sum_{k=0..n} T(n,k)*2^(n-k) = A101692(n). - Philippe Deléham, Oct 09 2007
Sum_{k=0..n} T(n,k)*2^k = A062878(n+1)/3. - Philippe Deléham, Aug 31 2009

A171224 Riordan array (f(x),x*f(x)) where f(x) is the g.f. of A117641.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 11, 6, 3, 0, 1, 42, 23, 9, 4, 0, 1, 167, 90, 36, 12, 5, 0, 1, 684, 365, 144, 50, 15, 6, 0, 1, 2867, 1518, 595, 204, 65, 18, 7, 0, 1, 12240, 6441, 2511, 858, 270, 81, 21, 8, 0, 1, 53043, 27774, 10782, 3672, 1155, 342, 98, 24, 9, 0, 1

Offset: 0

Philippe Deléham, Dec 05 2009

			Triangle begins
    1;
    0,  1;
    1,  0,  1;
    3,  2,  0,  1;
   11,  6,  3,  0,  1;
   42, 23,  9,  4,  0,  1;
  167, 90, 36, 12,  5,  0,  1;
  ...
Production array begins
    0,  1;
    1,  0,  1;
    3,  1,  0,  1;
    9,  3,  1,  0,  1;
   27,  9,  3,  1,  0,  1;
   81, 27,  9,  3,  1,  0,  1;
  243, 81, 27,  9,  3,  1,  0,  1;
  ... - _Philippe Deléham_, Mar 04 2013

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

Cf. A053121, A097609, A065600.

[[((k+1)/(n+1))*(&+[3^(n-k-2*j)*Binomial(n+1,j)*Binomial(n-k-j-1, n-k-2*j): j in [0..Floor((n-k)/2)]]): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Apr 04 2019

T[n_, k_]:= (k+1)/(n+1)*Sum[3^(n-k-2*j)*Binomial[n+1,j]*Binomial[n-k-j-1, n-k-2*j], {j, 0, Floor[(n-k)/2]}]; Table[T[n, k], {n,0,10}, {k,0,n} ]//Flatten (* G. C. Greubel, Apr 04 2019 *)

T(n,k):=(k+1)/(n+1)*sum(3^(n-k-2*j)*binomial(n+1,j)*binomial(n-k-j-1,n-k-2*j),j,0,floor((n-k)/2)); /* Vladimir Kruchinin, Apr 04 2019 */

{T(n,k) = ((k+1)/(n+1))*sum(j=0, floor((n-k)/2), 3^(n-k-2*j) *binomial(n+1,j)*binomial(n-k-j-1, n-k-2*j))}; \\ G. C. Greubel, Apr 04 2019

[[((k+1)/(n+1))*sum(3^(n-k-2*j)*binomial(n+1,j)*binomial(n-k-j-1, n-k-2*j) for j in (0..floor((n-k)/2))) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Apr 04 2019

Sum_{k=0..n} T(n,k)*x^k = A117641(n), A033321(n), A007317(n+1), A002212(n+1), A026378(n+1) for x = 0, 1, 2, 3, 4 respectively.
Triangle equals B*A065600*B^(-1) = B^2*A097609*B^(-2) = B^3*A053121*B^(-3), product considered as infinite lower triangular arrays and B = A007318. - Philippe Deléham, Dec 08 2009
T(n,k) = T(n-1,k-1) + Sum_{i>=0} T(n-1,k+1+i)*3^i, T(0,0) = 1. - Philippe Deléham, Feb 23 2012
T(n,k) = ((k+1)/(n+1))*Sum_{j=0..floor((n-k)/2)} 3^(n-k-2*j)*C(n+1,j)*C(n-k-j-1,n-k-2*j). - Vladimir Kruchinin, Apr 04 2019

Terms a(55) onward added by G. C. Greubel, Apr 04 2019

A124394 Inverse of Fine number renewal array.

Original entry on oeis.org

1, 0, 1, -1, 0, 1, -2, -2, 0, 1, -3, -4, -3, 0, 1, -4, -5, -6, -4, 0, 1, -5, -4, -6, -8, -5, 0, 1, -6, 0, 0, -6, -10, -6, 0, 1, -7, 8, 14, 8, -5, -12, -7, 0, 1, -8, 21, 36, 36, 20, -3, -14, -8, 0, 1, -9, 40, 63, 72, 65, 36, 0, -16, -9, 0, 1

Offset: 0

Paul Barry, Oct 30 2006

Inverse of A065600. Row sums are A057681(n+1). Diagonal sums are A124395.

			Triangle begins
1,
0, 1,
-1, 0, 1,
-2, -2, 0, 1,
-3, -4, -3, 0, 1,
-4, -5, -6, -4, 0, 1,
-5, -4, -6, -8, -5, 0, 1,
-6, 0, 0, -6, -10, -6, 0, 1

Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2); Number triangle T(n,k)=sum{j=0..k+1, C(k+1,j)C(n-j+k+1,2k+1)(-2)^j};

A294527 Number of Dyck paths of length 2n with exactly 2 hills.

Original entry on oeis.org

0, 0, 1, 0, 3, 6, 21, 66, 220, 744, 2562, 8942, 31569, 112530, 404445, 1464042, 5332872, 19532688, 71893470, 265778040, 986416614, 3674092044, 13729259586, 51455182260, 193369903608, 728504292576, 2750904025276, 10409856537786, 39470613237645, 149935171349546

Offset: 0

Eric M. Schmidt, Nov 01 2017

nonn

Dun Qiu and Jeffrey B. Remmel, Quadrant marked mesh patterns in 123-avoiding permutations, arXiv:1705.00164 [math.CO], 2017, p. 28.

Column k=2 of A065600. Cf. A000957, A065601.

a[n_] := Which[n>2, Sum[(i Binomial[i+2, i] Binomial[2n-2i-4, n-2])/(n-i-2), {i, 0, (n-2)/2}], n == 2, 1, True, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 27 2018 *)

Conjecture: 2*(3*n-5) *(n-2) *(3*n+11) *(n+1) *a(n) -(3*n+11) *(n-3) *(21*n^2-35*n+10) *a(n-1) -2*(3*n+11) *(n-1) *(2*n-1) *(3*n-2) *a(n-2)= 0. - R. J. Mathar, Jun 24 2018

A097877 Triangle read by rows: T(n,k) is the number of Dyck n-paths with k large components, 0 <= k <= n/2.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 12, 1, 1, 34, 7, 1, 98, 32, 1, 1, 294, 124, 10, 1, 919, 448, 61, 1, 1, 2974, 1576, 298, 13, 1, 9891, 5510, 1294, 99, 1, 1, 33604, 19322, 5260, 583, 16, 1, 116103, 68206, 20595, 2960, 146, 1, 1, 406614, 242602, 78954, 13704, 1006, 19, 1, 1440025

Offset: 0

David Callan, Sep 21 2004

A prime Dyck path is one with exactly one return to ground level. Every nonempty Dyck path decomposes uniquely as a concatenation of prime Dyck paths, called its components. For example, UUDDUD has 2 components: UUDD and UD, of semilength 2 and 1 respectively. A large component is one of semilength >= 2.

Conjecture: This is the statistic "indegree" of elements in Pallo's comb posets. For the statistic "outdegree", see A009766. - F. Chapoton, Apr 18 2023

			T(3,1) = 4 because each of the 5 Dyck paths of semilength 3 has one large component except for UDUDUD, which has none.
Table begins:
  \ k 0, 1, 2, ...
  n\ ____________________
  0 | 1;
  1 | 1;
  2 | 1,   1;
  3 | 1,   4;
  4 | 1,  12,   1;
  5 | 1,  34,   7;
  6 | 1,  98,  32,  1;
  7 | 1, 294, 124, 10;
  8 | 1, 919, 448, 61, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
J. M. Pallo, Right-arm rotation distance between binary trees, Inform. Process. Lett., 87(4):173-177, 2003.

The Fine distribution (A065600) counts Dyck paths by number of small components (= number of low peaks).

Cf. A000108, A009766.

G.f.: 2/(1 + t*(1 - 4*z)^(1/2) + (1 - 2*z)(1-t)) = Sum_{n>=0, k>=0} T(n, k) z^n t^k satisfies (1-z)*G = 1 + z*t*(CatalanGF[z]-1)*G. The gf for Dyck paths (A000108) with z marking semilength is CatalanGF[z]:=(1 - sqrt[1 - 4*z])/(2*z). Hence the gf for prime Dyck paths is z*CatalanGF[z] and the gf for non-UD prime Dyck paths is S(z):= z*CatalanGF[z]-z. For fixed k, the gf for (T(n, k))_{n>=0} is S(z)^k/(1-z)^(k+1). This is clear because 1/(1-z) is the gf for all-UD Dyck paths (including the empty one) and a Dyck path with k large components is a product (uniquely) of an all-UD, a non-UD prime, an all-UD, a non-UD prime, ... with k non-UD primes and k+1 all-UDs.

cp's OEIS Frontend

A033184 Catalan triangle A009766 transposed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

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

A065601 Number of Dyck paths of length 2n with exactly 1 hill.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A101371 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves at level 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A127543 Triangle T(n,k), 0<=k<=n, read by rows given by :[ -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

Programs

Mathematica

Sage

Formula

A128937 Triangle formed by reading A039598 mod 2.

Views

Author

Keywords

Comments

Examples

Crossrefs