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

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

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

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

Prog

(Magma) [(&+[Binomial(n-k, 3*k)*Catalan(k): k in [0..Floor(n/4)]]): n in [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

Crossrefs

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

Sequence in context: A326509 A082775 A023548 * A000785 A364552 A369525

Adjacent sequences: A144697 A144698 A144699 * A144701 A144702 A144703

Keyword

easy,nonn

Author

Paul Barry, Sep 19 2008

Status

approved