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

Author

Wolfdieter Lang

Keywords

• nonn

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

Crossrefs

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

Programs

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

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