keyword:walk - cp's OEIS frontend

A150500 Number of walks within N^3 (the first octant of Z^3) starting at (0,0,0) and consisting of n steps taken from {(-1, -1, -1), (-1, -1, 1), (0, 1, 0), (1, 1, -1), (1, 1, 1)}.

1, 2, 7, 25, 101, 416, 1787, 7792, 34645, 155722, 707795, 3242515, 14963665, 69458000, 324102287, 1519028843, 7147771981, 33750528146, 159860887355, 759295147045, 3615520821281, 17255165910632, 82521746019487, 395404081034830, 1897886817388201, 9124229781131546, 43930513066698367, 211803668881914847

Offset: 0

Manuel Kauers, Nov 18 2008

Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.
Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

Cf. A201805.

aux[i_Integer, j_Integer, k_Integer, n_Integer] := Which[Min[i, j, k, n] < 0 || Max[i, j, k] > n, 0, n == 0, KroneckerDelta[i, j, k, n], True, aux[i, j, k, n] = aux[-1 + i, -1 + j, -1 + k, -1 + n] + aux[-1 + i, -1 + j, 1 + k, -1 + n] + aux[i, -1 + j, k, -1 + n] + aux[1 + i, 1 + j, -1 + k, -1 + n] + aux[1 + i, 1 + j, 1 + k, -1 + n]]; Table[Sum[aux[i, j, k, n], {i, 0, n}, {j, 0, n}, {k, 0, n}], {n, 0, 10}]

a(n) = (A201805(n+1) + 3*A201805(n))/4. - Mark van Hoeij, Nov 29 2024

A271432 Number of n-step excursions on the 4-dimensional f.c.c. lattice.

Original entry on oeis.org

1, 0, 24, 192, 3384, 51840, 911040, 16369920, 307009080, 5902176000, 116083727424, 2323941903360, 47232891389376, 972252599205888, 20233078205573376, 425067670281526272, 9004456318854367800, 192148701659269774848

Offset: 0

Christoph Koutschan, Apr 07 2016

a(n) = number of walks in Z^4 starting and ending at the origin, using only the steps (a,b,0,0), (a,0,b,0), ..., (0,0,a,b), where a,b can be +1 or -1.

			There is one walk with no steps.
No walk with a single steps returns to the origin.
The number of returning walks with two steps is exactly the number of allowed steps (called the coordination number of the lattice): a(2) = 4*binomial(4,2).

Christoph Koutschan, Table of n, a(n) for n = 0..729
D. Broadhurst, Bessel moments, random walks and Calabi-Yau equations.
A. J. Guttmann, Lattice Green's functions in all dimensions, J. Phys. A: Math. Theor. 43 (2010), 305205.
C. Koutschan, Computations for higher-dimensional fcc lattices.
C. Koutschan, Lattice Green's Functions of the Higher-Dimensional Face-Centered Cubic Lattices, arXiv:1108.2164 [math.CO], 2011-2013.
C. Koutschan, Lattice Green's functions of the higher-dimensional face-centered cubic lattices, J. Phys. A: Math. Theor. 46(12) (2013), 125005.

Cf. A002899 (d = 3, i.e., excursions on the 3-dimensional f.c.c. lattice), this sequence (d = 4), A271650 (d = 5), A271651 (d = 6), A271670 (d = 7), A271671 (d = 8), A271672 (d = 9), A271673 (d = 10), A271674 (d = 11).

nmax := 50: tt := [seq([seq(add(binomial(2*p,p)*binomial(2*j,2*p-n)*binomial(2*n+2*j-2*p,n+j-p), p = floor((n+1)/2)..floor((n+2*j)/2)), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: for d1 from 3 to 4 do tt := [seq([seq(add(binomial(n,p)*add(binomial(2*j,2*q-p)*binomial(2*j+2*p-2*q,j+p-q)*tt[n-p+1,q+1], q = floor((p+1)/2)..floor((p+2*j)/2)), p = 0..n), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: od: [seq(tt[n+1,1], n = 0..nmax)];

a[0] = 1; a[1] = 0; a[2] = 24; a[3] = 192; a[4] = 3384; a[n_] := a[n] = (27648*(-4 + n)*(-3 + n)^2*(-2 + n)*(-8 + 35*n^2)*a[-5 + n] + 6912*(-3 + n)*(-2 + n)*(-132 + 62*n + 676*n^2 - 525*n^3 + 105*n^4)*a[-4 + n] + 144*(-2 + n)*(1440 - 352*n - 11430*n^2 + 15435*n^3 - 7350*n^4 + 1225*n^5)*a[-3 + n] + 8*(72 - 3738*n + 17065*n^2 - 29745*n^3 + 25150*n^4 - 10500*n^5 + 1750*n^6)*a[-2 + n] - (-1 + n)*(144 - 540*n + 487*n^2 + 151*n^3 - 315*n^4 + 105*n^5)*a[-1 + n])/(n^4*(27 - 70*n + 35*n^2)); Array[a, 30, 0]
nmax = 50; T = Table[Sum[Binomial[2 p, p]*Binomial[2 j, 2 p - n]*Binomial[2 n + 2 j - 2 p, n + j - p], {p, Floor[(n + 1)/2], Floor[(n + 2 j)/2]}], {n, 0, nmax}, {j, 0, Floor[(nmax - n)/2]}]; Do[T = Table[Sum[Binomial[n, p]*Sum[Binomial[2 j, 2 q - p]*Binomial[2 j + 2 p - 2 q, j + p - q]*T[[n - p + 1, q + 1]], {q, Floor[(p + 1)/2], Floor[(p + 2 j)/2]}], {p, 0, n}], {n, 0, nmax}, {j, 0, If[d1 < 4, Floor[(nmax - n)/2], 0]}], {d1, 3, 4}]; First /@ T

a(n) satisfies the fifth-order linear recurrence equation (35*n^2-70*n+27)*n^4*a(n) +(n-1)*(105*n^5-315*n^4+151*n^3 +487*n^2 -540*n+144)*a(n-1) -8*(1750*n^6-10500*n^5+25150*n^4 -29745*n^3 +17065*n^2-3738*n+72)*a(n-2) -144*(n-2) *(1225*n^5-7350*n^4 +15435*n^3 -11430*n^2-352*n+1440)*a(n-3)-6912*(n-3)*(n-2)*(105*n^4 -525*n^3+676*n^2 +62*n-132)*a(n-4)-27648*(n-4)*(n-3)^2*(n-2)*(35*n^2-8) *a(n-5) = 0.
The generating function P(z) = Sum_{n>=0} a(n)*(z/24)^n is given by the 4-fold integral (1/Pi)^4 Int_{0..Pi} ... Int_{0..Pi} 1/(1-z*lambda_4) dk_1 ... dk_4, where the structure function is defined as lambda_4 = (1/binomial(4,2)) Sum_{i=1..4} Sum_{j=(i+1)..4} cos(k_i)*cos(k_j). The function P(z) satisfies the fourth-order linear ODE 12*z*(256+632*z+702*z^2+382*z^3+98*z^4+9*z^5)*P(z)+12*(-384+224*z+3716*z^2+7633*z^3 +6734*z^4+2939*z^5+604*z^6+45*z^7) *P'(z)+6*z*(-5376-5248*z+11080*z^2 +25286*z^3 +19898*z^4+7432*z^5 +1286*z^6+81*z^7) *P''(z)+2*z^2*(4+3*z)*(-3456-2304*z+3676*z^2+4920 *z^3+2079*z^4+356*z^5 +21*z^6)*P'''(z)+(-1+z)*z^3*(2+z)*(3+z)*(6+z)*(8+z)*(4+3*z)^2*P''''(z) = 0.
a(n) ~  2^(3*n+1) * 3^n / (Pi^2 * n^2). - Vaclav Kotesovec, Apr 08 2016

A271650 Number of n-step excursions on the 5-dimensional f.c.c. lattice.

Original entry on oeis.org

1, 0, 40, 480, 11880, 281280, 7506400, 210268800, 6166993000, 187069411200, 5833030976640, 186014056166400, 6044435339896800, 199561060892793600, 6679216425794140800, 226213441773789550080, 7741313040820500484200

Offset: 0

Christoph Koutschan, Apr 11 2016

a(n) = number of walks in the integer lattice Z^5 starting and ending at the origin, using only the steps of the form (s_1, ..., s_5) with s_1^2 + ... + s_5^2 = 2, i.e., each possible step has precisely two nonzero entries which can be +1 or -1.

			There is one walk with no steps.
No walk with a single steps returns to the origin.
The number of returning walks with two steps is exactly the number of allowed steps (called the coordination number of the lattice): a(2) = 4*binomial(5,2).

Christoph Koutschan, Table of n, a(n) for n = 0..629
D. Broadhurst, Bessel moments, random walks and Calabi-Yau equations.
A. J. Guttmann, Lattice Green's functions in all dimensions, J. Phys. A.: Math. Theor. 43 (2010) 305205
C. Koutschan, Computations for higher-dimensional fcc lattices.
C. Koutschan, Differential operator annihilating the generating function.
C. Koutschan, Recurrence equation.
C. Koutschan, Lattice Green's Functions of the Higher-Dimensional Face-Centered Cubic Lattices, arXiv:1108.2164 [math.CO], 2011-2013.
C. Koutschan, Lattice Green's functions of the higher-dimensional face-centered cubic lattices, Journal of Physics A: Mathematical and Theoretical 46(12) (2013), 125005.

Cf. A002899 (d = 3, i.e., excursions on the 3-dimensional f.c.c. lattice), A271432 (d = 4), this sequence (d = 5), A271651 (d = 6), A271670 (d = 7), A271671 (d = 8), A271672 (d = 9), A271673 (d = 10), A271674 (d = 11).

nmax := 50: tt := [seq([seq(add(binomial(2*p,p)*binomial(2*j,2*p-n)*binomial(2*n+2*j-2*p,n+j-p), p = floor((n+1)/2)..floor((n+2*j)/2)), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: for d1 from 3 to 5 do tt := [seq([seq(add(binomial(n,p)*add(binomial(2*j,2*q-p)*binomial(2*j+2*p-2*q,j+p-q)*tt[n-p+1,q+1], q = floor((p+1)/2)..floor((p+2*j)/2)), p = 0..n), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: od: [seq(tt[n+1,1], n = 0..nmax)];

nmax = 50; T = Table[Sum[Binomial[2 p, p]*Binomial[2 j, 2 p - n]*Binomial[2 n + 2 j - 2 p, n + j - p], {p, Floor[(n + 1)/2], Floor[(n + 2 j)/2]}], {n, 0, nmax}, {j, 0, Floor[(nmax - n)/2]}]; Do[T = Table[Sum[Binomial[n, p]*Sum[Binomial[2 j, 2 q - p]*Binomial[2 j + 2 p - 2 q, j + p - q]*T[[n - p + 1, q + 1]], {q, Floor[(p + 1)/2], Floor[(p + 2 j)/2]}], {p, 0, n}], {n, 0, nmax}, {j, 0, If[d1 < 5, Floor[(nmax - n)/2], 0]}], {d1, 3, 5}]; First /@ T

a(n) satisfies a seventh-order linear recurrence equation with polynomial coefficients of degree 12 (see link above).

The probability generating function P(z) = Sum_{n>=0} a(n)*(z/40)^n is given by the 5-fold integral (1/Pi)^5 Int_{0..Pi} ... Int_{0..Pi} 1/(1-z*lambda_5) dk_1 ... dk_5, where the structure function is defined as lambda_5 = (1/binomial(5,2)) Sum_{i=1..5} Sum_{j=(i+1)..5} cos(k_i)*cos(k_j). The function P(z) satisfies a sixth-order linear ODE with polynomial coefficients of degree 17 (see link above).

A271651 Number of n-step excursions on the 6-dimensional f.c.c. lattice.

Original entry on oeis.org

1, 0, 60, 960, 30780, 996480, 36560400, 1430553600, 59089923900, 2543035488000, 113129280527760, 5170796720812800, 241741903350301200, 11520044551208793600, 558061378022616811200, 27421336248833005839360

Offset: 0

Christoph Koutschan, Apr 11 2016

a(n) = number of walks in the integer lattice Z^6 starting and ending at the origin, using only the steps of the form (s_1, ..., s_6) with s_1^2 + ... + s_6^2 = 2, i.e., each possible step has precisely two nonzero entries which can be +1 or -1.

			There is one walk with no steps.
No walk with a single steps returns to the origin.
The number of returning walks with two steps is exactly the number of allowed steps (called the coordination number of the lattice): a(2) = 4*binomial(6,2).

Christoph Koutschan, Table of n, a(n) for n = 0..567
C. Koutschan, Computations for higher-dimensional fcc lattices.
C. Koutschan, Differential operator annihilating the generating function.
C. Koutschan, Recurrence equation.
C. Koutschan, Lattice Green's Functions of the Higher-Dimensional Face-Centered Cubic Lattices, arXiv:1108.2164 [math.CO], 2011-2013.
C. Koutschan, Lattice Green's functions of the higher-dimensional face-centered cubic lattices, Journal of Physics A: Mathematical and Theoretical 46(12) (2013), 125005.

Cf. A002899 (d = 3, i.e., excursions on the 3-dimensional f.c.c. lattice), A271432 (d = 4), A271650 (d = 5), this sequence (d = 6), A271670 (d = 7), A271671 (d = 8), A271672 (d = 9), A271673 (d = 10), A271674 (d = 11).

nmax := 50: tt := [seq([seq(add(binomial(2*p,p)*binomial(2*j,2*p-n)*binomial(2*n+2*j-2*p,n+j-p), p = floor((n+1)/2)..floor((n+2*j)/2)), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: for d1 from 3 to 6 do tt := [seq([seq(add(binomial(n,p)*add(binomial(2*j,2*q-p)*binomial(2*j+2*p-2*q,j+p-q)*tt[n-p+1,q+1], q = floor((p+1)/2)..floor((p+2*j)/2)), p = 0..n), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: od: [seq(tt[n+1,1], n = 0..nmax)];

nmax = 50; T = Table[Sum[Binomial[2 p, p]*Binomial[2 j, 2 p - n]*Binomial[2 n + 2 j - 2 p, n + j - p], {p, Floor[(n + 1)/2], Floor[(n + 2 j)/2]}], {n, 0, nmax}, {j, 0, Floor[(nmax - n)/2]}]; Do[T = Table[Sum[Binomial[n, p]*Sum[Binomial[2 j, 2 q - p]*Binomial[2 j + 2 p - 2 q, j + p - q]*T[[n - p + 1, q + 1]], {q, Floor[(p + 1)/2], Floor[(p + 2 j)/2]}], {p, 0, n}], {n, 0, nmax}, {j, 0, If[d1 < 6, Floor[(nmax - n)/2], 0]}], {d1, 3, 6}]; First /@ T

a(n) satisfies a twelfth-order linear recurrence equation with polynomial coefficients of degree 33 (see link above).

The probability generating function P(z) = Sum_{n>=0} a(n)*(z/60)^n is given by the 6-fold integral (1/Pi)^6 Int_{0..Pi} ... Int_{0..Pi} 1/(1-z*lambda_6) dk_1 ... dk_6, where the structure function is defined as lambda_6 = (1/binomial(6,2)) Sum_{i=1..6} Sum_{j=(i+1)..6} cos(k_i)*cos(k_j). The function P(z) satisfies an eighth-order linear ODE with polynomial coefficients of degree 43 (see link above).

A271670 Number of n-step excursions on the 7-dimensional f.c.c. lattice.

Original entry on oeis.org

1, 0, 84, 1680, 66276, 2731680, 128704800, 6555265920, 355588928100, 20247799145280, 1198746727590384, 73266532153214400, 4598338364703822816, 295145004688715301120, 19311431876483926443264

Offset: 0

Christoph Koutschan, Apr 12 2016

a(n) = number of walks in the integer lattice Z^7 starting and ending at the origin, using only the steps of the form (s_1, ..., s_7) with s_1^2 + ... + s_7^2 = 2, i.e., each possible step has precisely two nonzero entries which can be +1 or -1.

			There is one walk with no steps.
No walk with a single steps returns to the origin.
The number of returning walks with two steps is exactly the number of allowed steps (called the coordination number of the lattice): a(2) = 4*binomial(7,2).

Christoph Koutschan, Table of n, a(n) for n = 0..524
C. Koutschan, Computations for higher-dimensional fcc lattices.
C. Koutschan, Differential operator annihilating the generating function.
C. Koutschan, Recurrence equation.
N. Zenine, S. Hassani, J-M. Maillard, Lattice Green Functions: the seven-dimensional face-centred cubic lattice, arXiv:1409.8615 [math-ph], 2014.
N. Zenine, S. Hassani, J-M. Maillard, Lattice Green Functions: the seven-dimensional face-centred cubic lattice, Journal of Physics A: Mathematical and Theoretical 48 (2015), 035205.

Cf. A002899 (d = 3, i.e., excursions on the 3-dimensional f.c.c. lattice), A271432 (d = 4), A271650 (d = 5), A271651 (d = 6), this sequence (d = 7), A271671 (d = 8), A271672 (d = 9), A271673 (d = 10), A271674 (d = 11).

nmax := 50: tt := [seq([seq(add(binomial(2*p,p)*binomial(2*j,2*p-n)*binomial(2*n+2*j-2*p,n+j-p), p = floor((n+1)/2)..floor((n+2*j)/2)), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: for d1 from 3 to 7 do tt := [seq([seq(add(binomial(n,p)*add(binomial(2*j,2*q-p)*binomial(2*j+2*p-2*q,j+p-q)*tt[n-p+1,q+1], q = floor((p+1)/2)..floor((p+2*j)/2)), p = 0..n), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: od: [seq(tt[n+1,1], n = 0..nmax)];

nmax = 50; T = Table[Sum[Binomial[2 p, p]*Binomial[2 j, 2 p - n]*Binomial[2 n + 2 j - 2 p, n + j - p], {p, Floor[(n + 1)/2], Floor[(n + 2 j)/2]}], {n, 0, nmax}, {j, 0, Floor[(nmax - n)/2]}]; Do[T = Table[Sum[Binomial[n, p]*Sum[Binomial[2 j, 2 q - p]*Binomial[2 j + 2 p - 2 q, j + p - q]*T[[n - p + 1, q + 1]], {q, Floor[(p + 1)/2], Floor[(p + 2 j)/2]}], {p, 0, n}], {n, 0, nmax}, {j, 0, If[d1 < 7, Floor[(nmax - n)/2], 0]}], {d1, 3, 7}]; First /@ T

a(n) conjecturally satisfies a linear recurrence equation of order 15 with polynomial coefficients of degree 56 (see link above).

The probability generating function P(z) = Sum_{n>=0} a(n)*(z/84)^n is given by the 7-fold integral (1/Pi)^7 Int_{0..Pi} ... Int_{0..Pi} 1/(1-z*lambda_7) dk_1 ... dk_7, where the structure function is defined as lambda_7 = (1/binomial(7,2)) Sum_{i=1..7} Sum_{j=(i+1)..7} cos(k_i)*cos(k_j). The function P(z) conjecturally satisfies an eleventh-order linear ODE with polynomial coefficients of degree 68 (see link above).

A271671 Number of n-step excursions on the 8-dimensional f.c.c. lattice.

Original entry on oeis.org

1, 0, 112, 2688, 126000, 6316800, 364887040, 23038364160, 1562288430640, 112014905049600, 8399872737107712, 653454438359331840, 52412319029000899584, 4313870772211888183296, 362994066330649023029760

Offset: 0

Christoph Koutschan, Apr 12 2016

a(n) = number of walks in the integer lattice Z^8 starting and ending at the origin, using only the steps of the form (s_1, ..., s_8) with s_1^2 + ... + s_8^2 = 2, i.e., each possible step has precisely two nonzero entries which can be +1 or -1.

			There is one walk with no steps.
No walk with a single steps returns to the origin.
The number of returning walks with two steps is exactly the number of allowed steps (called the coordination number of the lattice): a(2) = 4*binomial(8,2).

Christoph Koutschan, Table of n, a(n) for n = 0..493
S. Hassani, C. Koutschan, J-M. Maillard, N. Zenine, Lattice Green Functions: the d-dimensional face-centred cubic lattice, d = 8, 9, 10, 11, 12, arXiv:1601.05657 [math-ph], 2016.
S. Hassani, C. Koutschan, J-M. Maillard, N. Zenine, Lattice Green functions: the d-dimensional face-centred cubic lattice, d = 8, 9, 10, 11, 12, Journal of Physics A: Mathematical and Theoretical 49(16) (2016), 164003.
C. Koutschan, Computations for higher-dimensional fcc lattices.
C. Koutschan, Differential operator annihilating the generating function.
C. Koutschan, Recurrence equation.

Cf. A002899 (d = 3, i.e., excursions on the 3-dimensional f.c.c. lattice), A271432 (d = 4), A271650 (d = 5), A271651 (d = 6), A271670 (d = 7), this sequence (d = 8), A271672 (d = 9), A271673 (d = 10), A271674 (d = 11).

nmax := 50: tt := [seq([seq(add(binomial(2*p,p)*binomial(2*j,2*p-n)*binomial(2*n+2*j-2*p,n+j-p), p = floor((n+1)/2)..floor((n+2*j)/2)), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: for d1 from 3 to 8 do tt := [seq([seq(add(binomial(n,p)*add(binomial(2*j,2*q-p)*binomial(2*j+2*p-2*q,j+p-q)*tt[n-p+1,q+1], q = floor((p+1)/2)..floor((p+2*j)/2)), p = 0..n), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: od: [seq(tt[n+1,1], n = 0..nmax)];

nmax = 50; T = Table[Sum[Binomial[2 p, p]*Binomial[2 j, 2 p - n]*Binomial[2 n + 2 j - 2 p, n + j - p], {p, Floor[(n + 1)/2], Floor[(n + 2 j)/2]}], {n, 0, nmax}, {j, 0, Floor[(nmax - n)/2]}]; Do[T = Table[Sum[Binomial[n, p]*Sum[Binomial[2 j, 2 q - p]*Binomial[2 j + 2 p - 2 q, j + p - q]*T[[n - p + 1, q + 1]], {q, Floor[(p + 1)/2], Floor[(p + 2 j)/2]}], {p, 0, n}], {n, 0, nmax}, {j, 0, If[d1 < 8, Floor[(nmax - n)/2], 0]}], {d1, 3, 8}]; First /@ T

a(n) conjecturally satisfies a linear recurrence equation of order 20 with polynomial coefficients of degree 109 (see link above).

The probability generating function P(z) = Sum_{n>=0} a(n)*(z/112)^n is given by the 8-fold integral (1/Pi)^8 Int_{0..Pi} ... Int_{0..Pi} 1/(1-z*lambda_8) dk_1 ... dk_8, where the structure function is defined as lambda_8 = (1/binomial(8,2)) Sum_{i=1..8} Sum_{j=(i+1)..8} cos(k_i)*cos(k_j). The function P(z) conjecturally satisfies a linear ODE of order 14 with polynomial coefficients of degree 126 (see link above).

A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 13, 26, 4, 1, 1, 75, 818, 252, 8, 1, 1, 541, 47834, 64324, 2568, 16, 1, 1, 4683, 4488722, 42725052, 5592968, 26928, 32, 1, 1, 47293, 617364026, 58555826884, 44418808968, 515092048, 287648, 64, 1

Offset: 0

Alois P. Heinz, Jul 10 2018

A(n,k) is the number of nonnegative integer matrices with k columns and any number of nonzero rows with column sums n. - Andrew Howroyd, Jan 23 2020

			Square array A(n,k) begins:
  1,  1,     1,         1,              1,                    1, ...
  1,  1,     3,        13,             75,                  541, ...
  1,  2,    26,       818,          47834,              4488722, ...
  1,  4,   252,     64324,       42725052,          58555826884, ...
  1,  8,  2568,   5592968,    44418808968,      936239675880968, ...
  1, 16, 26928, 515092048, 50363651248560, 16811849850663255376, ...

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

Columns k=0..3 give: A000012, A011782, A052141, A316673.
Rows n=0..2 give: A000012, A000670, A059516.
Main diagonal gives A316677.
Cf. A011782, A219727, A262809, A331315, A331485, A331636.

A:= (n, k)-> `if`(k=0, 1, ceil(2^(n-1))*add(add((-1)^i*
     binomial(j, i)*binomial(j-i, n)^k, i=0..j), j=0..k*n)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[n_, k_] := Sum[If[k == 0, 1, Binomial[j+n-1, n]^k] Sum[(-1)^(i-j)* Binomial[i, j], {i, j, n k}], {j, 0, n k}];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Nov 04 2021 *)

T(n,k)={my(m=n*k); sum(j=0, m, binomial(j+n-1,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

A(n,k) = A262809(n,k) * A011782(n) for k>0, A(n,0) = 1.

A(n,k) = Sum_{j=0..n*k} binomial(j+n-1,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020

A323131 Number of uncrossed rooted knight's paths of length n on an infinite board.

Original entry on oeis.org

1, 7, 47, 303, 1921, 11963, 74130, 454484, 2779152, 16882278, 102384151, 618136584, 3727827148, 22408576099, 134595908277, 806452390868

Offset: 1

Hugo Pfoertner, Jan 05 2019

The direction of the first move is kept fixed.

The average number of steps of a random walk using such knight moves with forbidden crossing is 45 (compare to A322831).

			a(1) = 1: The fixed initial move.
a(2) = 7: Relative to the direction given by the initial move, there are 7 possible direction changes. The backward direction is illegal for the self-avoiding uncrossed path. Only for the right angle turn its mirror image would coincide with the turn in the opposite direction. Therefore this move would be eliminated in the unrooted walks, making a(2) > A323132(2) = 6.
a(3) = 47: 2 of all 7*7 = 49 continuation moves already lead to a crossing of the first path segment.
See illustrations at Pfoertner link.

Hugo Pfoertner, Illustrations of rooted uncrossed knight's paths of length <= 3, (2019).

Cf. A003192, A272773, A323132, A323133, A323134, A323559.

Erroneous (as pointed out by Bert Dobbelaere) a(8) and a(10) corrected by Hugo Pfoertner, Jan 18 2019

a(12)-a(16) from Bert Dobbelaere, Jan 18 2019

A323808 Squares visited by a knight on a spirally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Original entry on oeis.org

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 45, 20, 23, 44, 41, 18, 35, 38, 19, 16, 33, 30, 53, 26, 47, 22, 43, 70, 21, 40, 17, 34, 13, 28, 25, 46, 75, 42, 69, 104, 37, 62, 95, 58, 55, 86, 51, 48, 77, 114, 73, 108, 151, 68, 103, 64, 67, 36, 39, 66, 63

Offset: 1

Daniël Karssen, Jan 28 2019

This is an infinite extension of A316667 with which it agrees for the first 2016 terms. - N. J. A. Sloane, Jan 28 2019

			The board is numbered with the square spiral:
  17--16--15--14--13   :
   |               |   :
  18   5---4---3  12  29
   |   |       |   |   |
  19   6   1---2  11  28
   |   |           |   |
  20   7---8---9--10  27
   |                   |
  21--22--23--24--25--26
See A323809 for examples where "backtracking" happens. - _M. F. Hasler_, Nov 06 2019

Daniël Karssen, Table of n, a(n) for n = 1..100000
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810, and A323811.

Cf. A326924 & A326922 (using L2-norm), A328908 & A328928 (L1-norm), A328909 & A328929 (sup norm); A326916 & A326918 (digits on spiral), A326413 and A328698 (variants with other tie breaker).

A323808(n)=A323809(n-1)+1 \\ M. F. Hasler, Nov 06 2019

a(n) = A323809(n-1) + 1. - M. F. Hasler, Nov 06 2019

A323809 Squares visited by a knight on a spirally numbered board, moving always to the lowest available unvisited square, or one step back if no unvisited square is available.

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, 42, 69, 20, 39, 16, 33, 12, 27, 24, 45, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 50, 47, 76, 113, 72, 107, 150, 67, 102, 63, 66, 35, 38, 65, 62

Offset: 0

Daniël Karssen, Jan 28 2019

This is an infinite extension of A316328, with which it coincides for the first 2016 terms. - N. J. A. Sloane, Jan 29 2019
From M. F. Hasler, Nov 04 2019: (Start)
At move 99999, the least yet unvisited square has number 66048, which is near the border of the visited region. This suggests that the knight will eventually visit every square. Can this be proved or disproved through a counterexample?
More formally, let us call "isolated" a set of unvisited squares which is connected through knight moves, but which cannot be extended to a larger such set by adding a further square. Can there exist at some moment a finite isolated set which the knight cannot reach? (Without the last condition, the square a(2016) would clearly satisfy the condition just before the knight reaches it.)
Such subsets have a good chance of preserving this property forever. It should be possible to prove that an isolated subset sufficiently far (2 knight moves?) from any other unvisited square (or from the infinite connected subset of unvisited squares) remains so forever. (This condition of distance could replace the time-dependent condition "reachable by the knight".)
If such (forever) isolated sets do exist, with what frequency will they occur? Could they have a nonzero asymptotic density? Will this (if so, how) depend on the way the knight measures "lowest available" (cf. variants where the taxicab or Euclidean or sup norm distance from the origin is used)? (End)

			The board is numbered following a square spiral:
  16--15--14--13--12   :
   |               |   :
  17   4---3---2  11  28
   |   |       |   |   |
  18   5   0---1  10  27
   |   |           |   |
  19   6---7---8---9  26
   |                   |
  20--21--22--23--24--25
.
From _M. F. Hasler_, Nov 06 2019: (Start)
At move 2015, the knight lands on a(2015) = 2083, from where no unvisited squares can be reached. So the knight moves back to a(2016) = a(2014) = 2466, from where it goes on to the unvisited square a(2017) = 2667.
Similarly, at moves 2985, 3120, 3378, 7493, 8785, 9738, 10985, 11861, 11936, 12160, 18499, 18730, 19947 and 22251, the knight get "trapped" and has to move to the previous square on the next move.
On move 23044, the same happens on square 25808, and the knight must move back to square a(23045) = a(23043) = 27111. However, there is still no unvisited square in reach, so the knight has to make another step back to a(23046) = a(23042) = 28446, before it can move on to a(23047) = 29123. (End)

Daniël Karssen, Table of n, a(n) for n = 0..99999
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810 and A323811.

Cf. A326924 & A326922 (using L2-norm), A328908 & A328928 (L1-norm), A328909 & A328929 (sup norm); A326916 & A326918 (digits on spiral), A326413 and A328698 (variants with other tie breaker).

Nmax=1e5 /* number of terms 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]), U=0, Umin=0, t(x, p=pos(x[1],x[2]))=if(pt(x+K), K))[1], back=0); my(A=List(0)); for(n=1, Nmax, back||U+=1<<(A[n]-Umin); while(bittest(U,0), U>>=1; Umin++); listput(A, nxt(A[n])); if(A[n+1] != oo, back=0, A[n+1]=A[n+1-back+=2])); print("Index of the last term: ", #A-1); A323809(n)=A[n+1];}

a(n) = A323808(n+1) - 1. - M. F. Hasler, Nov 06 2019

Edited by M. F. Hasler, Nov 02 2019

cp's OEIS Frontend

A150500 Number of walks within N^3 (the first octant of Z^3) starting at (0,0,0) and consisting of n steps taken from {(-1, -1, -1), (-1, -1, 1), (0, 1, 0), (1, 1, -1), (1, 1, 1)}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A271432 Number of n-step excursions on the 4-dimensional f.c.c. lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A271650 Number of n-step excursions on the 5-dimensional f.c.c. lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A271651 Number of n-step excursions on the 6-dimensional f.c.c. lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A271670 Number of n-step excursions on the 7-dimensional f.c.c. lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A271671 Number of n-step excursions on the 8-dimensional f.c.c. lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple