A392303 Number of NE lattice paths from (0,0) to (n,n) staying weakly below the discretized parabolic boundary y = floor(x^2/n).

1, 1, 1, 2, 5, 7, 19, 56, 174, 392, 819, 2684, 9009, 19564, 65499, 223738, 776424, 1443362, 4994415, 14780970, 52707633, 146981085, 455786791, 1633090237, 5898386710, 14580005362, 37823819356, 137382153783, 449129095627, 1276944605965, 4644808915976, 15488533336586

Offset

0,4

Comments

The boundary y = floor(x^2/n) depends on n (unlike fixed-boundary lattice path problems), placing this outside the reach of standard kernel-method and transfer-matrix techniques.

Satisfies 1 <= a(n) < C(n) = A000108(n) for all n >= 2, where C(n) is the n-th Catalan number.

No P-recursive (D-finite) relation of order <= 6 and degree <= 5 was found in the first 500 terms using exact Gaussian elimination over a prime field (p = 10^18 + 9).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1830

Formula

a(n) is computed by the recurrence N(x,y) = N(x-1,y) + N(x,y-1), with N(x,y) = 0 if y > floor(x^2/n) or x < 0 or y < 0, N(0,0) = 1, and a(n) = N(n,n).

Example

For n = 4, the boundary heights are (0, 0, 1, 2, 4), giving a(4) = 5.

Maple

b:= proc(x, y, n) option remember; `if`(n*y>x^2, 0,
     `if`(x=0, 1, b(x-1, y, n)+`if`(y=0, 0, b(x, y-1, n))))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..31);  # Alois P. Heinz, Mar 09 2026

Prog

(Python)
def a(n):
    N = [0]*(n+1); N[0] = 1
    for x in range(1, n+1):
        b = x*x//n
        for y in range(1, b+1): N[y] += N[y-1]
        for y in range(b+1, n+1): N[y] = 0
    return N[n]

Crossrefs

Cf. A000108 (Catalan numbers, upper bound).

Sequence in context: A106872 A071198 A041387 * A096146 A041583 A143915

Adjacent sequences: A392300 A392301 A392302 * A392304 A392305 A392306

Keyword

nonn

Author

Sangyeol Yeol, Mar 09 2026

Status

approved