A121988 -id:A121988 - cp's OEIS frontend

A007317 Binomial transform of Catalan numbers.

1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, 223191, 974427, 4302645, 19181100, 86211885, 390248055, 1777495635, 8140539950, 37463689775, 173164232965, 803539474345, 3741930523740, 17481709707825, 81912506777200, 384847173838501, 1812610804416698

Offset: 1

N. J. A. Sloane, Mira Bernstein

Partial sums of A002212 (the restricted hexagonal polyominoes with n cells). Number of Schroeder paths (i.e., consisting of steps U=(1,1),D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n-2,0), with no peaks at even level. Example: a(3)=5 because among the six Schroeder paths from (0,0) to (4,0) only UUDD has a peak at an even level. - Emeric Deutsch, Dec 06 2003
Number of binary trees of weight n where leaves have positive integer weights. Non-commutative Non-associative version of partitions of n. - Michael Somos, May 23 2005
Appears also as the number of Euler trees with total weight n (associated with even switching class of matrices of order 2n). - David Garber, Sep 19 2005
Number of symmetric hex trees with 2n-1 edges; also number of symmetric hex trees with 2n-2 edges. A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference). A hex tree is symmetric if it is identical with its reflection in a bisector through the root. - Emeric Deutsch, Dec 19 2006
The Hankel transform of [1, 2, 5, 15, 51, 188, ...] is [1, 1, 1, 1, 1, ...], see A000012 ; the Hankel transform of [2, 5, 15, 51, 188, 731, ...] is [2, 5, 13, 34, 89, ...], see A001519. - Philippe Deléham, Dec 19 2006
a(n) = number of 321-avoiding partitions of [n]. A partition is 321-avoiding if the permutation obtained from its canonical form (entries in each block listed in increasing order and blocks listed in increasing order of their first entries) is 321-avoiding. For example, the only partition of [5] that fails to be 321-avoiding is 15/24/3 because the entries 5,4,3 in the permutation 15243 form a 321 pattern. - David Callan, Jul 22 2008
The sequence 1,1,2,5,15,51,188,... has Hankel transform A001519. - Paul Barry, Jan 13 2009
From Gary W. Adamson, May 17 2009: (Start)
  Equals INVERT transform of A033321: (1, 1, 2, 6, 21, 79, 311, ...).
  Equals INVERTi transform of A002212: (1, 3, 10, 36, 137, ...).
  Convolved with A026378, (1, 4, 17, 75, 339, ...) = A026376: (1, 6, 30, 144, ...)
(End)
a(n) is the number of vertices of the composihedron CK(n). The composihedra are a sequence of convex polytopes used to define maps of certain homotopy H-spaces. They are cellular quotients of the multiplihedra and cellular covers of the cubes. - Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009
a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps at level 0 come in 2 colors and those at a higher level come in 3 colors. Example: a(4)=15 because we have 2^3 = 8 paths of shape UHD, 2 paths of shape HUD, 2 paths of shape UDH, and 3 paths of shape UHD; here U=(1,1), H=(1,0), and D=(1,-1). - Emeric Deutsch, May 02 2011
REVERT transform of (1, 2, -3, 5, -8, 13, -21, 34, ... ) where the entries are Fibonacci numbers, A000045. Equivalently, coefficients in the series reversion of x(1-x)/(1+x-x^2). This means that the substitution of the gf (1-x-(1-6x+5x^2)^(1/2))/(2(1-x)) for x in x(1-x)/(1+x-x^2) will simplify to x. - David Callan, Nov 11 2012
The number of plane trees with nodes that have positive integer weights and whose total weight is n. - Brad R. Jones, Jun 12 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)].
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)
Starting with offset 0, a(n) is also the number of Schröder paths of semilength n avoiding UH (an up step directly followed by a long horizontal step). Example: a(2)=5 because among the six possible Schröder paths of semilength 2 only UHD contains UH. - Valerie Roitner, Jul 23 2020

			a(3)=5 since {3, (1+2), (1+(1+1)), (2+1), ((1+1)+1)} are the five weighted binary trees of weight 3.
G.f. = x + 2*x^2 + 5*x^3 + 15*x^4 + 51*x^5 + 188*x^6 + 731*x^7 + 2950*x^8 + 12235*x^9 + ... _Michael Somos_, Jan 17 2018

