login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A267862 Number of planar lattice convex polygonal lines joining the origin and the point (n,n). 1
1, 2, 5, 13, 32, 77, 178, 399, 877, 1882, 3959, 8179, 16636, 33333, 65894, 128633, 248169, 473585, 894573, 1673704, 3103334, 5705383, 10405080, 18831761, 33836627, 60378964, 107035022, 188553965, 330166814, 574815804, 995229598, 1714004131, 2936857097 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

LINKS

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.

FORMULA

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.

EXAMPLE

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

MATHEMATICA

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

CROSSREFS

Cf. A002774, A090806, A219554.

Sequence in context: A179257 A116702 A098156 * A098586 A199812 A255170

Adjacent sequences:  A267859 A267860 A267861 * A267863 A267864 A267865

KEYWORD

nonn,walk

AUTHOR

Christoph Koutschan, Apr 07 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 01:17 EST 2018. Contains 299357 sequences. (Running on oeis4.)