A191625 Number of n-step two-sided prudent self-avoiding walks ending at the northeast corner of their box.

1, 2, 4, 10, 24, 58, 140, 340, 828, 2022, 4948, 12130, 29780, 73202, 180124, 443614, 1093376, 2696622, 6654568, 16430016, 40583388, 100283298, 247890520, 612951190, 1516046060, 3750655206, 9281098840, 22970992024, 56864328080, 140790241078, 348635151944

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..750

Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, DMTCS proc. AJ, 2008, 167-180.

Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, arXiv:0804.4843 [math.CO], 2008-2009.

Enrica Duchi, On some classes of prudent walks, in: FPSAC'05, Taormina, Italy, 2005.

Formula

G.f.: (2*(1-t^2)*(1-t)*U/((1-t*U)*(2*t-U)))-1 with U = (1-t+t^2+t^3 -sqrt((1-t^4)*(1-2*t-t^2)))/(2*t).

a(n) ~ (1 - 3*r + (r-1)*sqrt(-7+8*r+24*r^2)) * (-40-22*r+35*r^2) / (37*r^n), where r = 0.40303171676268... is the root of the equation 1 - 2*r - 2*r^2 + 2*r^3 = 0. - Vaclav Kotesovec, Sep 10 2014

Conjecture: +(n+1)*a(n) -4*n*a(n-1) +(n-5)*a(n-2) +2*(4*n-3)*a(n-3) +3*(-n+3)*a(n-4) +2*(n-8)*a(n-5) +(-n+13)*a(n-6) +8*(-n+7)*a(n-7) +2*(n-7)*a(n-8) +2*(n-9)*a(n-9)=0. - R. J. Mathar, Sep 16 2017

Example

a(4) = 24: EEEE, EEEN, EENE, EENN, ENEE, ENEN, ENNE, ENNN, ESEN, NEEE, NEEN, NENE, NENN, NNEE, NNEN, NNNE, NNNN, NWNE, WNEE, WNEN, WNNE, SEEN, SENE, SENN.

Maple

U:= (1-t+t^2+t^3 -sqrt((1-t^4)*(1-2*t-t^2)))/(2*t):
gf:= (2*(1-t^2)*(1-t)*U/((1-t*U)*(2*t-U))) -1:
a:= n-> coeff(series(gf, t, n+4), t, n):
seq(a(n), n=0..30);

Mathematica

U = (1 - t + t^2 + t^3 - Sqrt[(1 - t^4)(1 - 2t - t^2)])/(2t);
gf = (2(1 - t^2)(1 - t) U/((1 - t U)(2t - U))) - 1;
a[n_] := SeriesCoefficient[gf, {t, 0, n}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 24 2018, from Maple *)

Crossrefs

Cf. A191605, A191652, A191653.

Sequence in context: A052542 A163271 A178036 * A253014 A110236 A191828

Adjacent sequences: A191622 A191623 A191624 * A191626 A191627 A191628

Keyword

nonn,walk

Author

Alois P. Heinz, Jun 09 2011

Status

approved