|
| |
|
|
A277756
|
|
Total number of nodes summed over all self-avoiding planar walks starting at (0,0), ending at (n,n), remaining in the first quadrant and using steps (0,1) and (1,0) on or below the diagonal and using steps (1,1), (-1,1), and (1,-1) on or above the diagonal.
|
|
3
|
|
|
|
1, 5, 32, 224, 1723, 14569, 135286, 1375882, 15263414, 183817326, 2391291386, 33443618930, 500611975023, 7988044467121, 135376576319870, 2428721569276698, 45988428905194350, 916607431346170686, 19182997480530342168, 420606731490047403144
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Both endpoints of each step have to satisfy the given restrictions.
a(n) is odd for n in {0, 1, 4, 5, 12, 13, ...} = { 2^i-4, 2^i-3 | i>=2 }.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Recurrence: n^2*(n+1)*(8*n^16 - 324*n^15 + 6627*n^14 - 87027*n^13 + 780619*n^12 - 4852225*n^11 + 20603783*n^10 - 54969555*n^9 + 52518873*n^8 + 263990331*n^7 - 1493664427*n^6 + 3993049393*n^5 - 6338994427*n^4 + 5219525379*n^3 - 208155582*n^2 - 3017597166*n + 1500639210)*a(n) = (16*n^20 - 512*n^19 + 7810*n^18 - 63907*n^17 + 125587*n^16 + 3122233*n^15 - 38493280*n^14 + 230844282*n^13 - 835406452*n^12 + 1696593140*n^11 - 205259278*n^10 - 11408670034*n^9 + 41877803802*n^8 - 78160407832*n^7 + 66176874282*n^6 + 28732169489*n^5 - 121052415075*n^4 + 101990581575*n^3 - 30017409912*n^2 + 2376230256*n - 1500639210)*a(n-1) - (8*n^21 - 108*n^20 - 1537*n^19 + 68210*n^18 - 1094143*n^17 + 10095374*n^16 - 55215407*n^15 + 145867798*n^14 + 207571130*n^13 - 3618003314*n^12 + 16712054348*n^11 - 45380132762*n^10 + 68844700788*n^9 + 3118224998*n^8 - 280665562873*n^7 + 597311526024*n^6 - 339913057015*n^5 - 736454012982*n^4 + 1583292134673*n^3 - 1163990061738*n^2 + 239783072958*n + 66391169670)*a(n-2) + 2*(48*n^21 - 1536*n^20 + 23158*n^19 - 183757*n^18 + 221058*n^17 + 11736518*n^16 - 139812764*n^15 + 849893261*n^14 - 3103145857*n^13 + 5885285434*n^12 + 4549993672*n^11 - 76009600910*n^10 + 293460263060*n^9 - 661116809084*n^8 + 807883602348*n^7 + 2415933549*n^6 - 1768326853960*n^5 + 2768261414022*n^4 - 1612284665202*n^3 - 46857648087*n^2 + 218218164669*n + 98070916860)*a(n-3) - 4*(96*n^21 - 3824*n^20 + 76108*n^19 - 967312*n^18 + 8230515*n^17 - 45136547*n^16 + 127907470*n^15 + 169884028*n^14 - 3686404098*n^13 + 20071768963*n^12 - 67940536761*n^11 + 154148555189*n^10 - 193594359619*n^9 - 89277087131*n^8 + 921649634933*n^7 - 1534876599357*n^6 - 198633061278*n^5 + 4903659055674*n^4 - 8336147283495*n^3 + 5973270250797*n^2 - 1064158064361*n - 539137461240)*a(n-4) + 8*(n-4)^2*(2*n - 9)^2*(2*n - 7)*(8*n^16 - 196*n^15 + 2727*n^14 - 23789*n^13 + 119465*n^12 - 267991*n^11 - 414841*n^10 + 5444929*n^9 - 23332455*n^8 + 66119405*n^7 - 117282857*n^6 + 58753831*n^5 + 267053105*n^4 - 695018505*n^3 + 683003538*n^2 - 193704714*n - 67206510)*a(n-5). - Vaclav Kotesovec, Apr 25 2017
a(n) ~ c * n^(n + 7/2) / exp(n), where c = 0.81569546019... - Vaclav Kotesovec, Apr 25 2017
|
|
|
MAPLE
|
b:= proc(x, y, t) option remember; `if`(x<0 or y<0, 0,
`if`(x=0 and y=0, [1$2], (p-> p+[0, p[1]])(
`if`(y<x, b(x-1, y, 0), 0)+ `if`(y<=x,
b(x, y-1, 0), 0)+`if`(y>=x, b(x-1, y-1, 0), 0)+
`if`(y>x+1 and t<>2, b(x+1, y-1, 1), 0)+
`if`(y>=x and t<>1, b(x-1, y+1, 2), 0))))
end:
a:= n-> b(n$2, 0)[2]:
seq(a(n), n=0..25);
|
|
|
MATHEMATICA
|
b[x_, y_, t_] := b[x, y, t] = If[x < 0 || y < 0, {0, 0}, If[x == 0 && y == 0, {1, 1}, # + {0, #[[1]]}&[If[y < x, b[x-1, y, 0], 0] + If[y <= x, b[x, y-1, 0], 0] + If[y >= x, b[x-1, y-1, 0], 0] + If[y > x+1 && t != 2, b[x+1, y-1, 1], 0] + If[y >= x && t != 1, b[x-1, y+1, 2], 0]]]];
a[n_] := b[n, n, 0][[2]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,walk
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
