A001453 Catalan numbers - 1. (Formerly M3464 N1409)

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,2

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.

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

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 *)

Prog

(MuPAD) combinat::dyckWords::count(n)-1 $ n = 2..26; // Zerinvary Lajos, May 08 2008
(Magma) [Catalan(n)-1: n in [2..30]]; // Vincenzo Librandi, May 22 2011
(PARI) a(n)=(2*n)!/n!/(n+1)!-1 \\ Charles R Greathouse IV, Apr 17 2012

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.

Sequence in context: A049222 A239249 A141364 * A005002 A085507 A121654

Adjacent sequences: A001450 A001451 A001452 * A001454 A001455 A001456

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Sep 08 2000

Status

approved