|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,walk
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
