A029760 A sum with next-to-central binomial coefficients of even order, Catalan related.

1, 8, 47, 244, 1186, 5536, 25147, 112028, 491870, 2135440, 9188406, 39249768, 166656772, 704069248, 2961699667, 12412521388, 51854046982, 216013684528, 897632738722, 3721813363288, 15401045060572, 63616796642368, 262357557683422, 1080387930269464

Offset

0,2

Comments

Proof by induction.

a(n) = total area below paths consisting of steps east (1,0) and north (0,1) from (0,0) to (n+2,n+2) that stay weakly below y=x. For example, the two paths with n=0 are

. _|.....|

_|.....__|

The first has area 1 below it, the second area 0 and so a(0)=1. - David Callan, Dec 09 2004

Convolution of A000346 with A001700. - Philippe Deléham, May 19 2009

Links

Michael De Vlieger, Table of n, a(n) for n = 0..1657

Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.

Sittipong Thamrongpairoj, Dowling Set Partitions, and Positional Marked Patterns, Ph. D. Dissertation, University of California-San Diego (2019).

Formula

a(n) = 4^(n+1)*Sum_{k=1..n+1} binomial(2k, k-1)/4^k = ((n+3)^2)*C(n+2)/2-2^(2*n+3), C = Catalan. Also a(n+1)=4*a(n)+binomial(2(n+2), n+1).

G.f.: (d/dx)c(x)/(1-4*x), where c(x) = g.f. for Catalan numbers; convolution of A001791 and powers of 4. G.f. also c(x)^2/(1-4*x)^(3/2); convolution of Catalan numbers A000108 C(n), n >= 1, with A002457; convolution of A008549(n), n >= 1, with A000984 (central binomial coefficients).

a(n) = Sum_{k=0..n+1} A039598(n+1,k)*k^2. - Philippe Deléham, Dec 16 2007

Mathematica

a[n_] := (n+3)^2 CatalanNumber[n+2]/2 - 2^(2n+3);
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Sep 25 2018 *)

Crossrefs

Cf. A000108, A002457, A008549, A000984, A139262.

Sequence in context: A099110 A106393 A300167 * A139262 A026900 A016198

Adjacent sequences: A029757 A029758 A029759 * A029761 A029762 A029763

Keyword

nonn

Author

Wolfdieter Lang

Status

approved