A052141 Number of paths from (0,0) to (n,n) that always move closer to (n,n) (and do not pass (n,n) and backtrack).

1, 3, 26, 252, 2568, 26928, 287648, 3112896, 34013312, 374416128, 4145895936, 46127840256, 515268544512, 5775088103424, 64912164888576, 731420783788032, 8259345993203712, 93443504499523584, 1058972245409005568, 12019152955622817792, 136599995048232747008

Offset: 0

Author

N. J. A. Sloane, Jan 23 2000

Keywords

• nonn
• easy
• nice
• walk

Comments

From Michel Marcus and Petros Hadjicostas, Jul 16 2020: (Start)

a(n) is the number of subdivisions of a 2 x n grid as defined in Robeva and Sun (2020). We have a(n) = A059576(n-1, n-1) for n >= 1 privided the latter is viewed as a square array (rather than a triangle).

In general, A059576(m-1, n-1) is the number of subdivisions of a 2-row grid with m points at the top row and n points at the bottom. (End)

The title condition is unclear: the path (0,0) -> (0,n) -> (n,n-1) -> (n,n) arguably meets the title condition but is not allowed, because steps with negative slope are proscribed. Steps must move east (slope 0) or have finite positive slope or move north (infinite slope). On the other hand, for lattice paths subject only to the condition that each successive point on the path is closer to the terminal point than its predecessor, see the question "Why are the numbers counting "ever-closer" lattice paths so round?" on the mathoverflow website. - David Callan, Nov 21 2021

References

• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 6.3.9.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Elina Robeva and Melinda Sun, Bimonotone Subdivisions of Point Configurations in the Plane, arXiv:2007.00877 [math.CO], 2020. See A(2,n) column in Table 3 (p. 10).

Crossrefs

Main diagonal of A059576.

Column k=2 of A316674.

Cf. A084773, A316673.

Programs

Magma

[n eq 0 select 1 else 2^(n-1)*Evaluate(LegendrePolynomial(n), 3) : n in [0..40]]; // G. C. Greubel, May 21 2023

Mathematica

a[0]=1; a[n_]:= Hypergeometric2F1[-n, n+1, 1, -1]*2^(n-1); Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Feb 23 2012, after Jon Stadler *)
Table[2^(n-1)*LegendreP[n,3] +Boole[n==0]/2, {n,0,40}] (* G. C. Greubel, May 21 2023 *)
CoefficientList[Series[(1+1/Sqrt[1-12x+4x^2])/2,{x,0,30}],x] (* Harvey P. Dale, Mar 10 2024 *)

SageMath

def A052141(n): return 2^(n-1)*gen_legendre_P(n,0,3) + int(n==0)/2
[A052141(n) for n in range(41)] # G. C. Greubel, May 21 2023

Formula

G.f.: (1/2)*( 1 + 1/sqrt(1 - 12*x + 4*x^2) ).

a(n) = 2^(n-1) * A001850(n). - Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003

D-finite with recurrence: n*a(n) = 6*(2*n-1)*a(n-1) - 4*(n-1)*a(n-2). - Vaclav Kotesovec, Oct 08 2012

a(n) ~ sqrt(8+6*sqrt(2))*(6+4*sqrt(2))^n/(8*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 08 2012