A001453 Catalan numbers - 1.

1, 4, 13, 41, 131, 428, 1429, 4861, 16795, 58785, 208011, 742899, 2674439, 9694844, 35357669, 129644789, 477638699, 1767263189, 6564120419, 24466267019, 91482563639, 343059613649, 1289904147323, 4861946401451, 18367353072151, 69533550916003, 263747951750359

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..500 (first 170 terms from Vincenzo Librandi)
• R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.
• J. M. Hammersley, A few seedings of research, in Proc. Sixth Berkeley Sympos. Math. Stat. and Prob., ed. L. M. le Cam et al., Univ. Calif. Press, 1972, Vol. I, pp. 345-394.
• Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), 227-238.
• Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Crossrefs

Cf. A000108, A001454. Column k=2 of A047874.

A141364 is essentially the same sequence.

All of A000108, A001453, A246604, A273526, A120304, A289615, A289616, A289652, A289653, A289654 are very similar sequences.

Programs

Magma

[Catalan(n)-1: n in [2..30]]; // Vincenzo Librandi, May 22 2011

Maple

with(combstruct): bin := {B=Union(Z,Prod(B,B))}: seq(count([B,bin, unlabeled], size=n+1)-1, n=2..30); # Zerinvary Lajos, Dec 05 2007

Mathematica

Array[CatalanNumber, 30, 2] - 1 (* Jean-François Alcover, Mar 11 2014 *)

MuPAD

combinat::dyckWords::count(n)-1 $ n = 2..26; // Zerinvary Lajos, May 08 2008

PARI

a(n)=(2*n)!/n!/(n+1)!-1 \\ Charles R Greathouse IV, Apr 17 2012

Formula

a(n) = A000108(n) - 1 = binomial(2*n,n)/(n+1) - 1.

D-finite with recurrence: (n+1)*a(n) +2*(-3*n+1)*a(n-1) +(9*n-13)*a(n-2) +2*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Sep 04 2013

a(n) = Sum_{k=1..floor(n/2)} (C(n,k)-C(n,k-1))^2. - J. M. Bergot, Sep 17 2013

a(n) = Sum_{k=1..n-1} A000245(n-k-1). - John M. Campbell, Dec 28 2016

From Ilya Gutkovskiy, Dec 28 2016: (Start)

O.g.f.: (1 - sqrt(1 - 4*x))/(2*x) - 1/(1 - x).

E.g.f.: exp(x)*(exp(x)*(BesselI(0,2*x) - BesselI(1,2*x)) - 1). (End)

a(n)= 3*Sum_{k=1..n} binomial(2*k-2,k)/(k+1). - Gary Detlefs, Feb 14 2020

Extensions

More terms from James Sellers, Sep 08 2000