0,2

In other words, we are counting walks on the integer lattice N^2 that start at (0,0) and end at (n,n); they may take arbitrary steps, but the slopes of the steps in the walk must strictly increase. As a result, we obtain a convex polygon when joining the two endpoints of the walk with the point (0,n).

Vaclav Kotesovec, Table of n, a(n) for n = 0..100

J. Bureaux, N. Enriquez, On the number of lattice convex chains, arXiv:1603.09587 [math.PR], 2016.

a(n) = [x^n*y^n] 1/((1-x)*(1-y)*Product_{i>0,j>0,gcd(i,j)=1} (1-x^i*y^j)).

An asymptotic formula for a(n) is given by Bureaux and Enriquez: a(n) ~ e^(-2*zeta'(-1))/((2*Pi)^(7/6)*sqrt(3)*kappa^(1/18)*n^(17/18)) * e^(3*kappa^(1/3)*n^(2/3)+...) where kappa := zeta(3)/zeta(2) and zeta denotes the Riemann zeta function.

The two walks for n = 1 are

(0,0) -> (1,1)

(0,0) -> (1,0) -> (1,1).

The five possibilities for n = 2 are

(0,0) -> (2,2)

(0,0) -> (1,0) -> (2,1) -> (2,2)

(0,0) -> (1,0) -> (2,2)

(0,0) -> (2,0) -> (2,2)

(0,0) -> (2,1) -> (2,2).

a[i_Integer, j_Integer, s_] := a[i, j, s] = If[i === 0, 1, Sum[a[i - x, j - y, y/x], {x, 1, i}, {y, Floor[s*x] + 1, j}]]; a[n_Integer] := a[n] = 1 + Sum[a[n - x, n - y, y/x], {x, 1, n}, {y, 0, x - 1}]; Flatten[{1, Table[a[n], {n, 30}]}]

nmax = 20; p = (1 - x)*(1 - y); Do[Do[p = Expand[p*If[GCD[i, j] == 1, (1 - x^i*y^j), 1]]; p = Select[p, (Exponent[#, x] <= nmax) && (Exponent[#, y] <= nmax) &], {i, 1, nmax}], {j, 1, nmax}]; p = Expand[Normal[Series[1/p, {x, 0, nmax}, {y, 0, nmax}]]]; p = Select[p, Exponent[#, x] == Exponent[#, y] &]; Flatten[{1, Table[Coefficient[p, x^n*y^n], {n, 1, nmax}]}] (* Vaclav Kotesovec, Apr 08 2016 *)

Cf. A002774, A090806, A219554.

Sequence in context: A179257 A116702 A098156 * A098586 A199812 A255170

Adjacent sequences: A267859 A267860 A267861 * A267863 A267864 A267865

nonn,walk

Christoph Koutschan, Apr 07 2016

approved