A133656 Number of below-diagonal paths from (0,0) to (n,n) using steps (1,0), (0,1) and (2k-1,1), k a positive integer.

1, 2, 6, 23, 99, 456, 2199, 10962, 56033, 292094, 1546885, 8299058, 45010492, 246377362, 1359339710, 7551689783, 42206697209, 237156951618, 1338917298708, 7591380528489, 43207023511013, 246773061257046, 1413889039642479, 8124356140582768, 46807462792903984

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1276 (first 51 terms from Brian Drake)

Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.

Formula

G.f. g(x) satisfies: g(x) = 1 + x*g(x)^2+x*g(x)/(1-x^2*g(x)^2).

a(n) = sum(k=0..n, binomial(n+k,n)*sum(j=0..k+n+1, binomial(j,-n-3*k+2*j-2) *(-1)^(n+k-j+1)*binomial(n+k+1,j)))/(n+1). - Vladimir Kruchinin, Oct 11 2011

From Peter Bala, Feb 22 2022: (Start)

G.f. g(x) = (1/x)*series reversion of x*(1 + x)*(1 - x)^2/(1 + x - x^2).

It appears that 1 + x*g'(x)/g(x) = 1 + 2*x + 8*x^2 + 41*x^3 + 220*x^4 + ... is the g.f. of A348474. (End)

Example

a(4) = 99 since there are 90 Schroeder paths (A006318) from (0,0) to (4,4) plus DNNEN, DNENN, DENNN, DdNN, DNdN, DNNd, EDNNN, ENDNN and dDNN, where E=(1,0), N=(0,1), D=(3,1) and d=(1,1).

Maple

A:=series(RootOf(1+_Z*(x-1)+_Z^2*(x-x^2)+_Z^3*x^2-_Z^4*x^3), x, 21): seq(coeff(A, x, i), i=0..20);

Mathematica

a[n_] := Sum[Binomial[n+k, n] * Sum[Binomial[j, -n - 3k + 2j - 2]* (-1)^(n+k-j+1) * Binomial[n+k+1, j], {j, 0, k+n+1}], {k, 0, n}]/(n+1);
a /@ Range[0, 24] (* Jean-François Alcover, Oct 06 2019, after Vladimir Kruchinin *)

Prog

(Maxima) a(n):=sum(binomial(n+k, n)*sum(binomial(j, -n-3*k+2*j-2)*(-1)^(n+k-j+1) *binomial(n+k+1, j), j, 0, k+n+1), k, 0, n)/(n+1); /* Vladimir Kruchinin, Oct 11 2011 */

Crossrefs

Cf. A006318, A064641, A052709, A063020, A348474.

Row sums of A201080.

Sequence in context: A196018 A009449 A233106 * A078487 A193038 A213090

Adjacent sequences: A133653 A133654 A133655 * A133657 A133658 A133659

Keyword

easy,nonn

Author

Brian Drake, Sep 20 2007

Status

approved