J. Brunvoll et al., Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq. 15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..200
Roland Bacher and David Garber, Spindle-configurations of skew lines, arXiv:math/0205245 [math.GT], 2002-2005.
Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks, arXiv:2308.09344 [math.CO], 2023.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, On the Central Antecedents of Integer (and Other) Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010) # 10.8.2.
Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, 2015.
Janusz Brzozowski and Marek Szykula, Large Aperiodic Semigroups, arXiv preprint arXiv:1401.0157 [cs.FL], 2013-2014.
David Callan, Pattern avoidance in "flattened" partitions , arXiv:0802.2275 [math.CO], 2008.
H. Cambazard and N. Catusse, Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane, arXiv preprint arXiv:1512.06649 [cs.DS], 2015-2017.
Giulio Cerbai, Pattern-avoiding modified ascent sequences, arXiv:2401.10027 [math.CO], 2024. See p. 17.
Giulio Cerbai, Anders Claesson, Luca Ferrari, and Einar Steingrímsson, Sorting with pattern-avoiding stacks: the 132-machine, arXiv:2006.05692 [math.CO], 2020.
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.
Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
S. J. Cyvin et al., Enumeration and classification of benzenoid systems. 32. Normal perifusenes with two internal vertices, J. Chem. Inform. Comput. Sci., 32 (1992), 532-540.
S. J. Cyvin et al., Graph-theoretical studies on fluoranthenoids and fluorenoids:enumeration of some catacondensed systems, J. Molec. Struct. (Theochem), 285 (1993), 179-185.
S. J. Cyvin et al., Enumeration and Classification of Certain Polygonal Systems Representing Polycyclic Conjugated Hydrocarbons: Annelated Catafusenes, J. Chem. Inform. Comput. Sci., 34 (1994), 1174-1180.
Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Francesc Fite, Kiran S. Kedlaya, Victor Rotger, and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 2011-2012.
S. Forcey, Quotients of the multiplihedron as categorified associahedra,Homotopy, Homology and Applications, vol. 10(2), 227-256, 2008. [From Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009]
Ira M. Gessel and Jang Soo Kim, A note on 2-distant noncrossing partitions and weighted Motzkin paths, arXiv:1003.5301 [math.CO], 2010.
Ira M. Gessel and Jang Soo Kim, A note on 2-distant noncrossing partitions and weighted Motzkin paths, Discrete Math. 310 (2010), no. 23, 3421--3425. MR2721104 (2011j:05350). See Eq. (1). - _N. J. A. Sloane_, Jul 05 2014
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019) Article 111705. doi:10.1016/j.disc.2019.111705
Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 18-19.
U. Grude, Java ist eine Sprache: Rekursive Unterprogramme. See page 4.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Frank Harary and Ronald C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 124
Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Hana Kim and R. P. Stanley, A refined enumeration of hex trees and related polynomials, Preprint 2015.
Jang Soo Kim, Bijections on two variations of noncrossing partitions, Discrete Math., 311 (2011), 1057-1063.
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
Toufik Mansour and Mark Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 22 2012
Igor Pak, Partition identities and geometric bijections, Proc. Amer. Math. Soc. 132 (2004), 3457-3462.
Lara K. Pudwell, Ascent sequences and the binomial convolution of Catalan numbers, arXiv:1408.6823 [math.CO], 2014.
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
Valerie Roitner, The vectorial kernel method for walks with longer steps, arXiv:2008.02240 [math.CO], 2020.
N. J. A. Sloane, Transforms
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
Makhin Thitsa and W. Steven Gray, On the Radius of Convergence of Interconnected Analytic Nonlinear Input-Output Systems, SIAM Journal on Control and Optimization, Vol. 50, No. 5, 2012, pp. 2786-2813. - From _N. J. A. Sloane_, Dec 26 2012
S. H. F. Yan, Schröder paths and Pattern Avoiding Partitions, Int. J. Contemp. Math. Sciences, Vol. 4, no. 20, pp. 979-986, 2009.

See A181768 for another version. - N. J. A. Sloane, Nov 12 2010
First column of triangle A104259. Row sums of absolute values of A091699.
Number of vertices of multiplihedron A121988.
m-th binomial transform of the Catalan numbers: A126930 (m = -2), A005043 (m = -1), A000108 (m = 0), A064613 (m = 2), A104455 (m = 3), A104498 (m = 4) and A154623 (m = 5).
Cf. A055879, A033321, A026376, A026378, A059346, A000045, A000957, A057078,  A091867, A104597, A249548, A162326.

G := (1-sqrt(1-4*z/(1-z)))*1/2: Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 1 .. 26); # Emeric Deutsch, Aug 12 2007
seq(round(evalf(JacobiP(n-1,1,-n-1/2,9)/n,99)),n=1..25); # Peter Luschny, Sep 23 2014

Rest@ CoefficientList[ InverseSeries[ Series[(y - y^2)/(1 + y - y^2), {y, 0, 26}], x], x] (* then A(x)=y(x); note that InverseSeries[Series[y-y^2, {y, 0, 24}], x] produces A000108(x) *) (* Len Smiley, Apr 10 2000 *)
Range[0, 25]! CoefficientList[ Series[ Exp[ 3x] (BesselI[0, 2x] - BesselI[1, 2x]), {x, 0, 25}], x] (* Robert G. Wilson v, Apr 15 2011 *)
a[n_] := Sum[ Binomial[n, k]*CatalanNumber[k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 07 2012 *)
Rest[CoefficientList[Series[3/2 - (1/2) Sqrt[(1 - 5 x)/(1 - x)], {x, 0, 40}], x]] (* Vincenzo Librandi, Nov 03 2014 *)
Table[Hypergeometric2F1[1/2, -n+1, 2, -4], {n, 1, 30}] (* Vaclav Kotesovec, May 12 2022 *)

{a(n) = my(A); if( n<2, n>0, A=vector(n); for(j=1,n, A[j] = 1 + sum(k=1,j-1, A[k]*A[j-k])); A[n])}; /* Michael Somos, May 23 2005 */

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

/* Offset = 0: */ {a(n)=local(A=1+x);for(i=1,n, A=sum(m=0,n, x^m*sum(k=0,m,A^k)+x*O(x^n))); polcoeff(A,n)} \\ Paul D. Hanna

(n+2)*a(n+2) = (6n+4)*a(n+1) - 5n*a(n).
G.f.: 3/2-(1/2)*sqrt((1-5*x)/(1-x)) [Gessel-Kim]. - N. J. A. Sloane, Jul 05 2014
G.f. for sequence doubled: (1/(2*x))*(1+x-(1-x)^(-1)*(1-x^2)^(1/2)*(1-5*x^2)^(1/2)).
a(n) = hypergeom([1/2, -n], [2], -4), n=0, 1, 2...; Integral representation as n-th moment of a positive function on a finite interval of the positive half-axis: a(n)=int(x^n*sqrt((5-x)/(x-1))/(2*Pi), x=1..5), n=0, 1, 2... This representation is unique. - Karol A. Penson, Sep 24 2001
a(1)=1, a(n)=1+sum(i=1, n-1, a(i)*a(n-i)). - Benoit Cloitre, Mar 16 2004
a(n) = Sum_{k=0..n} (-1)^k*3^(n-k)*binomial(n, k)*binomial(k, floor(k/2)) [offset 0]. - Paul Barry, Jan 27 2005
G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=x-(1-x)(y-y^2). - Michael Somos, May 23 2005
G.f. A(x) satisfies 0=f(x, A(x), A(A(x))) where f(x, y, z)=x(z-z^2)+(x-1)y^2 . - Michael Somos, May 23 2005
G.f. (for offset 0): (-1+x+(1-6*x+5*x^2)^(1/2))/(2*(-x+x^2)).
G.f. =z*c(z/(1-z))/(1-z) = 1/2 - (1/2)sqrt(1-4z/(1-z)), where c(z)=(1-sqrt(1-4z))/(2z) is the Catalan function (follows from Michael Somos' first comment). - Emeric Deutsch, Aug 12 2007
G.f.: 1/(1-2x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-.... (continued fraction). - Paul Barry, Apr 19 2009
a(n) = Sum_{k, 0<=k<=n} A091965(n,k)*(-1)^k. - Philippe Deléham, Nov 28 2009
E.g.f.: exp(3x)*(I_0(2x)-I_1(2x)), where I_k(x) is a modified Bessel function of the first kind. - Emanuele Munarini, Apr 15 2011
If we prefix sequence with an additional term a(0)=1, g.f. is (3-3*x-sqrt(1-6*x+5*x^2))/(2*(1-x)). [See Kim, 2011] - N. J. A. Sloane, May 13 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows:
  2, 1, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, ...
  1, 1, 2, 1, 0, 0, ...
  1, 1, 1, 2, 1, 0, ...
  1, 1, 1, 1, 2, 1, ...
  1, 1, 1, 1, 1, 2, ...
  ... (End)
G.f. satisfies: A(x) = Sum_{n>=0} x^n * (1 - A(x)^(n+1))/(1 - A(x)); offset=0. - Paul D. Hanna, Nov 07 2011
G.f.: 1/x - 1/x/Q(0), where Q(k)= 1 + (4*k+1)*x/((1-x)*(k+1) - x*(1-x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
G.f.: (1-x - (1-5*x)*G(0))/(2*x*(1-x)), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-x) - 2*x*(1-x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 25 2013
Asymptotics (for offset 0): a(n) ~ 5^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 28 2013
G.f.: G(0)/(1-x), where G(k) = 1 + (4*k+1)*x/((k+1)*(1-x) - 2*x*(1-x)*(k+1)*(4*k+3)/(2*x*(4*k+3) + (2*k+3)*(1-x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2014
a(n) = JacobiP(n-1,1,-n-1/2,9)/n. - Peter Luschny, Sep 23 2014
0 = +a(n)*(+25*a(n+1) -50*a(n+2) +15*a(n+3)) +a(n+1)*(-10*a(n+1) +31*a(n+2) -14*a(n+3)) +a(n+2)*(+2*a(n+2) +a(n+3)) for all n in Z. - Michael Somos, Jan 17 2018
a(n+1) = (2/Pi) * Integral_{x = -1..1} (m + 4*x^2)^n*sqrt(1 - x^2) dx at m = 1. In general, the integral, qua sequence in n, gives the m-th binomial transform of the Catalan numbers. - Peter Bala, Jan 26 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

A158825 Square array of coefficients in the successive iterations of xC(x) = (1-sqrt(1-4x))/2 where C(x) is the g.f. of the Catalan numbers (A000108); read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 5, 1, 4, 12, 21, 14, 1, 5, 20, 54, 80, 42, 1, 6, 30, 110, 260, 322, 132, 1, 7, 42, 195, 640, 1310, 1348, 429, 1, 8, 56, 315, 1330, 3870, 6824, 5814, 1430, 1, 9, 72, 476, 2464, 9380, 24084, 36478, 25674, 4862, 1, 10, 90, 684, 4200, 19852, 67844, 153306, 199094, 115566, 16796

Offset: 1

Paul D. Hanna, Mar 28 2009, Mar 29 2009

			Square array of coefficients in iterations of x*C(x) begins:
  1,  1,   2,    5,    14,      42,      132,       429,       1430, ... A000108;
  1,  2,   6,   21,    80,     322,     1348,      5814,      25674, ... A121988;
  1,  3,  12,   54,   260,    1310,     6824,     36478,     199094, ... A158826;
  1,  4,  20,  110,   640,    3870,    24084,    153306,     993978, ... A158827;
  1,  5,  30,  195,  1330,    9380,    67844,    500619,    3755156, ... A158828;
  1,  6,  42,  315,  2464,   19852,   163576,   1372196,   11682348, ...;
  1,  7,  56,  476,  4200,   38052,   351792,   3305484,   31478628, ...;
  1,  8,  72,  684,  6720,   67620,   693048,   7209036,   75915708, ...;
  1,  9,  90,  945, 10230,  113190,  1273668,  14528217,  167607066, ...;
  1, 10, 110, 1265, 14960,  180510,  2212188,  27454218,  344320262, ...;
  1, 11, 132, 1650, 21164,  276562,  3666520,  49181418,  666200106, ...;
  1, 12, 156, 2106, 29120,  409682,  5841836,  84218134, 1225314662, ...;
  1, 13, 182, 2639, 39130,  589680,  8999172, 138755799, 2157976392, ...;
  1, 14, 210, 3255, 51520,  827960, 13464752, 221101608, 3660331064, ...;
  1, 15, 240, 3960, 66640, 1137640, 19640032, 342179672, 6007747368, ...;
  1, 16, 272, 4760, 84864, 1533672, 28012464, 516105720, 9578580504, ...;
ILLUSTRATE ITERATIONS.
       Let G(x) = x*C(x), then the first few iterations of G(x) are:
           G(x) = x +   x^2 +  2*x^3 +   5*x^4 +  14*x^5 + ...;
        G(G(x)) = x + 2*x^2 +  6*x^3 +  21*x^4 +  80*x^5 + ...;
     G(G(G(x))) = x + 3*x^2 + 12*x^3 +  54*x^4 + 260*x^5 + ...;
  G(G(G(G(x)))) = x + 4*x^2 + 20*x^3 + 110*x^4 + 640*x^5 + ...;
...
RELATED TRIANGLES.
The g.f. of column n is (g.f. of row n of A158830)/(1-x)^n
where triangle A158830 begins: 1;
      1,       0;
      2,       0,        0;
      5,       1,        0,        0;
     14,      10,        0,        0,       0;
     42,      70,        8,        0,       0,       0;
    132,     424,      160,        4,       0,       0,     0;
    429,    2382,     1978,      250,       1,       0,     0,   0;
   1430,   12804,    19508,     6276,     302,       0,     0,   0, 0;
   4862,   66946,   168608,   106492,   15674,     298,     0,   0, 0, 0;
  16796,  343772,  1337684,  1445208,  451948,   33148,   244,   0, 0, 0, 0;
  58786, 1744314, 10003422, 16974314, 9459090, 1614906, 61806, 162, 0, 0, 0, 0;
  ...
Triangle A158835 transforms one diagonal into the next:
       1;
       1,      1;
       4,      2,     1;
      27,     11,     3,    1;
     254,     94,    21,    4,   1;
    3062,   1072,   217,   34,   5,  1;
   45052,  15212,  2904,  412,  50,  6, 1;
  783151, 257777, 47337, 6325, 695, 69, 7, 1; ...
so that:
  A158835 * A158831 = A158832;
  A158835 * A158832 = A158833;
  A158835 * A158833 = A158834;
where the diagonals start:
  A158831 = [1, 1,  6,  54,  640,  9380,  163576,  3305484, ...];
  A158832 = [1, 2, 12, 110, 1330, 19852,  351792,  7209036, ...];
  A158833 = [1, 3, 20, 195, 2464, 38052,  693048, 14528217, ...];
  A158834 = [1, 4, 30, 315, 4200, 67620, 1273668, 27454218, ...].

Paul D. Hanna, Table of n, a(n), n = 1..1275 (rows 1..50)
Frédéric Chapoton and Vincent Pilaud, Shuffles of deformed permutahedra, multiplihedra, constrainahedra, and biassociahedra, arXiv:2201.06896 [math.CO], 2022. See p. 26.

Rows: A000108, A121988, A158826, A158827, A158828.
Columns: A000012, A000027, A002378, A160378.
Antidiagonal sums: A158829.
Diagonals: A158831, A158832, A158833, A158834.
Related triangles: A158830, A158835.
Variant: A122888.

Clear[row]; nmax = 12;
row[n_]:= row[n]= CoefficientList[Nest[(1-Sqrt[1-4#])/2&, x, n] + O[x]^(nmax+1), x] //Rest;
T[n_, k_]:= row[n][[k]];
Table[T[n-k+1, k], {n, nmax}, {k, n}]//Flatten (* Jean-François Alcover, Jul 13 2018, updated Aug 09 2018 *)

{T(n,k)= local(F=serreverse(x-x^2+O(x^(k+2))), G=x);
for(i=1, n, G=subst(F,x,G)); polcoeff(G,k)}

G.f. of column n = (g.f. of row n of A158830)/(1-x)^n.
Row k equals the first column of the k-th matrix power of Catalan triangle A033184; thus triangle A033184 transforms row n into row n+1 of this array (A158825). - Paul D. Hanna, Mar 30 2009
From G. C. Greubel, Apr 01 2021: (Start)
T(n, 1) = A000012(n),   T(n, 2) = A000027(n).
T(n, 3) = A002378(n),   T(n, 4) = A160378(n+1). (End)

A127632 Expansion of c(x*c(x)), where c(x) is the g.f. for A000108.

Original entry on oeis.org

1, 1, 3, 11, 44, 185, 804, 3579, 16229, 74690, 347984, 1638169, 7780876, 37245028, 179503340, 870374211, 4243141332, 20786340271, 102275718924, 505235129250, 2504876652190, 12459922302900, 62167152967680, 311040862133625

Offset: 0

Paul Barry, Jan 20 2007, Jan 25 2007

Old name was: Expansion of 1/(1 - x*c(x) * c(x*c(x))), where c(x) is the g.f. of A000108.
Hankel transform appears to be A075845.
Catalan transform of Catalan numbers. - Philippe Deléham, Jun 20 2007
Number of functions f:[1,n] -> [1,n] satisfying the condition that, for all i < j, f(j) - (j - i) is not in the interval [1, f(i) - 1]; see the Callan reference. - Joerg Arndt, May 31 2013
This is the number of intervals in the comb posets of Pallo. See the Pallo and Csar et al. references for the definition of these posets. For the proof, see the Aval et al. reference - F. Chapoton, Apr 06 2015
Construct a lower triangular array (T(n,k))n,k>=0 by putting the sequence of Catalan numbers as the first column of the array and completing the remaining columns using the recurrence T(n, k) = T(n, k-1) + T(n-1, k). This sequence will then be the leading diagonal of the array. - Peter Bala, May 13 2017
a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 231 and 4132. (A permutation is called uniquely sorted if it has exactly one preimage under West's stack-sorting map.  See the Defant link.) - Colin Defant, Jun 08 2019
a(n) is the number of 132-avoiding permutations of length 3*n whose disjoint cycle decomposition contains only 3-cycles (a,b,c) with a>b>c. See the Archer and Graves reference. - Alexander Burstein, Oct 21 2021

Alois P. Heinz, Table of n, a(n) for n = 0..1000
K. Archer and C. Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.
J.-C. Aval and F. Chapoton, Poset structures on (m+2)-angulations and polynomial bases of the quotient by Gm-quasisymmetric functions, Séminaire Lotharingien de Combinatoire, vol 77, article B77b.
Peter Bala, A note on the Catalan transform of a sequence
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
David Callan, A combinatorial interpretation of the Catalan transform of the Catalan numbers, arXiv:1111.0996 [math.CO], 2011.
David Callan, Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193 [math.CO], 2013.
S. Csar, R. Sengupta, and W. Suksompong, On a Subposet of the Tamari Lattice, arXiv preprint arXiv:1108.5690 [math.CO], 2011.
Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.
Tian-Xiao He and Louis W. Shapiro, Row sums and alternating sums of Riordan arrays, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95.
Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
J. M. Pallo, Right-arm rotation distance between binary trees, Inform. Process. Lett., 87(4):173-177, 2003.
Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832, table 1, {ud}.
S. Yakoubov, Pattern Avoidance in Extensions of Comb-Like Posets, arXiv preprint arXiv:1310.2979 [math.CO], 2013.

Row sums of number triangle A127631.

Cf. A127714, A075845, A000108, A009766, A344056, A344057, A121988.

a:= proc(n) option remember; `if`(n<3, [1, 1, 3][n+1],
      ((8*(4*n-11))*(4*n-5)*(4*n-9)*(2*n-5)*a(n-3)
      -(8*(4*n-5))*(n-1)*(22*n^2-94*n+99)*a(n-2)
      +8*n*(n-1)*(20*n^2-67*n+48)*a(n-1))/
      ((3*(4*n-9))*(n+1)*n*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 06 2015

a[n_] := Sum[m*(2*n-m-1)!*HypergeometricPFQ[{m/2+1/2, m/2, m-n}, {m, m-2*n+1}, 4]/(n!*(n-m)!), {m, 1, n}]; a[0]=1; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Jul 24 2012, after Vladimir Kruchinin *)
a[n_] := CatalanNumber[n - 1] HypergeometricPFQ[{3/2, 2, 1 - n}, {3, 2 - 2 n}, 4];
a[0] := 1; Table[a[n], {n, 0, 23}] (* Peter Luschny, May 12 2021 *)

a(n):=if n=0 then 1 else sum(m*sum(binomial(2*k-m-1,k-1)*binomial(2*n-k-1,n-1),k,m,n),m,1,n)/n; /* Vladimir Kruchinin, Oct 08 2011 */

{a(n)= if(n<1, n==0, polcoeff( serreverse( x*(1-x)^3*(1-x^3)/(1-x^2)^4 +x*O(x^n) ), n))} /* Michael Somos, May 04 2007 */

{a(n)= local(A); if(n<1, n==0, A= serreverse( x-x^2 +x*O(x^n) ); polcoeff( 1/(1 - subst(A, x, A)), n))} /* Michael Somos, May 04 2007 */

a(n) = A127714(n+1, 2n+1).
G.f. A(x) satisfies: 0 = 1 - A(x) + A(x)^2 * x * c(x) where c(x) is the g.f. of A000108.
G.f.: 2/(1 + sqrt(2 * sqrt(1 - 4*x) - 1)). - Michael Somos, May 04 2007
a(n) = Sum_{k=0..n} A106566(n, k)*A000108(k). - Philippe Deléham, Jun 20 2007
a(n) = (Sum_{m=1..n} (m*Sum_{k=m..n} binomial(2*k-m-1, k-1)*binomial(2*n-k-1, n-1)))/n, a(0)=1. - Vladimir Kruchinin, Oct 08 2011
Conjecture: 3*n*(n-1)*(4*n-9)*(n+1)*a(n) - 8*n*(n-1)*(20*n^2-67*n+48)*a(n-1) + 8*(4*n-5)*(n-1)*(22*n^2-94*n+99)*a(n-2) - 8*(4*n-11)*(4*n-5)*(4*n-9)*(2*n-5)*a(n-3) = 0. - R. J. Mathar, May 04 2018
a(n) ~ 2^(4*n - 1/2) / (sqrt(Pi) * n^(3/2) * 3^(n - 1/2)). - Vaclav Kotesovec, Aug 14 2018
From Alexander Burstein, Nov 21 2019: (Start)
G.f.: A(x) = 1 + x*c(x)^2*m(x*c(x)^2), where m(x) is the g.f. of A001006 and c(x) is the g.f. of A000108.
G.f.: A(x) satisfies: A(-x*A(x)^5) = 1/A(x). (End)
From Peter Luschny, May 12 2021: (Start)
a(n) = Catalan(n - 1) * hypergeom([3/2, 2, 1 - n], [3, 2 - 2*n], 4) for n >= 1.
a(n) = A344056(n) / A344057(n).  (End)
The G.f. satisfies the algebraic equation 0 = F^4*x - F^3 + 2*F^2 - 2*F + 1. - F. Chapoton, Oct 18 2021
D-finite with recurrence 3*n*(n-1)*(n+1)*a(n) -4*n*(7*n-2)*(n-1)*a(n-1) +8*(n-1)*(2*n^2+30*n-65)*a(n-2) +8*(56*n^3-520*n^2+1534*n-1445)*a(n-3) -32*(4*n-15)*(2*n-7)*(4*n-13)*a(n-4)=0. - R. J. Mathar, Aug 01 2022

Better name from David Callan, Jun 03 2013

cp's OEIS Frontend

A007317 Binomial transform of Catalan numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

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

A158825 Square array of coefficients in the successive iterations of x*C(x) = (1-sqrt(1-4*x))/2 where C(x) is the g.f. of the Catalan numbers (A000108); read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A127632 Expansion of c(x*c(x)), where c(x) is the g.f. for A000108.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A129442 Expansion of c(x)*c(x*c(x)) where c(x) is the g.f. of A000108.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A158826 Third iteration of x*C(x) where C(x) is the Catalan function (A000108).

Views

Author

Keywords

Comments

Links

A158825 Square array of coefficients in the successive iterations of xC(x) = (1-sqrt(1-4x))/2 where C(x) is the g.f. of the Catalan numbers (A000108); read by antidiagonals.

A129442 Expansion of c(x)c(xc(x)) where c(x) is the g.f. of A000108.

A243204 Expansion of 2x/((1-sqrt(1-2(1-sqrt(1-4x))))sqrt(1-2(1-sqrt(1-4x))) * sqrt(1-4*x)).