A144700 Generalized (3,-1) Catalan numbers.

1, 1, 1, 1, 2, 5, 11, 21, 38, 71, 141, 289, 591, 1195, 2410, 4897, 10051, 20763, 42996, 89139, 185170, 385809, 806349, 1689573, 3547152, 7459715, 15714655, 33161821, 70095642, 148388521, 314562189, 667682057, 1418942341

Offset: 0

Author

Paul Barry, Sep 19 2008

Keywords

• easy
• nonn

Comments

Number of lattice paths in the first quadrant from (0,0) to (n,0) using only steps H=(1,0), U=(1,1) and D=(3,-1). Hankel transform has g.f. (1-x^3)/(1+x^4) (A132380 (n+3)).

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).

Crossrefs

Cf. A000108, A014137, A023431, A090344, A132380.

Programs

Magma

[(&+[Binomial(n-k,3*k)*Catalan(k): k in [0..Floor(n/4)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022

Mathematica

b[n_, m_]:=a[n, m]=Sum[Binomial[n-k,m*k]*CatalanNumber[k], {k,0,Floor[n/(m+1)]}];
A144700[n_]:= b[n,3]; (* A014137 (m=0), A090344 (m=1), A023431 (m=2) *)
Table[A144700[n], {n, 0, 40}] (* G. C. Greubel, Jun 15 2022 *)

SageMath

[sum(binomial(n-k,3*k)*catalan_number(k) for k in (0..(n//4))) for n in (0..40)] # G. C. Greubel, Jun 15 2022

Formula

G.f.: (1/(1-x)) * c(x^4/(1-x)^3), where c(x) is the g.f. of A000108.

a(n) = Sum_{k=0..floor(n/4)} binomial(n-k, 3*k)*A000108(k).

(n+4)*a(n) = 2*(2*n+5)*a(n-1) - 6*(n+1)*a(n-2) + 2*(2*n-1)*a(n-3) +3*(n-2)*a(n-4) - 2*(2*n-7)*a(n-5). - R. J. Mathar, Nov 16 2011

a(n) = b(n, 3), where b(n, m) = Sum_{k=0..floor(n/(m+1))} binomial(n-k, m*k)*A000108(k). - G. C. Greubel, Jun 15 2022