

A007317


Binomial transform of Catalan numbers.
(Formerly M1480)


96



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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 xaxis) from (0,0) to (2n2,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. Noncommutative Nonassociative 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 2n1 edges; also number of symmetric hex trees with 2n2 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 treelike polyhexes; see the HararyRead 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 321avoiding partitions of [n]. A partition is 321avoiding 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 321avoiding. For example, the only partition of [5] that fails to be 321avoiding 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 Hspaces. 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 n1 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(1x)/(1+xx^2). This means that the substitution of the gf (1x(16x+5x^2)^(1/2))/(2(1x)) for x in x(1x)/(1+xx^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/(1x) = P[x], and C(x)= [1sqrt(14x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1x).
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)] = (xx^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)/[1xx^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,1t]], 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


REFERENCES

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


LINKS

T. D. Noe, Table of n, a(n) for n=1..200
Roland Bacher and David Garber, Spindleconfigurations of skew lines, arXiv:math/0205245 [math.GT], 20022005.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343385.
Paul Barry, On the Central Antecedents of Integer (and Other) Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
P. Barry, A. Hennessy, The EulerSeidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010) # 10.8.2.
Andrew M. Baxter, Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, 2015.
Janusz Brzozowski, Marek Szykula, Large Aperiodic Semigroups, arXiv preprint arXiv:1401.0157 [cs.FL], 20132014.
David Callan, Pattern avoidance in "flattened" partitions , arXiv:0802.2275 [math.CO], 2008.
H Cambazard, N Catusse, FixedParameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane, arXiv preprint arXiv:1512.06649 [cs.DS], 20152017.
Giulio Cerbai, Anders Claesson, Luca Ferrari, Einar Steingrímsson, Sorting with patternavoiding stacks: the 132machine, arXiv:2006.05692 [math.CO], 2020.
XiangKe Chang, X.B. Hu, H. Lei, Y.N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
Harry Crane, Leftright arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 5772.
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), 532540.
S. J. Cyvin et al., Graphtheoretical studies on fluoranthenoids and fluorenoids:enumeration of some catacondensed systems, J. Molec. Struct. (Theochem), 285 (1993), 179185.
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), 11741180.
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, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
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, SatoTate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 20112012.
S. Forcey, Quotients of the multiplihedron as categorified associahedra,Homotopy, Homology and Applications, vol. 10(2), 227256, 2008. [From Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009]
Ira M. Gessel, Jang Soo Kim, A note on 2distant noncrossing partitions and weighted Motzkin paths, arXiv:1003.5301 [math.CO], 2010.
Ira M. Gessel, Jang Soo Kim, A note on 2distant noncrossing partitions and weighted Motzkin paths, Discrete Math. 310 (2010), no. 23, 34213425. MR2721104 (2011j:05350). See Eq. (1).  N. J. A. Sloane, Jul 05 2014
Juan B. Gil, Jordan O. Tirrell, A simple bijection for classical and enhanced knoncrossing partitions, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019) Article 111705. doi:10.1016/j.disc.2019.111705
Juan B. Gil, Michael D. Weiner, On patternavoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.
U. Grude, Java ist eine Sprache: Rekursive Unterprogramme. See page 4.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2Binary trees: bijections and related issues, Discr. Math., 308 (2008), 12091221.
Frank Harary and Ronald C. Read, The enumeration of treelike polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 113.
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 Bseries, Master's thesis, Simon Fraser University, 2014.
Hana Kim, 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), 10571063.
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), 45704577.
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), 34573462.
Lara K. Pudwell, Ascent sequences and the binomial convolution of Catalan numbers, arXiv:1408.6823 [math.CO], 2014.
Lara Pudwell, Andrew Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Lara Pudwell, Patternavoiding 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
Makhin Thitsa and W. Steven Gray, On the Radius of Convergence of Interconnected Analytic Nonlinear InputOutput Systems, SIAM Journal on Control and Optimization, Vol. 50, No. 5, 2012, pp. 27862813.  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.


FORMULA

(n+2)*a(n+2) = (6n+4)*a(n+1)  5n*a(n).
G.f.: 3/2(1/2)*sqrt((15*x)/(1x)) [GesselKim].  N. J. A. Sloane, Jul 05 2014
G.f. for sequence doubled: (1/(2*x))*(1+x(1x)^(1)*(1x^2)^(1/2)*(15*x^2)^(1/2)).
a(n) = hypergeom([1/2, n], [2], 4), n=0, 1, 2...; Integral representation as nth moment of a positive function on a finite interval of the positive halfaxis: a(n)=int(x^n*sqrt((5x)/(x1))/(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, n1, a(i)*a(ni)).  Benoit Cloitre, Mar 16 2004
a(n) = sum{k=0..n, (1)^k*3^(nk)*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(1x)(yy^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(zz^2)+(x1)y^2 .  Michael Somos, May 23 2005
G.f. (for offset 0): (1+x+(16*x+5*x^2)^(1/2))/(2*(x+x^2)).
G.f. =z*c(z/(1z))/(1z) = 1/2  (1/2)sqrt(14z/(1z)), where c(z)=(1sqrt(14z))/(2z) is the Catalan function (follows from Michael Somos' first comment).  Emeric Deutsch, Aug 12 2007
G.f.: 1/(12xx^2/(13xx^2/(13xx^2/(13xx^2/(13xx^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 (33*xsqrt(16*x+5*x^2))/(2*(1x)). [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^(n1), 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/((1x)*(k+1)  x*(1x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1x)/Q(k+1))); (continued fraction).  Sergei N. Gladkovskii, May 14 2013
G.f.: (1x  (15*x)*G(0))/(2*x*(1x)), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1x)  2*x*(1x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1x)*(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)/(1x), where G(k) = 1 + (4*k+1)*x/((k+1)*(1x)  2*x*(1x)*(k+1)*(4*k+3)/(2*x*(4*k+3) + (2*k+3)*(1x)/G(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Jan 29 2014
a(n) = JacobiP(n1,1,n1/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 mth binomial transform of the Catalan numbers.  Peter Bala, Jan 26 2020


EXAMPLE

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


MAPLE

G := (1sqrt(14*z/(1z)))*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(n1, 1, n1/2, 9)/n, 99)), n=1..25); # Peter Luschny, Sep 23 2014


MATHEMATICA

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[yy^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}] (* JeanFranç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 *)


PROG

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


CROSSREFS

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.
mth 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.
Sequence in context: A007581 A124303 A073525 * A181768 A279554 A279555
Adjacent sequences: A007314 A007315 A007316 * A007318 A007319 A007320


KEYWORD

easy,nonn,nice


AUTHOR

N. J. A. Sloane, Mira Bernstein


STATUS

approved



