keyword:walk - cp's OEIS frontend

A225094 Number A(n,k) of lattice paths without interior points from {n}^k to {0}^k using steps that decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 6, 2, 0, 1, 1, 24, 54, 2, 0, 1, 1, 120, 1944, 384, 2, 0, 1, 1, 720, 99000, 132000, 2550, 2, 0, 1, 1, 5040, 6966000, 79716000, 8059800, 16506, 2, 0, 1, 1, 40320, 655678800, 78928416000, 57010275000, 471369024, 105840, 2, 0, 1

Offset: 0

Alois P. Heinz, Apr 27 2013

An interior point p = (p_1, ..., p_k) has k>0 components with 0

			A(n,0) = 1: [()].
A(0,k) = 1: [{0}^k].
A(1,1) = 1: [(1), (0)].
A(2,1) = 0, there is no path from (2) to (0) without interior points.
A(1,2) = 2: [(1,1), (0,1), (0,0)], [(1,1), (1,0), (0,0)].
A(1,3) = 6: [(1,1,1), (0,1,1), (0,0,1), (0,0,0)], [(1,1,1), (0,1,1), (0,1,0), (0,0,0)], [(1,1,1), (1,0,1), (0,0,1), (0,0,0)], [(1,1,1), (1,0,1), (1,0,0), (0,0,0)], [(1,1,1), (1,1,0), (0,1,0), (0,0,0)], [(1,1,1), (1,1,0), (1,0,0), (0,0,0)].
Square array A(n,k) begins:
  1, 1, 1,     1,         1,              1, ...
  1, 1, 2,     6,        24,            120, ...
  1, 0, 2,    54,      1944,          99000, ...
  1, 0, 2,   384,    132000,       79716000, ...
  1, 0, 2,  2550,   8059800,    57010275000, ...
  1, 0, 2, 16506, 471369024, 38606650125120, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Columns k=0, 2-4 give: A000012, A040000, A060774, A225220.
Rows n=0-4 give: A000012, A000142, A071798(k) (for k>0), A225096, A225221.
Main diagonal gives: A225111.
Cf. A089759 (unrestricted paths), A210472, A262809, A263159.

b:= proc(n, l) option remember; local m; m:= nops(l);
      `if`(m=0 or l[m]=0, 1, `if`(l[1]>0 and l[m] b(n, [n$k]):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, l_] := b[n, l] = With[{m = Length[l]}, If[m == 0 || l[[m]] == 0, 1, If[l[[1]] > 0 && l[[m]] < n, 0, Sum[If[l[[i]] == 0, 0, b[n, Sort[ReplacePart[l, i -> l[[i]] - 1]]]], {i, 1, m}]]] ]; a[n_, k_] := b[n, Array[n&, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

A328908 Knight's tour on spirally numbered infinite chessboard, when the knight always jumps on the unvisited square closest to the origin, first according to 1-norm, then 2-norm, then number of the square: a(n) = number of the square visited at the n-th move.

Original entry on oeis.org

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 175

Offset: 0

M. F. Hasler, Oct 31 2019

Differs from A326924 (where only the 2-norm is considered) from a(73) = 175 on.
The sequence is also finite, when the knight lands on square number a(1092366) there is no unvisited square within reach.
The 1-norm or taxicab distance from the origin of the square a(n) is given in A328928(n).
It appears that this knight's tour would also completely fills the board, if we consider the infinite extension where the knight is allowed to move back on its last step(s) when there's no unvisited square available: no isolated sets of unvisited squares as defined in A323809, seem to occur. Is there a proof or disproof for this? - M. F. Hasler, Nov 04 2019

			The squares are numbered as in the spiral given in A174344 (upside down to get a counterclockwise spiral, but this is irrelevant here).
The knight starts at a(0) = 0 with coordinates (0, 0).
It jumps to a(1) = 9 with co-ordinates (2, -1): all 8 available squares (+-2, +-1) and (+-1, +-2) are at the same taxicab (2 + 1 = 3) and Euclidean distance (sqrt(2^2 + 1^2) = sqrt(5)) from the origin, but square number 9 has the smallest number.
a(73) = 175 with coordinates (7, 0) is the first destination which is preferred due to the 1-norm (= 7) over A326924(73) = 81 with coordinates (5, -4), having 1-norm 5 + 4 = 9 but Euclidean or 2-norm sqrt(41) smaller than 7.
a(1000) = 816 with coordinates (-10, -14).
a(2000) = 2568 with coordinates (-7, -25).
a(5000) = 4476 with coordinates (21, -33).
a(10000) = 15560 with coordinates (-2, -62).
a(20000) = 19566 with coordinates (-36, 70).
a(50000) = 62092 with coordinates (125, -33).
a(10^5) = 135634 with coordinates (-184, -26), taxicab distance 210 from the origin.
a(200'000) = 259798 with coordinates (47, 255).
a(500'000) = 713534 with coordinates (-68, -422).
a(1'000'000) = 995288 with coordinates (217, 499).
a(1'092'366) = 1165672 with coordinates (188, 540), taxicab norm 728 from the origin, is the last square visited by the knight before there is no unvisited square within reach.
By then the earliest square on the spiral not yet visited is number 629641 at (397, 396), taxicab norm 793, and the unvisited square closest to the origin is number 1794929 at (1, 670), taxicab norm 671.

M. F. Hasler, Table of n, a(n) for n = 0..100000
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.

Cf. A328928 for the "value" (= 1-norm) on the visited square.
Cf. A316328 ~ A316667, A326924, A328909 (variants).
Cf. A174344, A274923, A296030 (coordinates of square number n).

{Nmax=1e5;/* Full seq. with > 10^6 terms takes long to compute. */ local( K=[[(-1)^(i\2)<<(i>4),(-1)^i<<(i<5)]|i<-[1..8]], pos(x,y)=if(y>=abs(x),4*y^2-y-x,-x>=abs(y),4*x^2-x-y,-y>=abs(x),(4*y-3)*y+x,(4*x-3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, k], [k, 3*k+n]), t(x, p=pos(x[1],x[2]))=if(pt(x+K), K))[1][3], U=0,Umin=0); my(A=List(0)); for(n=1, Nmax, U+=1<<(A[n]-Umin); while(bittest(U,0), U>>=1;Umin++); iferr(listput(A, nxt(A[n])), E, break)); print("Index of the last term: ", #A-1); A328908(n)=A[n+1];}

A328928(n) = |A174344(a(n))| + |A274923(a(n))|, the 1-norm (or taxicab distance) of the square visited at the n-th step.

A001336 Number of n-step self-avoiding walks on f.c.c. lattice.

Original entry on oeis.org

1, 12, 132, 1404, 14700, 152532, 1573716, 16172148, 165697044, 1693773924, 17281929564, 176064704412, 1791455071068, 18208650297396, 184907370618612, 1876240018679868, 19024942249966812, 192794447005403916, 1952681556794601732, 19767824914170222996

Offset: 0

N. J. A. Sloane

B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 460.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrey Zabolotskiy, Table of n, a(n) for n = 0..24 (from Schram et al.)
M. E. Fisher and M. F. Sykes, Excluded-volume problem and the Ising model of ferromagnetism, Phys. Rev. 114 (1959), 45-58.
B. D. Hughes, Random Walks and Random Environments, vol. 1, Oxford 1995, Tables and references for self-avoiding walks counts [Annotated scanned copy of several pages of a preprint or a draft of chapter 7 "The self-avoiding walk"]
J. L. Martin, M. F. Sykes and F. T. Hioe, Probability of initial ring closure for self-avoiding walks on the face-centered cubic and triangular lattices, J. Chem. Phys., 46 (1967), 3478-3481.
S. McKenzie, Self-avoiding walks on the face-centered cubic lattice, J. Phys. A 12 (1979), L267-L270.
S. Redner, Distribution functions in the interior of polymer chains, J. Phys. A 13 (1980), 3525-3541, doi:10.1088/0305-4470/13/11/023.
Raoul D. Schram, Gerard T. Barkema, Rob H. Bisseling and Nathan Clisby, Exact enumeration of self-avoiding walks on BCC and FCC lattices, J. Stat. Mech. (2017) 083208; arXiv:1703.09340 [cond-mat.stat-mech], 2017. See Table II.
M. F. Sykes, Some counting theorems in the theory of the Ising problem and the excluded volume problem, J. Math. Phys., 2 (1961), 52-62.
Index entries for sequences related to f.c.c. lattice

Cf. A001411, A001412, A001334, A001666, A001337.

a(15) from Bert Dobbelaere, Jan 13 2019

Terms a(16) and beyond from Schram et al. added by Andrey Zabolotskiy, Feb 02 2022

A003192 Length of uncrossed knight's path on an n X n board.

Original entry on oeis.org

0, 0, 2, 5, 10, 17, 24, 35, 47

Offset: 1

N. J. A. Sloane

I used ZDD techniques to show that a(9)=47. (This is the longest uncrossed knight's path on a 9 X 9 board; thus I confirmed the conjecture that the paths of length 47, found by hand long ago, are indeed optimum.) - Don Knuth, Jun 24 2010

For best known results see link to Alex Chernov's site. - Dmitry Kamenetsky, Mar 02 2021

			Lengths of longest uncrossed knight's paths on all sufficiently small rectangular boards m X n, with 3 <= m <= n:
......2...4...5...6...8...9..10
..........5...7...9..11..13..15
.............10..14..16..19..22
.................17..21..25..29
.....................24..30..35
.........................35..42
.............................47

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, CSLI, Stanford, CA, 2010. (CSLI Lecture Notes, vol. 192)
J. S. Madachy, Letter to N. J. A. Sloane, Apr 26 1975.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Various authors, Uncrossed knight's tours, J. Rec. Math., 2 (1969), 154-157.
L. D. Yarbrough, Uncrossed knight's tours, J. Rec. Math., 1 (No. 3, 1969), 140-142.

Alex Chernov, Uncrossed Knight's Tours.
George Jelliss, Non-Intersecting Paths.
J. S. Madachy, Letter to N. J. A. Sloane, Apr 26 1975.
Jean-Charles Meyrignac, Non-crossing knight tours.
N. J. A. Sloane, Illustration of initial terms
Various authors, Uncrossed knight's tours, J. Rec. Math., 2 (1969), 154-157. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Knight's Tour
L. D. Yarbrough, Uncrossed knight's tours, J. Rec. Math., 1 (No. 3, 1969), 140-142. [Annotated scanned copy]

Cf. A157416.

a(1)=a(2)=0 prepended by Max Alekseyev, Jul 17 2011

A039699 Number of 4-dimensional cubic lattice walks that start and end at the origin after 2n steps, free to pass through origin at intermediate stages.

Original entry on oeis.org

1, 8, 168, 5120, 190120, 7939008, 357713664, 16993726464, 839358285480, 42714450658880, 2225741588095168, 118227198981126144, 6380762273973278464, 349019710593278412800, 19310744204362333900800, 1079054103459778710405120, 60818479243449308702049960

Offset: 0

Alessandro Zinani (alzinani(AT)tin.it)

Generating function G(x) is D-finite with a singular point at x = 1/64 (cf. Graph Link). After summing 300000 terms, G(1/64) = 1.239466... and 1 - 1/G(1/64) = 0.193201... Convergence to A086232 is very slow. - Bradley Klee, Aug 20 2018

a(n) is also the constant term in the expansion of (w + 1/w + x + 1/x + y + 1/y + z + 1/z)^(2n). This follows directly from the sequence name, each variable corresponding to a single step in one of the four axis directions. - Christopher J. Smyth, Sep 28 2018

			a(5)=7939008, i.e., there are 7939008 different walks that start and end at origin of a 4-dimensional integer lattice after 2*5=10 steps, free to pass through origin at intermediate steps.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 322-331.

Seiichi Manyama, Table of n, a(n) for n = 0..557
S. R. Finch, Symmetric Random Walk on n-Dimensional Integer Lattice. [broken link]
Steven R. Finch, Symmetric Random Walk on n-Dimensional Integer Lattice. [Cached copy, with permission of the author]
S. Hassani, J.-M. Maillard, and N. Zenine, On the diagonals of rational functions: the minimal number of variables (unabridged version), arXiv:2502.05543 [math-ph], 2025. See pp. 33, 44.
Bradley Klee, Graph of g.f.
Gilbert Labelle and Annie Lacasse, Closed paths whose steps are roots of unity, in FPSAC 2011, Reykjavik, Iceland DMTCS proc. AO, 2011, 599-610.
Yen Lee Loh, A general method for calculating lattice Green functions on the branch cut, arXiv:1706.03083 [math-ph], 2017.
J. Novak, Pólya's random walk theorem, arXiv:1301.3916 [math.PR], 2013.

1-dimensional, 2-dimensional, 3-dimensional analogs are A000984, A002894, A002896. Pólya Constant: A086232.

Row k=4 of A287318.

A039699 := n -> binomial(2*n,n)^2*hypergeom([1/2, -n, -n, -n],[1, 1, 1/2 - n], 1):
seq(simplify(A039699(n)), n=0..14); # Peter Luschny, May 23 2017

max = 30 (* must be even *); Partition[ CoefficientList[ Series[ BesselI[0, 2 x]^4, {x, 0, max}], x]*Range[0, max]!, 2][[All, 1]] (* Jean-François Alcover, Oct 05 2011 *)
With[{nn=30},Take[CoefficientList[Series[BesselI[0,2x]^4,{x,0,nn}],x] Range[0,nn]!,{1,-1,2}]] (* Harvey P. Dale, Aug 09 2013 *)
RecurrenceTable[{256*(n-1)^2*(2*n-3)*(2*n-1)*a[n-2] - 4*(2*n-1)^2*(5*n^2-5*n+2)*a[n-1] + n^4*a[n]==0, a[0]==1, a[1]==8}, a, {n,0,100}] (* Bradley Klee, Aug 20 2018 *)

C=binomial;
A002895(n) = sum(k=0,n, C(n,k)^2 * C(2*n-2*k,n-k) * C(2*k,k) );
a(n)= C(2*n,n) * A002895(n);
/* Joerg Arndt, Apr 19 2013 */

from math import comb
def A039699(n): return comb(n<<1,n)*((sum(comb(n,k)**2*comb(n-k<<1,n-k)*comb(m:=k<<1,k) for k in range(n+1>>1))<<1) + (0 if n&1 else comb(n,n>>1)**4)) # Chai Wah Wu, Jun 17 2025

E.g.f.: Sum_{n>=0} a(2*n) * x^(2*n)/(2*n)! = I_0(2*x)^4. (I = Modified Bessel function of the first kind).
a(n) = binomial(2*n,n)*A002895(n). - Mark van Hoeij, Apr 19 2013
a(n) = binomial(2*n,n)^2*hypergeom([1/2,-n,-n,-n],[1,1,1/2-n],1). - Peter Luschny, May 23 2017
a(n) ~ 2^(6*n+1) / (Pi*n)^2. - Vaclav Kotesovec, Nov 13 2017
From Bradley Klee, Aug 20 2018: (Start)
G.f.: Define G(x) = Sum_{n>=0} a(n)*x^n and G^(j) = (d/dx)^j G(x), then Sum_{j=0..4,k=0..5} M_{j,k}*G^(j)*x^k = 0, with
M={{-8, 768, 0, 0, 0, 0}, {1, -424, 14592, 0, 0, 0}, {0, 7, -1172, 25344, 0, 0}, {0, 0, 6, -640, 10240, 0}, {0, 0, 0, 1, -80, 1024}}.
Sum_{j=0..2,k=0..4} M_{j,k}*a(n-j)*n^k = 0, with
M={{0, 0, 0, 0, 1}, {-8, 52, -132, 160, -80}, {768, -3584, 5888, -4096, 1024}}.
(End)
a(n) = Sum_{i+j+k+l=n, 0<=i,j,k,l<=n} multinomial(2n [i,i,j,j,k,k,l,l]). - Shel Kaphan, Jan 16 2023

A174319 Number of n-step walks on cubic lattice (no points repeated, no adjacent points unless consecutive in path).

Original entry on oeis.org

1, 6, 30, 126, 534, 2214, 9246, 38142, 157974, 649086, 2675022, 10966470, 45054630, 184400910, 755930958, 3089851782, 12645783414, 51635728518, 211059485310, 861083848998, 3516072837894, 14334995983614, 58485689950254

Offset: 0

Joseph Myers, Nov 27 2010

Fisher and Hiley give 2674926 as their last term instead of 2675022 (see A002934). Douglas McNeil confirms the correction on the seqfan list.

In the notation of Nemirovsky et al. (1992), a(n), the n-th term of the current sequence is C_{n,m} with m=0 (and d=3). Here, for a d-dimensional hypercubic lattice, C_{n,m} is "the number of configurations of an n-bond self-avoiding chain with m neighbor contacts." (Let n >= 1. For d=2, we have C(n,0) = A173380(n); for d=4, we have C(n,0) = A034006(n); and for d=5, we have C(n,0) = A038726(n).) - Petros Hadjicostas, Jan 03 2019

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. E. Fisher and B. J. Hiley, Configuration and free energy of a polymer molecule with solvent interaction, J. Chem. Phys., 34 (1961), 1253-1267.
A. M. Nemirovsky, K. F. Freed, T. Ishinabe, and J. F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.

Cf. A002934, A038746, A038748.

a(n) = 6 + 24*A038746(n) + 48*A038748(n) for n >= 1. (It follows from Eq. (5), p. 1090, in Nemirovsky et al. (1992).) - Petros Hadjicostas, Jan 01 2019

a(16)-a(22) from Bert Dobbelaere, Jan 03 2019

A210472 Number A(n,k) of paths starting at {n}^k to a border position where one component equals 0 using steps that decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 33, 20, 1, 0, 1, 5, 196, 543, 70, 1, 0, 1, 6, 1305, 22096, 10497, 252, 1, 0, 1, 7, 9786, 1304045, 3323092, 220503, 924, 1, 0, 1, 8, 82201, 106478916, 1971644785, 574346824, 4870401, 3432, 1, 0

Offset: 0

Alois P. Heinz, Jan 22 2013

			A(0,3) = 1: [(0,0,0)].
A(1,1) = 1: [(1), (0)].
A(1,2) = 2: [(1,1), (0,1)], [(1,1), (1,0)].
A(1,3) = 3: [(1,1,1), (0,1,1)], [(1,1,1), (1,0,1)], [(1,1,1), (1,1,0)].
A(2,1) = 1: [(2), (1), (0)].
A(2,2) = 6: [(2,2), (1,2), (0,2)], [(2,2), (1,2), (1,1), (0,1)], [(2,2), (1,2), (1,1), (1,0)], [(2,2), (2,1), (1,1), (0,1)], [(2,2), (2,1), (1,1), (1,0)], [(2,2), (2,1), (2,0)].
Square array A(n,k) begins:
  0, 1,   1,      1,         1,             1, ...
  0, 1,   2,      3,         4,             5, ...
  0, 1,   6,     33,       196,          1305, ...
  0, 1,  20,    543,     22096,       1304045, ...
  0, 1,  70,  10497,   3323092,    1971644785, ...
  0, 1, 252, 220503, 574346824, 3617739047205, ...

Alois P. Heinz, Antidiagonals n = 0..24, flattened

Columns k=0-4 give: A000004, A000012, A000984, A209245, A209288.
Rows n=0-3 give: A057427, A001477, A093964, A210486.
Main diagonal gives A276490.
Cf. A089759 (unrestricted paths), A225094, A262809, A263159.

b:= proc() option remember; `if`(nargs=0, 0, `if`(args[1]=0, 1,
      add(b(sort(subsop(i=args[i]-1, [args]))[]), i=1..nargs)))
    end:
A:= (n, k)-> b(n$k):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[] = 0; b[args__] := b[args] = If[First[{args}] == 0, 1, Sum[b @@ Sort[ReplacePart[{args}, i -> {args}[[i]] - 1]], {i, 1, Length[{args}]}]]; a[n_, k_] := b @@ Array[n&, k]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

Previous Showing 61-70 of 4476 results. Next

cp's OEIS Frontend

A039648 Number of n-step self-avoiding paths on the first octant of a 3-dimensional cubic lattice, starting at the origin.

Views

Author

Keywords

Crossrefs

Extensions

A135388 Number of (directed) Eulerian circuits on the complete graph K_{2n+1}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A145157 Number of Greek-key tours on an n X n board; i.e., self-avoiding walks on n X n grid starting in top left corner.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A225094 Number A(n,k) of lattice paths without interior points from {n}^k to {0}^k using steps that decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A328908 Knight's tour on spirally numbered infinite chessboard, when the knight always jumps on the unvisited square closest to the origin, first according to 1-norm, then 2-norm, then number of the square: a(n) = number of the square visited at the n-th move.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A001336 Number of n-step self-avoiding walks on f.c.c. lattice.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A003192 Length of uncrossed knight's path on an n X n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A039699 Number of 4-dimensional cubic lattice walks that start and end at the origin after 2n steps, free to pass through origin at intermediate stages.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula