|
%I #29 Apr 08 2016 15:49:12
%S 1,2,5,13,32,77,178,399,877,1882,3959,8179,16636,33333,65894,128633,
%T 248169,473585,894573,1673704,3103334,5705383,10405080,18831761,
%U 33836627,60378964,107035022,188553965,330166814,574815804,995229598,1714004131,2936857097
%N Number of planar lattice convex polygonal lines joining the origin and the point (n,n).
%C 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).
%H Vaclav Kotesovec, <a href="/A267862/b267862.txt">Table of n, a(n) for n = 0..100</a>
%H J. Bureaux, N. Enriquez, <a href="http://arxiv.org/abs/1603.09587">On the number of lattice convex chains</a>, arXiv:1603.09587 [math.PR], 2016.
%F 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)).
%F 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.
%e The two walks for n = 1 are
%e (0,0) -> (1,1)
%e (0,0) -> (1,0) -> (1,1).
%e The five possibilities for n = 2 are
%e (0,0) -> (2,2)
%e (0,0) -> (1,0) -> (2,1) -> (2,2)
%e (0,0) -> (1,0) -> (2,2)
%e (0,0) -> (2,0) -> (2,2)
%e (0,0) -> (2,1) -> (2,2).
%t 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}]}]
%t 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 *)
%Y Cf. A002774, A090806, A219554.
%K nonn,walk
%O 0,2
%A _Christoph Koutschan_, Apr 07 2016
|
