keyword:walk - cp's OEIS frontend

A232545 Number of Euler tours of the complete digraph on n vertices.

1, 3, 256, 972000, 247669456896, 6022251970560000000, 18932148110851728998400000000, 10036271333655026636037644353536000000000, 1135547314049215265041779022180122624000000000000000000, 33878761698754076709292639330840075944838638855101181276979200000000000

Offset: 2

Tomas Boothby, Nov 25 2013

			For n = 2, there is one Euler tour, (1,2,1), since (1,2,1) is cyclically equivalent to (2,1,2).
For n = 3, there are three Euler tours: (1,2,1,3,2,3,1), (1,2,3,1,3,2,1), (1,2,3,2,1,3,1).

Andrew Howroyd, Table of n, a(n) for n = 2..30
Wikipedia, BEST Theorem, a formula for counting Euler tours in digraphs.

a(n) = n^(n-2)*(n-2)!^n \\ Andrew Howroyd, Dec 28 2021

a(n) = n^(n-2)*(n-2)!^n, by the "BEST Theorem". - James Thompson, Jul 18 2017, Günter Rote, Dec 09 2021

The above formula can be written as a(n) = A000272(n)*A000142(n-2)^n. - Omar E. Pol, Jul 18 2017

a(5) corrected by Tomas Boothby, Dec 03 2013

Terms a(8) and beyond from Andrew Howroyd, Dec 28 2021

A284869 Number of n-step 2-dimensional closed self-avoiding paths on triangular lattice, reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Original entry on oeis.org

0, 0, 1, 1, 1, 4, 5, 16, 37, 120, 344, 1175, 3807, 13224, 45645, 161705, 575325, 2074088, 7521818, 27502445, 101134999, 374128188

Offset: 1

Luca Petrone, Apr 04 2017

Differs from A057729 beginning at n = 11, since that sequence includes triangular polyominoes with holes.

a(n) is the number of simply connected polyiamonds with perimeter n. - Walter Trump, Nov 29 2023

Rade Doroslovački, Ivan Stojmenović and Ratko Tošić, Generating and counting triangular systems, BIT Numerical Mathematics, 27 (1987), 18-24. See Table 1.
Hugo Pfoertner, Illustration of ratio A036418(n)/a(n) using Plot2.
Hugo Pfoertner, Illustration of polygons of perimeter <= 11.
Walter Trump, Self-avoiding closed walks on a triangular lattice

Approaches (1/12)*A036418 for increasing n.

Cf. A057729, A258206, A266549, A316196.

a(15) from Hugo Pfoertner, Jun 27 2018

a(16)-a(22) from Walter Trump, Nov 29 2023

A306178 Number of unrooted self-avoiding walks with n steps that can make turns from the set 0, +-Pi/4, +-Pi/2, +-3*Pi/4.

Original entry on oeis.org

1, 4, 15, 86, 492, 2992, 18172, 110643, 672267, 4069122, 24578785, 147972210, 889332713, 5331980703, 31924424199

Offset: 1

Hugo Pfoertner, Jun 23 2018

The turning angles are those of the regular octagon, with one vertex corresponding to the forbidden U-turn. The path may neither intersect nor touch itself anywhere.

Contest Organizers, Al Zimmermann's Programming Contests - Snakes on a Plane, Fall 2006.
Hugo Pfoertner, Illustration of walks of lengths <= 3.

Cf. A266925, A037245, A306175, A151541, A306177, A306179, A306180, A306181, A306182.

a(7)-a(15) from Bert Dobbelaere, May 15 2025

A334720 Number of 2-dimensional closed-loop self-avoiding paths on a square lattice where each path consists of steps with incrementing length from 1 to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 8, 24, 0, 0, 40, 112, 0, 0, 1376, 2008, 0, 0, 21720, 60848, 0, 0, 635544, 1517368, 0, 0, 20008456, 46010640, 0, 0, 640819936, 1571759136, 0, 0, 22704325648, 55436103264

Offset: 1

Scott R. Shannon, May 08 2020

This sequence gives the number of closed-loop self avoiding walks on a 2D square lattice where the walk starts with a step length of 1 which then increments by 1 after each step up until the step length is n. No closed-loop path is possible until n = 7.
Like A010566 all possible paths are counted, including those that are equivalent via rotation and reflection.
For n = 8, 15, 20, 24, 27, 32, 35, 39, 44, ... =  A380867, the path can be a rectangle. The first two cases are illustrated through the "Images" link from Scott R. Shannon. These numbers correspond to triangular numbers T(n) for which there are n1 > n2 > n3 > n4 >= 0 such that T(n) = 2(A+B) for A = T(n1) - T(n2) = T(n3) - T(n4) and B = T(n2) - T(n3). See A380867 for more. - M. F. Hasler, Mar 14 2025

			a(1) to a(6) = 0 as no closed-loop is possible.
a(7) = 8 as there is one path which forms a closed loop which can be walked in 8 different ways on a 2D square lattice. The path is:
.
             5
   *---.---.---.---.---*
   |                   |
   .                   .
   |                   |
   .                   .  4
   |                   |
6  .                   .
   |                   |     3
   .                   *---.---.---*
   |                               |
   .                               . 2
   |                               |
   *---.---.---.---.---.---.---X---*
                 7               1
.
See the attached link for text images of the closed loops for other n values.

A. J. Guttmann and I. G. Enting, The size and number of rings on the square lattice, J. Phys. A 21 (1988), L165-L172.
Scott R. Shannon, Images of the closed-loops for n=7,8,11,12,15.

Cf. A010566, A334877, A002931, A334756, A380867.

A335661 The squares visited on a square (Ulam) spiral, with a(1) = 1 and a(2) = 2, when stepping to the closest unvisited square containing a number that shares a common divisor > 1 with the number in the current square. If two or more such squares are the same distance from the current square then the one with the smallest number is chosen.

Original entry on oeis.org

1, 2, 4, 6, 8, 22, 20, 40, 18, 39, 69, 105, 150, 104, 66, 38, 36, 63, 98, 62, 34, 14, 12, 3, 15, 5, 35, 60, 33, 30, 55, 88, 54, 87, 129, 177, 234, 299, 455, 375, 456, 374, 300, 235, 130, 90, 57, 93, 135, 186, 134, 92, 58, 32, 56, 91, 133, 182, 132, 180, 237

Offset: 1

Scott R. Shannon, Jun 17 2020

Any even number on the square spiral has 4 diagonally adjacent squares which contain an even number and thus, unless all four such squares have been previously visited, a step to one of those adjacent squares, the one containing the smallest number, will always be possible. Any visited square containing a prime number will need to step to, and be stepped to from, a square containing a multiple of that prime number.
In the first 10 million terms the longest required step is from a(97528) = 5981, a prime number which has coordinates (39,13) relative to the starting 1-square, to a(97529) = 167468 (27*5981), with coordinates (205,-18), a step of length sqrt(28517), approximately 168.9 units. This is an extremely large step length relative to the total number of steps taken up to that point - see the attached link image. It is not surpassed by any subsequent step up to 10 million steps. If the maximum step distance between adjacent terms has a finite value or is unbounded as n increases is unknown. The largest difference between terms is for a(9404208) = 8964653 to a(9404209) = 10485343, a difference of 1520690.
In the first 10 million terms the smallest unvisited square is 37, which has coordinates (-3,3) relative to the starting 1-square. It is unknown if this square, and similar unvisited squares near the origin, is eventually visited for very large values of n or is never visited. The longest run of diagonal steps in the same direction to adjacent smaller even numbers is 52, from a(3979714) = 5051162 to a(3979766) = 4594498.

			a(3) = 4 as a(2) = 2 is surrounded by eight adjacent squares with numbers 3,4,1,8,9,10,11,12. The unvisited squares 1 unit away, 3,9,11 have no common factor with 2. Of the other squares sqrt(2) units away, 4,8,10,12, all share the common factor 2 with a(2), and the smallest of those is 4.
a(10) = 39 as a(9) = 18 is surrounded by adjacent squares 5,6,19,40,39,38,17,16. The square containing 39 is 1 unit directly left of 18 and shares the common factor 3. The other squares one unit away, 5,17,19, have no common factor with 18.

Scott R. Shannon, Image of the steps from 1 to 20001. The green dot shows the starting square 1, the red dot the final square 26453, and the yellow dot the smallest unvisited square 11. The orange line shows the largest step distance, sqrt(976), from a(8538) = 233 to a(8539) = 3029. The blue line shows the longest run of adjacent diagonal steps, each of length sqrt(2), to a lower even number in the same direction, from a(3747) = 7880 and lasts for 19 steps. The pink line shows the largest change in value for a single step, from a(19032) = 15023 to a(19033) = 25159, a difference of 10136.
Scott R. Shannon, Image of the steps from 1 to 20001 with color. The color of each step is graduated across the spectrum from red to violet to show the relative visit order of the squares. Note how green colored steps, those around n = 10000, approach the origin, showing that all numbers near the origin may eventually be visited for very large values of n.
Scott R. Shannon, Image of the steps from 1 to 100000. The orange line shows the step length of sqrt(28517) units at a(97528), from 5981 to 167468. The blue line shows the new longest run of adjacent diagonal steps to lower even numbers, a series of 24 steps. The yellow dot shows the new lowest unvisited square 13, square 11 being visited at a(26321).
Scott R. Shannon, Image of the steps from 1 to 5000000 with color. Note how some violet colored steps, those around n = 4200000, approach the origin. The yellow dot shows the new lowest unvisited square 37, square 13 being visited at a(105263). Also note the visited area forms a roughly square pattern, following the largest outer numbers of the spiral. This becomes more pronounced as n increases.

Cf. A000005, A032741, A063826, A214665, A330979, A331027, A332767, A335710.

A005564 Number of n-step walks on square lattice in the first quadrant which finish at distance n-3 from the x-axis.

Original entry on oeis.org

6, 20, 45, 84, 140, 216, 315, 440, 594, 780, 1001, 1260, 1560, 1904, 2295, 2736, 3230, 3780, 4389, 5060, 5796, 6600, 7475, 8424, 9450, 10556, 11745, 13020, 14384, 15840, 17391, 19040, 20790, 22644, 24605, 26676, 28860, 31160, 33579, 36120, 38786, 41580, 44505

Offset: 3

N. J. A. Sloane

The steps are N, S, E or W.
For n>=4, a(n-1)/2 is the coefficient c(n-2) of the m^(n-2) term of P(m,n) = (c(m-1)* m^(n-1) + c(m-2)* m^(n-2) +...+ c(0)* m^0)/((a!)* (a-1)!), the polynomial for the number of partitions of m with exactly n parts. - Gregory L. Simay, Jun 28 2016
2a(n) is the denominator of formula 207 in Jolleys' "Summation of Series." 2/(1*3*4)+3/(2*4*5)+...n terms. Sum_{k = 1..n} (k+1)/(k*(k+2)*(k+3)). This summation has a closed form of 17/36-(6*n^2+21*n+17)/(6*(n+1)*(n+2)*(n+3)). - Gary Detlefs, Mar 15 2018
a(n) is the number of degrees of freedom in a tetrahedral cell for a Nédélec first kind finite element space of order n-2. - Matthew Scroggs, Jan 02 2021

			The n=4 diagram in Fig. 4 of Guy's paper is:
1
0 4
9 0 6
0 16 0 4
10 0 9 0 1
Adding 16+4 we get a(4)=20.
The a(3) = 6 walks are EEN, ENE, ENW, NEW, NSN, NNS. - _Michael Somos_, Jun 09 2014
G.f. = 6*x^3 + 20*x^4 + 45*x^5 + 84*x^6 + 140*x^7 + 216*x^8 + 315*x^9 + ...
From _Gregory L. Simay_ Jun 28 2016: (Start)
P(m,4) = (m^3 + 3*m^2 + ...)/(3!*4!) with 3 = a(3)/2 = 6/2.
P(m,5) = (m^4 + 10*m^3 + ...)/(4!*5!) with 10 = a(4)/2 = 20/2.
P(m,6) = (m^5 + (45/2)*m^4 +...)/(5!*6!) with 45/2 = a(5)/2.
P(m,7) = (m^6 + 42*m^5 +...)/(6!*7!) with 42 = a(6)/2 = 84/2. (End)

L. B. W. Jolley, "Summation of Series", Dover Publications, 1961, p. 38.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
DefElement, Nédélec first kind
R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6. See figure 4, sum of terms in (n-2)-nd row.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A000217.
First differences of A001701.
Fourth column of A093768.

a:=List([0..45],n->(n+1)*Binomial(n+4,2)); # Muniru A Asiru, Feb 15 2018

I:=[6, 20, 45, 84]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..45]]; // Vincenzo Librandi, Jun 18 2012

A005564 := proc(n)
        (n-2)*(n)*(n+1)/2 ;
end proc: seq(A005564(n),n=0..10) ; # R. J. Mathar, Dec 09 2011

Table[(n-2)*Binomial[n+1, 2], {n, 3, 40}]
LinearRecurrence[{4,-6,4,-1},{6,20,45,84},50] (* Vincenzo Librandi, Jun 18 2012 *)

a(n)=(n-2)*(n)*(n+1)/2 \\ Charles R Greathouse IV, Dec 12 2011

G.f.: x^3 * ( 6 - 4*x + x^2 ) / ( 1 - x )^4. [Simon Plouffe in his 1992 dissertation]
a(n) = (n-2)*n*(n+1)/2 = (n-2)*A000217(n).
a(n) = Sum_{j = 0..n} ((n+j-1)^2-(n-j+1)^2)/4. - Zerinvary Lajos, Sep 13 2006
a(n) = Sum_{k = 2..n-1} k*n. - Zerinvary Lajos, Jan 29 2008
a(n) = 4*binomial(n+1,2)*binomial(n+1,4)/binomial(n+1,3) = (n-2)*binomial(n+1,2). - Gary Detlefs, Dec 08 2011
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 18 2012
E.g.f.: x - x*(2 - 2*x - x^2)*exp(x)/2. - Ilya Gutkovskiy, Jun 29 2016
a(n) = 6*Sum_{i = 1..n-1} A000217(i) - n*A000217(n). - Bruno Berselli, Jul 03 2018
Sum_{n>=3} 1/a(n) = 5/18. - Amiram Eldar, Oct 07 2020

Entry revised by N. J. A. Sloane, Jul 06 2012

A007082 Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).

Original entry on oeis.org

2, 264, 1015440, 90449251200, 169107043478365440, 6267416821165079203599360, 4435711276305905572695127676467200, 58393052751308545653929138771580386824519680, 14021772793551297695593332913856884153315254190271692800, 60498832138791357698014788383803842810832836262245623803123983974400

Offset: 1

N. J. A. Sloane, Mira Bernstein

			From _Günter Rote_, Dec 09 2021: (Start)
For n=2, in the graph K5, if we fix the Euler tour to start with the edge 12, we get 132 Euler tours. Here are the first and the last few in lexicographic order.
  12314253451
  12314254351
  12314352451
  12314354251
  12314524351
  ...
  12543153241
  12543241351
  12543241531
  12543513241
  12543514231.
To get all 264*1!^5 = 264 Euler tours, the number must be multiplied by 2 to include the reversed tours. (End)

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.3, p. 745, Problem 107.
B. D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Florian Ragwitz, Table of n, a(n) for n = 1..16
Brendan D. McKay and Robert W. Robinson, Asymptotic enumeration of Eulerian circuits in the complete graph, Combinatorics, Probability and Computing, 7 (1998), 437-449. (gives terms up to n=10, i.e., up through K_{21})

Cf. A135388, A232545, A350028, A356366, A357855, A357856, A357857, A357885, A357886, A357887.

# for n <= 4
def A(n,w="12"):
    if len(w) > (2*n+1)*n: return 2
    return sum(A(n, w+t) for t in "123456789"[:2*n+1]
        if t!=w[-1] and t+w[-1] not in w and w[-1]+t not in w)

a(n) = A135388(n) / (n-1)!^(2n+1) = A350028(2n+1) / (n-1)!^(2n+1) = A357887(2n+1,n(2n+1)) / (n-1)!^(2n+1). - Max Alekseyev, Oct 19 2022

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003

A054881 Number of walks of length n along the edges of an octahedron starting and ending at a vertex and also ( with a(0)=0 ) between two opposite vertices.

Original entry on oeis.org

1, 0, 4, 8, 48, 160, 704, 2688, 11008, 43520, 175104, 698368, 2797568, 11182080, 44744704, 178946048, 715849728, 2863267840, 11453333504, 45812809728, 183252287488, 733007052800, 2932032405504, 11728121233408

Offset: 0

Paolo Dominici (pl.dm(AT)libero.it), May 23 2000

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 7.
Index entries for linear recurrences with constant coefficients, signature (2,8).

Cf. A001045, A003683, A054882, A054883, A054884, A054885, A246036.

[(4^n+(-1)^n*2^(n+1)+3*0^n)/6: n in [0..30]]; // Vincenzo Librandi, Apr 23 2015

CoefficientList[Series[(1-2*x-4*x^2)/((1+2x)*(1-4x)), {x,0,40}], x] (* L. Edson Jeffery, Apr 22 2015 *)
LinearRecurrence[{2,8}, {1,0,4}, 41] (* G. C. Greubel, Feb 06 2023 *)

[(4^n + (-1)^n*2^(n+1) + 3*0^n)/6 for n in range(31)] # G. C. Greubel, Feb 06 2023

a(n) = 4*A003683(n-1) + 0^n/2, n >= 0.
a(n) = (4^n + (-1)^n*2^(n+1) + 3*0^n)/6.
G.f.: (1/6)*(3 + 2/(1+2*x) + 1/(1-4*x)).
From L. Edson Jeffery, Apr 22 2015: (Start)
G.f.: (1-2*x-4*x^2)/((1+2*x)*(1-4*x)).
a(n) = 8*A246036(n-3) + 0^n/2, n >= 0. (End)
a(n) = 2^n*A001045(n-1) + (1/2)*[n=0] = 2^n*(2^(n-1) + (-1)^n)/3 + (1/2)*[n=0], n >= 0. - Ralf Steiner, Aug 27 2020, edited by M. F. Hasler, Sep 11 2020
E.g.f.: (1/6)*(exp(4*x) + 2*exp(-2*x) + 3). - G. C. Greubel, Feb 06 2023

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Original entry on oeis.org

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Don Knuth, Jul 26 2008

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Main diagonal of A329118.
Cf. A140519, A158651, A234622, A007764, A038496.
Cf. A220638 (Hosoya index).

a(9)-a(11) from Andrew Howroyd, Apr 07 2016

A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph.

Original entry on oeis.org

1, 3, 16, 2830, 2462064, 22853860116, 1622043117414624, 961742089476282321684, 4601667243759511495116347104, 179517749570891592016479828267003018, 56735527086758553613684823040730404215973136, 145328824470156271670635015466987199469360063082789418

Offset: 1

Don Knuth, Jul 26 2008

Or, number of Hamiltonian cycles in the graph P_n X P_n (strong product of two paths of length n-1).
If the direction of the tour is to be taken into account, the numbers for n > 1 must be multiplied by 2 (see A140521).
Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

D. E. Knuth, The Art of Computer Programming, Section 7.1.4, in preparation.

N. J. A. Sloane, Table of n, a(n) for n = 1..16 [From Pettersson 2014]
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A001230, A140521.

New name from Eric W. Weisstein, May 06 2019

cp's OEIS Frontend

A232545 Number of Euler tours of the complete digraph on n vertices.

Views

Author

Keywords

Examples

Links

Programs

PARI

Formula

Extensions

A284869 Number of n-step 2-dimensional closed self-avoiding paths on triangular lattice, reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A306178 Number of unrooted self-avoiding walks with n steps that can make turns from the set 0, +-Pi/4, +-Pi/2, +-3*Pi/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A334720 Number of 2-dimensional closed-loop self-avoiding paths on a square lattice where each path consists of steps with incrementing length from 1 to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A005564 Number of n-step walks on square lattice in the first quadrant which finish at distance n-3 from the x-axis.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

Extensions

A007082 Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A054881 Number of walks of length n along the edges of an octahedron starting and ending at a vertex and also ( with a(0)=0 ) between two opposite vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica