A000108 -id:A000108 - cp's OEIS frontend

A115139 Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108.

1, 1, 1, -1, 1, -2, 1, -3, 1, 1, -4, 3, 1, -5, 6, -1, 1, -6, 10, -4, 1, -7, 15, -10, 1, 1, -8, 21, -20, 5, 1, -9, 28, -35, 15, -1, 1, -10, 36, -56, 35, -6, 1, -11, 45, -84, 70, -21, 1, 1, -12, 55, -120, 126, -56, 7, 1, -13, 66, -165, 210, -126, 28, -1, 1, -14, 78, -220, 330, -252, 84, -8, 1, -15, 91, -286, 495, -462, 210, -36, 1

Offset: 1

Wolfdieter Lang, Jan 13 2006

This is a signed version of A011973 (Fibonacci polynomials) with different offset.
The sequence of row lengths is [1,1,2,2,3,3,4,4,5,5,6,6,...] = A008619(n-1), n>=1.
The row sums give the period 6 sequence [1,1,0,-1,-1,0,...] = A010892(n-1), n>=1.
The o.g.f. for the column m sequence (with leading zeros) is ((-1)^m)*x^(2*m+1)/(1-x)^(m+1).
The unsigned row sums give the Fibonacci numbers A000045(n-1), n>=1.
The row polynomial are P(n,x):= Sum_{m=0..ceiling(n/2)-1} a(n,m)*x^m = (sqrt(x)^(n-1))*S(n-1,1/sqrt(x)), n>=1, with Chebyshev's S(n,x) polynomials A049310.
These polynomials appear in the formula 1/c(x)^n = P(n+1,x) - x*P(n,x)*c(x), n>=1, with the o.g.f. c(x):=(1-sqrt(1-4*x))/(2*x) of A000108 (Catalan numbers). See the W. Lang reference, eqs. (1) and (2), p. 408, with P(n,x):=p(-n,x).
These polynomials also appear in the formula c(x)^n = (-P(n-1,x) + P(n,x)*c(x))/x^(n-1), n>=1, with the above given o.g.f. c(x) of A000108 (Catalan numbers). See the W. Lang reference, eq. (1), with P(n,x):=p(-n,x).
With offset n>=0 this array a(n,m) coincides with the row reversed coefficient table of Chebyshev's S-polynomials without interspersed zeros. See A049310 for the S(n,x) coefficient table with increasing powers of x.
The polynomials with this sequence as coefficients form the set of so-called "Catalan polynomials", having arisen from computations in looking at the problem of 'fitting' iterated generating function schemes to the Catalan sequence. A neighboring pair forms the basis of a first-order linear recurrence that generates, through a succession of iterated generating functions (polynomials in Z[x]), a predetermined number of Catalan numbers before 'failing' - see the Clapperton et al. 2008 reference in Utilitas Mathematica, where some of the essential mathematical properties of the Catalan polynomials are also listed (based mainly on existing results for Dickson and Chebyshev polynomials, to which they are related). - Peter J Larcombe, Sep 16 2008
In the Clapperton et al. 2008 Congressus Numerantium paper, a new class of nonlinear identities satisfied by Catalan polynomials are presented. They arise from the algebraic implementation of particular cases of a general root finding formulation due to Householder, of which the classic O(2) Newton-Raphson and O(3) Halley algorithms are special cases. The role of Catalan polynomials in forming Padé approximants to the Catalan sequence o.g.f. is also discussed. - Peter J Larcombe, Nov 02 2008
These polynomials appear in the following statements: (i) P(k+1,x)/P(k+2,x) is the g.f. of all ordered trees (Dyck paths) of height at most k; (ii) x^k/(P(k+1,x)*P(k+2,x)) is the g.f. of all ordered trees (Dyck paths) of height k. See the de Bruijn et al., the Kreweras, the Sedgewick and Flajolet (p. 258), and the Flajolet and Sedgewick (p. 326) references. - Emeric Deutsch, Jun 16 2011
For a mirrored, shifted version showing the relation of these coefficients to the Pascal triangle, Fibonacci, and other number triangles, see A030528. See also A053122 for a relation to Cartan matrices. (Cf. A011973, A169803, A115139, A092865, A098925, and A102426.) - Tom Copeland, Nov 04 2014
M. Sinan Kul, Dec 09 2015, observed that (in a rewritten form) Chebyshev's S polynomials A049310 are given by S(n, x) = Sum_{m=0..floor(n/2)} a(n+1, m)*x^(n-2*m), n >= 0. This formula is well known and can be proved from the S recurrence by induction using the recurrence for the binomial coefficients. - Wolfdieter Lang, Feb 01 2016
These are the coefficients of generalized Fibonacci polynomials (see link bellow). - Rigoberto Florez, Aug 28 2022

			The irregular triangle a(n, m) begins:
  n\m  0   1   2    3   4    5   6   7  8
  1:   1
  2:   1
  3:   1  -1
  4:   1  -2
  5:   1  -3   1
  6:   1  -4   3
  7:   1  -5   6   -1
  8:   1  -6  10   -4
  9:   1  -7  15  -10   1
  10:  1  -8  21  -20   5
  11:  1  -9  28  -35  15   -1
  12:  1 -10  36  -56  35   -6
  13:  1 -11  45  -84  70  -21   1
  14:  1 -12  55 -120 126  -56   7
  15:  1 -13  66 -165 210 -126  28  -1
  16:  1 -14  78 -220 330 -252  84  -8
  17:  1 -15  91 -286 495 -462 210 -36  1
  ... Reformatted and extended. - _Wolfdieter Lang_, Jan 27 2016
1/c(x) = P(2,x) - x*P(1,x)*c(x) = 1 - x*c(x), with the o.g.f. of A000108 (Catalan).
1/c(x)^2 = P(3,x) - x*P(2,x)*c(x) = (1-x) - x*c(x).
c(x)^2 = (-P(1,x) + P(2,x)*c(x))/x^1 = (-1 + 1*c(x))/x.
c(x)^3 = (-P(2,x) + P(3,x)*c(x))/x^2 = (-1 + (1-x)*c(x))/x^2.
P(3,x) = 1-x = x*S(2,1/sqrt(x)) with Chebyshev's S(2,y) = U(2,y/2) = y^2 - 1.

J. A. Clapperton, P. J. Larcombe and E. J. Fennessey, On iterated generating functions for integer sequences and Catalan polynomials, Utilitas Mathematica, 77 (2008), 3-33.
J. A. Clapperton, P. J. Larcombe, E. J. Fennessey and P. Levrie, A class of auto-identities for Catalan polynomials and Padé approximation, Congressus Numerantium, 189 (2008), 77-95.
N. G. de Bruijn, D. E. Knuth and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.
R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

Alois P. Heinz, Rows n = 1..200, flattened
Hong Duc Bui, Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials, arXiv:2504.09615 [cs.CG], 2025. See p. 3.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009.
R. Florez and J. C. Saunders, Irreducibility of generalized Fibonacci polynomials , Integers 22 (2022).
Atsushi Komaba, Hisashi Johno, and Kazunori Nakamoto, A novel statistical approach for two-sample testing based on the overlap coefficient, arXiv:2206.03166 [math.ST], 2022.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
Wolfdieter Lang, First 16 rows
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419.
Peter J. Larcombe and Eric J. Fennessey, A Non-Linear Identity for A Particular Class of Polynomial Families, Fibonacci Quart. 52 (2014), no. 1, 75-79. Mentions this sequence.

Cf. A011973, A030528, A053122, A092865, A098925, A102426, A115139, A169803.

seq(seq((-1)^k*binomial(n-k,k),k=0..floor(n/2)),n=0..16); # Peter Luschny, May 10 2016

p[x_, n_] := p[x, n] = p[x, n - 1] + x*p[x, n - 2];
p[x_, -1] = p[x_, 0] = 1; p[x_, 1] = 1 + x;
Flatten[ Table[ CoefficientList[p[-x, n - 1], x], {n, 0, 16}]]
(* Jean-François Alcover, Jun 20 2011 *)
Flatten[Map[CoefficientList[#,x]&, Table[Sum[Binomial[t - i, i] x^(i) (-1)^i, {i, 0, t}], {t, 1,15}]]] (* Rigoberto Florez, Aug 28 2022 *)

import math
L1 = [math.comb(t - i, i)*(-1)**i for t in range(16) for i in range(t)]
L1 = list(filter((0)._ne_, L1))
print(L1) # Rigoberto Florez, Sep 03 2022

a(n, m) = ((-1)^(m))*binomial(n-1-m, m), n>=1, m=0..ceiling(n/2)-1.
a(n, m) = [x^m]P(n,x), n>=1, m=0..ceiling(n/2)-1, with P(n,x) given above in terms of Chebyshev's S-polynomials.
P(n,x) = (u^(2*n) - v^(2*n))/(u^2 - v^2), where u and v are defined by u^2 + v^2 =1 and u*v = sqrt(x). Example: P(3,x) = (u^6 - v^6)/(u^2 - v^2) = u^4 + u^2*v^2 + v^4 = 1 - x. - Emeric Deutsch, Jun 16 2011
G.f.: 1/(1- x + y*x^2) = R(0)/2, where R(k) = 1 + 1/(1 - (2*k+1- x*y)*x/((2*k+2- x*y)*x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013
T(n, k) = GegenbauerC(k, (n+1)/2-k, -1) assuming the triangle (0,0) based. - Peter Luschny, May 10 2016

A003645 a(n) = 2^n * C(n+1), where C(n) = A000108(n) Catalan numbers.

Original entry on oeis.org

1, 4, 20, 112, 672, 4224, 27456, 183040, 1244672, 8599552, 60196864, 426008576, 3042918400, 21909012480, 158840340480, 1158600130560, 8496400957440, 62605059686400, 463277441679360, 3441489566760960, 25654740406763520, 191852841302753280, 1438896309770649600

Offset: 0

N. J. A. Sloane

Number of nonisomorphic unrooted unicursal planar maps with n+2 edges and exactly one vertex of valency 1 (unicursal means that exactly two vertices are of odd valency). - Valery A. Liskovets, Apr 07 2002
Total number of vertices in rooted Eulerian planar maps with n+1 edges.
Half the number of ways to dog-ear every page of an (n+1)-page book. - R. H. Hardin, Jun 21 2002
Convolution of A052701(n+1) with itself.
Number of Motzkin lattice paths with weights: 1 for up step, 4 for level step and 4 for down step. - Wenjin Woan, Oct 24 2004
The number of rooted bipartite n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005
Also the number of paths of length 2n+1 in a binary tree between two vertices that are one step away from each other. - David Koslicki (koslicki(AT)math.psu.edu), Nov 02 2010
2*a(n) for n > 1 is the number of increasing strict binary trees with 2n-1 nodes that simultaneously avoid 213 and 231 in the classical sense. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 22 2014

L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin. 54 (2000), 149-160.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

A. Claesson, S. Kitaev and A. de Mier, An involution on bicubic maps and beta(0,1)-trees, arXiv preprint arXiv:1210.3219 [math.CO], 2012. - From _N. J. A. Sloane_, Jan 01 2013
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.
Samuele Giraudo, Pluriassociative algebras II: The polydendriform operad and related operads, arXiv:1603.01394 [math.CO], 2016.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 652.
Anatol N. Kirillov, Notes on Schubert, Grothendieck and key polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 034, 56 p. (2016).
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 13.
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 209-221.
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., Vol. 36, No.4 (2006), pp. 364-387.
Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 11.
Youngja Park and SeungKyung Park, Enumeration of generalized lattice paths by string types, peaks, and ascents, Discrete Mathematics, Vol. 339, No. 11 (2016), pp. 2652-2659.
M. Z. Spivey and L. L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seq., Vol. 9 (2006), Article 06.1.1.

Cf. A069724, A069725, A090375.
Third row of array A102539.
Column of array A073165.
Cf. A000108, A052701, A195699.

[2^n*Binomial(2*n+3, n+1)/(2*n+3) : n in [0..30]]; // Wesley Ivan Hurt, Aug 23 2014

A003645:=n->2^n*binomial(2*n+3, n+1)/(2*n+3): seq(A003645(n), n=0..30); # Wesley Ivan Hurt, Aug 23 2014

Table[2^n CatalanNumber[n+1],{n,0,20}] (* Harvey P. Dale, May 07 2013 *)

a(n)=if(n<0,0,2^n*(2*n+2)!/(n+1)!/(n+2)!)

a(n) = A052701(n+2)/2.
2*a(n) matches the odd-indexed terms of A090375.
a(n) = 2^n * binomial(2n+3, n+1) / (2n+3). - Len Smiley, Feb 24 2006
G.f.: (1-4x-sqrt(1-8x))/(8x^2) = C(2x)^2, where C(x) is the g.f. for Catalan numbers, A000108.
From Gary W. Adamson, Jul 12 2011: (Start)
Let M = the following production matrix:
  2, 2, 0, 0, 0, ...
  2, 2, 2, 0, 0, ...
  2, 2, 2, 2, 0, ...
  2, 2, 2, 2, 2, ...
  ...
a(n) = sum of top row terms in M^n. Example: top row of M^3 = (40, 40, 24, 8, 0, 0, 0, ...), sum = 112 = a(3). (End)
D-finite with recurrence (n+2)*a(n) - 4*(2n+1)*a(n-1) = 0. - R. J. Mathar, Apr 01 2012
E.g.f.: a(n) = n!* [x^n] exp(4*x)*BesselI(1, 4*x)/(2*x). - Peter Luschny, Aug 25 2012
Expansion of square of continued fraction 1/(1 - 2*x/(1 - 2*x/(1 - 2*x/(1 - ...)))). - Ilya Gutkovskiy, Apr 19 2017
From Amiram Eldar, Mar 06 2022: (Start)
Sum_{n>=0} 1/a(n) = 38/49 + 192*arcsin(sqrt(1/8))/(49*sqrt(7)).
Sum_{n>=0} (-1)^n/a(n) = 14/27 + 32*log(2)/81. (End)
a(n) = Product_{1 <= i <= j <= n} (i + j + 2)/(i + j - 1). Cf. A001700. - Peter Bala, Feb 22 2023

A052701 a(0) = 0; for n >= 1, a(n) = 2^(n-1)*C(n-1), where C(n) = A000108(n) Catalan numbers, n>0.

Original entry on oeis.org

0, 1, 2, 8, 40, 224, 1344, 8448, 54912, 366080, 2489344, 17199104, 120393728, 852017152, 6085836800, 43818024960, 317680680960, 2317200261120, 16992801914880, 125210119372800, 926554883358720, 6882979133521920

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A151374 shifted one place right. - Joerg Arndt, Mar 17 2011
The number of rooted Eulerian n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005
This is also the number of strings of length 2n-2 of two different types of balanced parentheses. For example, a(2) = 2, since the two possible strings of length 2 are [] and (), a(3) = 8, since the 8 possible strings of length 4 are (()), [()], ([]), [[]], ()(), [](), ()[], and [][]. - Jeffrey Shallit, Jun 03 2006
Row sums of number triangle A110506. - Paul Barry, Jul 24 2005
Also row sums of triangle in A085880. - Philippe Deléham, Aug 01 2005
Row sums of number triangle A114608. - Philippe Deléham, Oct 15 2008

V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Sergey Kirgizov, and Mehdi Naima, A lattice on Dyck paths close to the Tamari lattice, arXiv:2309.00426 [math.CO], 2023.
M. Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.
Marek Bożejko, Maciej Dołęga, Wiktor Ejsmont, and Światosław R. Gal, Reflection length with two parameters in the asymptotic representation theory of type B/C and applications, arXiv:2104.14530 [math.RT], 2021.
F. Chapoton and S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv:1310.4521 [math.CO], 2013.
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics, Vol. 24, No. 2 (2017), Article P2.3.
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 651.
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., Vol. 36, No.4 (2006), pp. 364-387.
Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017.
Index to sequences related to reversion of series.

Limit of array A102544.

Cf. A000108, A003645, A025225, A052714, A195699.

spec := [S,{B=Union(C,Z),S=Union(B,C),C=Prod(S,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

InverseSeries[Series[y-2*y^2, {y, 0, 24}], x] (* then A(x)=y(x) *) (* Len Smiley, Apr 07 2000 *)
Join[{0},Table[2^n CatalanNumber[n],{n,0,30}]] (* Harvey P. Dale, Aug 29 2015 *)

a(n)=if(n<1,0,2^(n-1)*(2*n-2)!/(n-1)!/n!)

a(n)=if(n<1,0,polcoeff(serreverse(x-2*x^2+x*O(x^n)),n))

a(n)=if(n<1,0,polcoeff(2*x/(1+sqrt(1-8*x+O(x^n))),n))

a(n) = A052714(n)/n!.
a(n) = A003645(n-2)*2, n>1.
a(n) = 8^(n-1)*GAMMA(n-1/2)/GAMMA(n+1)/Pi^(1/2), n>0.
D-finite with recurrence: a(1)=1, (-4+8*n)*a(n) - (n+1)*a(n+1) = 0.
G.f.: (1-sqrt(1-8*x))/4 = x*C(2*x) where C(x) is g.f. for Catalan numbers, A000108.
G.f. A(x) satisfies 2*A(x)^2-A(x)+x=0, A(0)=0 and A(x)=x+2*A(x)^2=x/(1-2*A(x)). Series reversion of x-2*x^2. - Michael Somos, Sep 06 2003
a(0)=0, a(1)=1; a(n) = 2*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
With a different offset, a(0)=1, a(n) = Sum_{k=0..n} Sum_{j=0..n} (j*C(2n-j-1, n-j)*C(j, k)*2^(n-j)/n), n>0. - Paul Barry, Jul 24 2005
The Hankel transform of a(n+1) = [1,2,8,40,224,1344,...] is 4^C(n+1,2). - Philippe Deléham, Nov 06 2007
G.f.: x + 4*x^2/(G(0)-4*x) where G(k) = k*(8*x+1) + 4*x + 2 - 2*x*(2*k+3)*(2*k+4)/G(k+1) ; (continued fraction ). - Sergei N. Gladkovskii, Apr 05 2013
a(n) ~ 8^(n-1)/(sqrt(Pi)*n^(3/2)). - Ilya Gutkovskiy, Dec 04 2016
From Amiram Eldar, Mar 06 2022: (Start)
Sum_{n>=1} 1/a(n) = 68/49 + 96*arcsin(sqrt(1/8))/(49*sqrt(7)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 20/27 - 16*log(2)/81. (End)
a(n) = A025225(n)/2 for n>=1. - Alois P. Heinz, Feb 16 2025

Better description from Claude Lenormand (claude.lenormand(AT)free.fr), Mar 19 2001

Additional comments from Michael Somos, Feb 24 2002

A005817 a(n) = C(floor(n/2 + 1/2))*C(floor(n/2 + 1)) where C(i) = Catalan numbers A000108.

Original entry on oeis.org

1, 1, 2, 4, 10, 25, 70, 196, 588, 1764, 5544, 17424, 56628, 184041, 613470, 2044900, 6952660, 23639044, 81662152, 282105616, 987369656, 3455793796, 12228193432, 43268992144, 154532114800, 551900410000, 1986841476000, 7152629313600

Offset: 0

Simon Plouffe and N. J. A. Sloane

Number of lattice paths in the first quadrant that do not cross the main diagonal, go from (0,0) to a point on the x-axis and consist of n+1 steps from the set {E=(1,0), W=(-1,0), N=(0,1), S=(0,-1)}. Example: a(2)=4 because we have EEE, ENS, EEW and EWE [Gouyou-Beauchamps]. - Emeric Deutsch, Apr 29 2004
Also, number of standard Young tableaux of height <= 4. - Mike Zabrocki, Mar 24 2007
Also, number of walks within N^2 (the first quadrant of Z^2) starting at (0,0), ending on the vertical axis and consisting of n steps taken from {(-1, 1), (0, -1), (0, 1), (1, -1)}. - Manuel Kauers, Nov 18 2008
Also, number of walks within N^3 (the first octant of Z^3) starting at (0,0,0) and consisting of n steps taken from {(-1, 0, 0), (0, -1, 1), (0, 1, 0), (1, 0, -1)} - Manuel Kauers, Nov 18 2008
Also, number of n-length words w over alphabet {a,b,c,d} such that for every prefix z of w we have #(z,a) >= #(z,b) >= #(z,c)>= #(z,d), where #(z,x) counts the letters x in word z.  The a(4) = 10 words are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca, abcd. - Alois P. Heinz, May 30 2012
Also, for n>0, number of coalescent histories for a maximally symmetric matching bicaterpillar gene tree and species tree with n+1 leaves, that is, a bicaterpillar divided into caterpillars of size floor(n/2+1/2) and floor(n/2+1) leaves (Rosenberg 2007, Theorem 3.10). - Noah A Rosenberg, Feb 04 2019

			There are 26 standard tableaux of size 5, one of them is of length longer than 4 so a(5) = 25.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(b), y_4(n), p. 452.

T. D. Noe, Table of n, a(n) for n=0..200
F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, vol. 139, no. 1-3 (1995), 463-468.
A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.
M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
R. Cori et al., Shuffle of parenthesis systems and Baxter permutations, J. Combin. Theory, A 43 (1986), 1-22.
D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableaux de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462 [math.NT], 2008-2010.
Zhicong Lin, David G.L. Wang, and Tongyuan Zhao, A decomposition of ballot permutations, pattern avoidance and Gessel walks, arXiv:2103.04599 [math.CO], 2021.
Zhicong Lin and Jing Liu, Proof of Dilks' bijectivity conjecture on Baxter permutations, arXiv:2112.11698 [math.CO], 2021.
Alon Regev, Amitai Regev, and Doron Zeilberger, Identities in character tables of S_n, arXiv preprint arXiv:1507.03499 [math.CO], 2015.
N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.
Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]

Cf. A000108, A001405, A001006, A005700, A049401, A007579, A007578.
Bisections are A001246 and A005568.
Column k=4 of A182172. - Alois P. Heinz, May 30 2012

[Catalan(n div 2)*Catalan(((n+1)) div 2) : n in [1..30]]; // Vincenzo Librandi, Apr 16 2019

c := n->binomial(2*n,n)/(n+1); seq(c(floor((n+1)/2))*c(floor(n/2+1)), n=0..16);

Table[Binomial[2*Floor[(n+1)/2], Floor[(n+1)/2]]/(Floor[(n+1)/2]+1) * Binomial[2*Floor[n/2+1], Floor[n/2+1]]/(Floor[n/2+1]+1), {n,0,20}] (* Vaclav Kotesovec, Sep 11 2013 *)

c(n)=binomial(2*n, n)/(n+1)
for(n=1, 40, print1(c(floor((n+1)/2))*c(floor(n/2+1)), ", ")); \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008

G.f.: (hypergeom([-1/2, -1/2],[1],16*x^2)-2*x*hypergeom([-1/2, 1/2],[2],16*x^2)-1+2*x-4*x^2)/(4*x^3). - Mark van Hoeij, Oct 25 2011
D-finite with recurrence (n+3)*(n+4)*a(n) = 4*(2*n+3)*a(n-1) + 16*(n-1)*n*a(n-2). - Vaclav Kotesovec, Sep 11 2013
a(n) ~ 2^(2*n+5)/(Pi*n^3). - Vaclav Kotesovec, Sep 11 2013

Description corrected Feb 15 1997.
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008
Offset changed by N. J. A. Sloane, Nov 28 2008

A105523 Expansion of 1-x*c(-x^2) where c(x) is the g.f. of A000108.

Original entry on oeis.org

1, -1, 0, 1, 0, -2, 0, 5, 0, -14, 0, 42, 0, -132, 0, 429, 0, -1430, 0, 4862, 0, -16796, 0, 58786, 0, -208012, 0, 742900, 0, -2674440, 0, 9694845, 0, -35357670, 0, 129644790, 0, -477638700, 0, 1767263190, 0

Offset: 0

Paul Barry, Apr 11 2005

Row sums of A105522. Row sums of inverse of A105438.

First column of number triangle A106180.

			G.f. = 1 - x + x^3 - 2*x^5 + 5*x^7 - 14*x^9 + 42*x^11 - 132*x^13 + 429*x^15 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 313.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011.

Cf. A000108, A097331, A090192, A090181, A105522, A105438.

m:=25; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!((1 + 2*x - Sqrt(1+4*x^2))/(2*x))); // G. C. Greubel, Sep 16 2018

A105523_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w]:=-a[w-1]+(-1)^w*add(a[j]*a[w-j-1],j=1..w-1) od; convert(a,list)end: A105523_list(40); # Peter Luschny, May 19 2011

a[n_?EvenQ] := 0; a[n_?OddQ] := 4^n*Gamma[n/2] / (Gamma[-n/2]*(n+1)!); a[0] = 1; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)
CoefficientList[Series[(1 + 2 x - Sqrt[1 + 4 x^2])/(2 x), {x, 0, 50}], x] (* Vincenzo Librandi, Nov 01 2014 *)
a[ n_] := SeriesCoefficient[ (1 + 2 x - Sqrt[ 1 + 4 x^2]) / (2 x), {x, 0, n}]; (* Michael Somos, Jun 17 2015 *)
a[ n_] := If[ n < 1, Boole[n == 0], a[n] = -2 a[n - 1] + Sum[ a[j] a[n - j - 1], {j, 0, n - 1}]]; (* Michael Somos, Jun 17 2015 *)

{a(n) = local(A); if( n<0, 0, n++; A = vector(n); A[1] = 1; for( k=2, n, A[k] = -2 * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])}; /* Michael Somos, Jul 24 2011 */

def A105523(n):
    if is_even(n): return 0 if n>0 else 1
    return -(sqrt(pi)*2^(n-1))/(gamma(1-n/2)*gamma((n+3)/2))
[A105523(n) for n in (0..29)] # Peter Luschny, Oct 31 2014

G.f.: (1 + 2*x - sqrt(1+4*x^2))/(2*x).
a(n) = 0^n + sin(Pi*(n-2)/2)(C((n-1)/2)(1-(-1)^n)/2).
G.f.: 1/(1+x/(1-x/(1+x/(1-x/(1+x/(1-x.... (continued fraction). - Paul Barry, Jan 15 2009
a(n) = Sum{k = 0..n} A090181(n,k)*(-1)^k. - Philippe Deléham, Feb 02 2009
a(n) = (1/n)*sum_{i = 0..n-1} (-2)^i*binomial(n, i)*binomial(2*n-i-2, n-1). - Vladimir Kruchinin, Dec 26 2010
With offset 1, a(n) = -2 * a(n-1) + Sum_{k=1..n-1} a(k) * a(n-k), for n>1. - Michael Somos, Jul 25 2011
D-finite with recurrence: (n+3)*a(n+2) = -4*n*a(n), a(0)=1, a(1)=-1. - Fung Lam, Mar 18 2014
For nonzero terms, a(n) ~ (-1)^((n+1)/2)/sqrt(2*Pi)*2^(n+1)/(n+1)^(3/2). - Fung Lam, Mar 17 2014
a(n) = -(sqrt(Pi)*2^(n-1))/(Gamma(1-n/2)*Gamma((n+3)/2)) for n odd. - Peter Luschny, Oct 31 2014
From Peter Bala, Apr 20 2024: (Start)
a(n) = Sum_{k = 0..n} (-2)^(n-k)*binomial(n + k, 2*k)*Catalan(k), where Catalan(k) = A000108(k).
a(n) = (-2)^n * hypergeom([-n, n+1], [2], 1/2).
O.g.f.: A(x) = 1/x * series reversion of x*(1 - x)/(1 - 2*x).  Cf. A152681. (End)

Typo in definition corrected by Robert Israel, Oct 31 2014

A049027 G.f.: (1-2xc(x))/(1-3xc(x)) where c(x) = (1 - sqrt(1-4x))/(2x) is the g.f. for Catalan numbers A000108.

Original entry on oeis.org

1, 1, 4, 17, 74, 326, 1446, 6441, 28770, 128750, 576944, 2587850, 11615932, 52167688, 234383146, 1053386937, 4735393794, 21291593238, 95747347176, 430624242942, 1936925461644, 8712882517188, 39195738193836, 176335080590442, 793336332850164, 3569368545752076

Offset: 0

Wolfdieter Lang

Row sums of triangle A035324.
a(n+1) = {1, 4, 17, 74, 326, ...} is the binomial transform of A059738. - Philippe Deléham, Nov 26 2009
(1, 4, 17, 74, 326, ...) is the invert transform of the odd-indexed central binomial coefficients, A001700. - David Callan, Oct 14 2012
The sequence starting with index 1 is the INVERT transform of A001700: (1, 3, 10, 35, 126, ...) and the second INVERT transform of the Catalan numbers starting with index 1: (1, 2, 5, 14, 42, ...). - Gary W. Adamson, Jun 23 2015
From Peter Bala, Jan 27 2020: (Start)
This sequence is the main diagonal of the lower triangular array formed by taking the first column (k = 0) of the array equal to (1,1,3,9,27,...) - powers of 3 with 1 prepended - and then completing the triangle using the relation T(n,k) = T(n-1,k) + T(n,k-1) for k >= 1. See my link in A001517.
   1
   1    1
   3    4    4
   9   13   17   17
  27   40   57   74   74
  81  121  178  252  326  326
  ...
(End)

			G.f. = 1 + x + 4*x^2 + 17*x^3 + 74*x^4 + 326*x^5 + 1446*x^6 + 6441*x^7 + ...

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
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 and arXiv version, arXiv:1505.05568 [math.CO], 2015.
Paul Barry and Arnauld Mesinga Mwafise, Classical and Semi-Classical Orthogonal Polynomials Defined by Riordan Arrays, and Their Moment Sequences, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.5.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 20.
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)
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Cf. A000108, A001700.

[1] cat [n eq 1 select 1 else (9*Self(n-1)-Catalan(n-1))/2: n in [1..30]]; // Vincenzo Librandi, Jun 25 2015

a:= proc(n) option remember; `if`(n<3, 1+3*n*(n-1)/2,
      (17/2-6/n)*a(n-1)-(18-27/n)*a(n-2))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Jan 28 2020

Table[SeriesCoefficient[2/(3-1/Sqrt[1-4*x]),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 08 2012 *)
FunctionExpand@Table[3^(2n-1)/2^(n+1) + 2^n (2n-1)!! Hypergeometric2F1[1, n + 1/2, n + 2, 8/9]/(9 (n + 1)!) + 2 KroneckerDelta[n]/3, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 08 2016 *)

{a(n) = if( n<1, n==0, polcoeff( serreverse( x * (1 + 2*x) / (1 + 3*x)^2 + x * O(x^n) ), n))}; /* Michael Somos, Apr 08 2007 */

{a(n) = if( n<0, 0, polcoeff( 2 / (3 - 1 / sqrt(1 - 4*x + x * O(x^n))), n))}; /* Michael Somos, Apr 08 2007 */

(2/(3-1/sqrt(1-4*x))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 02 2019

G.f.: x*c(x)/(1-3*x*c(x)), c(x)= g.f. of Catalan numbers A000108.
a(n+1) = Sum_{k=0..n} 2^k*comb(2n+1, n-k)*2*(k+1)/(n+k+2) - Paul Barry, Jun 22 2004
a(n) = (9*a(n-1) - Catalan(n-1))/2, n > 1. - Vladeta Jovovic, Aug 08 2004
a(n+1) = Sum_{k=0..n} A039598(n,k)*2^k. - Philippe Deléham, Mar 21 2007
G.f.: 2 / (3 - 1 / sqrt(1 - 4*x)). - Michael Somos, Apr 08 2007
a(n) = Sum_{k=0..n} A039599(n,k)*A001045(k), for n >= 1. - Philippe Deléham, Jun 10 2007
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,-3). - Milan Janjic, Jul 08 2010
From Gary W. Adamson, Jul 25 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows:
  4, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ... (End)
D-finite with recurrence: 2*n*a(n) + (12-17*n)*a(n-1) + 18*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011
a(n) ~ 3^(2*n-1)/2^(n+1). - Vaclav Kotesovec, Oct 08 2012
0 = a(n)*(1296*a(n+1) - 1098*a(n+2) + 180*a(n+3)) + a(n+1)*(-126*a(n+1) + 253*a(n+2) - 58*a(n+3)) + a(n+2)*(-10*a(n+2) + 4*a(n+3)) if n > 0. - Michael Somos, Jan 23 2014
O.g.f.: A(x) = 1/(1 - (1/2)*Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016
a(n) = 3^(2*n-1)/2^(n+1) + 2^n * (2*n-1)!! * hypergeom([1,n+1], [n+2], 8/9)/(9*(n+1)!) + 0^n * 2/3. - Vladimir Reshetnikov, Oct 08 2016

A057117 Permutation of nonnegative integers obtained by mapping each forest of A000108[n] rooted binary plane trees from breadth-first to depth-first encoding.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 8, 6, 9, 10, 12, 13, 11, 17, 18, 21, 22, 20, 14, 15, 16, 19, 23, 24, 26, 27, 25, 31, 32, 35, 36, 34, 28, 29, 30, 33, 45, 46, 49, 50, 48, 58, 59, 63, 64, 62, 54, 55, 57, 61, 37, 38, 40, 41, 39, 44, 47, 42, 43, 56, 60, 51, 52, 53, 65, 66, 68, 69, 67, 73, 74

Offset: 0

Antti Karttunen, Aug 11 2000

nonn

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Restriction of the automorphism A072088 to the plane binary trees.

Add one to each term and "overlay" each successive subpermutation of A000108[n] terms and one obtains A038776. Inverse permutation is A057118.

a(n) = CatalanRankGlobal(btbf2df(binrev(A014486[n]),0,1)/2)
Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES book, see A014486
CatalanRank := proc(n,aa) local x,y,lo,a; a := binrev(aa); y := 0; lo := 0; for x from 1 to (2*n)-1 do lo := lo + (1-(a mod 2))*Mn(n,x,y+1); y := y - ((-1)^a); a := floor(a/2); od; RETURN((binomial(2*n,n)/(n+1))-(lo+1)); end;
CatalanRankGlobal := proc(a) local n; n := floor(binwidth(a)/2); RETURN(add((binomial(2*j,j)/(j+1)),j=0..(n-1))+CatalanRank(n,a)); end;

A007595 a(n) = C_n / 2 if n is even or ( C_n + C_((n-1)/2) ) / 2 if n is odd, where C = Catalan numbers (A000108).

Original entry on oeis.org

1, 1, 3, 7, 22, 66, 217, 715, 2438, 8398, 29414, 104006, 371516, 1337220, 4847637, 17678835, 64823110, 238819350, 883634026, 3282060210, 12233141908, 45741281820, 171529836218, 644952073662, 2430973304732, 9183676536076, 34766775829452, 131873975875180

Offset: 1

N. J. A. Sloane

Number of necklaces of 2 colors with 2n beads and n-1 black ones. - Wouter Meeussen, Aug 03 2002
Number of rooted planar binary trees up to reflection (trees with n internal nodes, or a total of 2n+1 nodes). - Antti Karttunen, Aug 19 2002
Number of even permutations avoiding 132.
Number of Dyck paths of length 2n having an even number of peaks at even height. Example: a(3)=3 because we have UDUDUD, U(UD)(UD)D and UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even height are shown between parentheses. - Emeric Deutsch, Nov 13 2004
Number of planar trees (A002995) on n edges with one distinguished edge. - David Callan, Oct 08 2005
Assuming offset 0 this is an analog of A275165: pairs of two Catalan nestings with index sum n. - R. J. Mathar, Jul 19 2016

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
Peter J. Cameron, Some treelike objects Quart. J. Math. Oxford Ser., Vol. 38, No. 2 (1987), pp. 155-183. Note that line 3 on p. 163 has a typo. - _N. J. A. Sloane_, Apr 18 2014
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seq., Vol. 3 (2000), Article 00.1.5.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), Article 16.2.4.
Andrew Gainer-Dewar, Pólya theory for species with an equivariant group action, arXiv preprint arXiv:1401.6202 [math.CO], 2014.
Toufik Mansour, Counting occurrences of 132 in an even permutation, arXiv:math/0211205 [math.CO], 2002.
Krishna Menon and Anurag Singh, Grassmannian permutations avoiding identity, arXiv:2212.13794 [math.CO], 2022.

a(n) = A047996(2*n, n-1) for n >= 1 and a(n) = A072506(n, n-1) for n >= 2.
Occurs in A073201 as rows 0, 2, 4, etc. (with a(0)=1 included).
Cf. also A003444, A007123.
Cf. A000108, A000150, A334843.

A007595 := n -> (1/2)*(Cat(n) + (`mod`(n,2)*Cat((n-1)/2))); Cat := n -> binomial(2*n,n)/(n+1);

Table[(Plus@@(EulerPhi[ # ]Binomial[2n/#, (n-1)/# ] &)/@Intersection[Divisors[2n], Divisors[n-1]])/(2n), {n, 2, 32}] (* or *) Table[If[EvenQ[n], CatalanNumber[n]/2, (CatalanNumber[n] + CatalanNumber[(n-1)/2])/2], {n, 24}]
Table[(CatalanNumber[n] + 2^n Binomial[1/2, (n + 1)/2] Sin[Pi n/2])/2, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)
Table[If[EvenQ[n],CatalanNumber[n]/2,(CatalanNumber[n]+CatalanNumber[(n-1)/2])/2],{n,30}] (* Harvey P. Dale, Sep 06 2021 *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n % 2, (catalan(n) + catalan((n-1)/2))/2, catalan(n)/2); \\ Michel Marcus, Jan 23 2016

G.f.: (2-2*x-sqrt(1-4*x)-sqrt(1-4*x^2))/x/4. - Vladeta Jovovic, Sep 26 2003
D-finite with recurrence: n*(n+1)*a(n) -6*n*(n-1)*a(n-1) +4*(2*n^2-10*n+9)*a(n-2) +8*(n^2+n-9)*a(n-3) -48*(n-3)*(n-4)*a(n-4) +32*(2*n-9)*(n-5)*a(n-5)=0. - R. J. Mathar, Jun 03 2014, adapted to offset Feb 20 2020
a(n) ~ 4^n /(2*sqrt(Pi)*n^(3/2)). - Ilya Gutkovskiy, Jul 19 2016
a(2n) = A000150(2n). - R. J. Mathar, Jul 19 2016
a(n) = (A000108(n) + 2^n * binomial(1/2, (n+1)/2) * sin(Pi*n/2))/2. - Vladimir Reshetnikov, Oct 03 2016
Sum_{n>=1} a(n)/4^n = (3-sqrt(3))/2 (A334843). - Amiram Eldar, Mar 20 2022

Description corrected by Reiner Martin and Wouter Meeussen, Aug 04 2002

A007854 Expansion of 1/(1 - 3xC(x)), where C(x) = (1 - sqrt(1 - 4x))/(2x) = g.f. for the Catalan numbers A000108.

Original entry on oeis.org

1, 3, 12, 51, 222, 978, 4338, 19323, 86310, 386250, 1730832, 7763550, 34847796, 156503064, 703149438, 3160160811, 14206181382, 63874779714, 287242041528, 1291872728826, 5810776384932, 26138647551564, 117587214581508

Offset: 0

Martin Klazar

Chains in rooted plane trees on n nodes.
The Hankel transform of the aerated sequence with g.f. 1/(1-3x^2c(x^2)) is also 3^n. In general, the expansions of 1/(1-k*x*c(x)) and 1/(1-k*x^2*c(x^2)) have Hankel transform k^n. - Paul Barry, Jan 20 2007
Binomial transform of A112657. - Philippe Deléham, Nov 25 2007
Row sums of the Riordan matrix (1/sqrt(1-4x),(1-sqrt(1-4x))/(2*sqrt(1-4x))) (A116395). - Emanuele Munarini, Apr 26 2011
Numbers have the same parity as the Catalan numbers, that is, a(n) is even except for n of the form 2^m - 1. Follows from C(x) = 1/(1 - x*C(x)) = 1/(1 - 3*x*C(x)) (mod 2). - Peter Bala, Jul 24 2016

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Martin Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
J.-C. Novelli and J.-Y. Thibon, Free quasi-symmetric functions of arbitrary level, arXiv:math/0405597 [math.CO], 2004.
Index entries for sequences related to rooted trees

Cf. A000108, A000984, A076035, A076036, A067347, A116395, A126694.

CoefficientList[Series[(1+3Sqrt[1-4x])/(4-18x),{x,0,25}],x] (* Emanuele Munarini, Apr 26 2011 *)
nm = 25; t = NestList[Append[Accumulate[#], 3 Total[#]] &, {1}, nm];
Table[t[[n, n]], {n, nm}] (*similar to generating Catalan's triangle A009766*)
(* Li Han, Oct 23 2020 *)

makelist(kron_delta(n,0)+sum(binomial(2*n-k,n-k)*(k*3^k)/(2*n-k),k,1,n),n,0,12); /* Emanuele Munarini, Apr 26 2011 */

a(n) = (9*a(n-1)-3*A000108(n-2))/2 = 3*A049027(n-1) = A067336(n-1)*3/2 = A049027(n-1) + A067336(n-1) = A067347(3, n-1). - Henry Bottomley, Jan 16 2002
a(n) = Sum_{k>=0} A106566(n, k)*3^k. - Philippe Deléham, Aug 11 2005
The Hankel transform of this sequence is A000244 = [1, 3, 9, 27, 81, 243, 729, ...](powers of 3). - Philippe Deléham, Nov 26 2006
a(n) = Sum_{k = 0..n} C(2n,n-k)(2k+1)2^k/(n+k+1). - Paul Barry, Jan 20 2007
a(n) = Sum_{k = 0..n} A039599(n,k)*2^k. - Philippe Deléham, Sep 08 2007
a(n) = Sum_{k = 0..n} A116395(n,k). - Vladimir Kruchinin, Mar 09 2011
From Emanuele Munarini, Apr 26 2011 (Start)
a(n) = Sum_{k = 1..n} C(2*n-k,n-k)*(k*3^k)/(2*n-k), for n>0.
a(n) = (1/4)*(9/2)^n-3*Sum_{k=0..n} C(2*k,k)/(2k-1)*(9/2)^(n-k).
D-finite with recurrence: 2*(n+2)*a(n+2)-(17*n+22)*a(n+1)+18*(2*n+1)*a(n)=0. (End)
From Gary W. Adamson, Jul 14 2011: (Start)
a(n) = upper left term in M^n, M = the infinite square production matrix:
  3, 3, 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, ...
  ... (End)

More terms from Henry Bottomley, Jan 16 2002

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

A115139 Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A003645 a(n) = 2^n * C(n+1), where C(n) = A000108(n) Catalan numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A052701 a(0) = 0; for n >= 1, a(n) = 2^(n-1)*C(n-1), where C(n) = A000108(n) Catalan numbers, n>0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A005817 a(n) = C(floor(n/2 + 1/2))*C(floor(n/2 + 1)) where C(i) = Catalan numbers A000108.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A105523 Expansion of 1-x*c(-x^2) where c(x) is the g.f. of A000108.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A049027 G.f.: (1-2*x*c(x))/(1-3*x*c(x)) where c(x) = (1 - sqrt(1-4*x))/(2*x) is the g.f. for Catalan numbers A000108.

Views

Author

A049027 G.f.: (1-2xc(x))/(1-3xc(x)) where c(x) = (1 - sqrt(1-4x))/(2x) is the g.f. for Catalan numbers A000108.

A007854 Expansion of 1/(1 - 3xC(x)), where C(x) = (1 - sqrt(1 - 4x))/(2x) = g.f. for the Catalan numbers A000108.