keyword:walk - cp's OEIS frontend

A006356 a(n) = 2*a(n-1) + a(n-2) - a(n-3) for n >= 3, starting with a(0) = 1, a(1) = 3, and a(2) = 6.

1, 3, 6, 14, 31, 70, 157, 353, 793, 1782, 4004, 8997, 20216, 45425, 102069, 229347, 515338, 1157954, 2601899, 5846414, 13136773, 29518061, 66326481, 149034250, 334876920, 752461609, 1690765888, 3799116465, 8536537209, 19181424995

Offset: 0

N. J. A. Sloane

Number of distributive lattices; also number of paths with n turns when light is reflected from 3 glass plates.
Let u(k), v(k), w(k) be defined by u(1) = 1, v(1) = 0, w(1) = 0 and u(k+1) = u(k) + v(k) + w(k), v(k+1) = u(k) + v(k), w(k+1) = u(k); then {u(n)} = 1, 1, 3, 6, 14, 31, ... (this sequence with an extra initial 1), {v(n)} = 0, 1, 2, 5, 11, 25, ... (A006054 with its initial 0 deleted) and {w(n)} = {u(n)} prefixed by an extra 0 = A077998 with an extra initial 0. - Benoit Cloitre, Apr 05 2002
Also u(k)^2 + v(k)^2 + w(k)^2 = u(2*k). - Gary W. Adamson, Dec 23 2003
The n-th term of the series is the number of paths for a ray of light that enters two layers of glass and then is reflected exactly n times before leaving the layers of glass.
One such path (with 2 plates of glass and 3 reflections) might be:
...\........./..................
--------------------------------
....\/\..../....................
--------------------------------
........\/......................
--------------------------------
For a k-glass sequence, say a(n,k), a(n,k) is always asymptotic to z(k)*w(k)^n where w(k) = (1/2)/cos(k*Pi/(2*k+1)) and it is conjectured that z(k) is the root 1 < x < 2 of a polynomial of degree Phi(2k+1)/2.
Number of ternary sequences of length n-1 such that every pair of consecutive digits has a sum less than 3. That is to say, the pairs (1,2), (2,1) and (2,2) do not appear. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 07 2004
Number of weakly up-down sequences of length n using the digits {1,2,3}. When n=2 the sequences are 11, 12, 13, 22, 23, 33.
Form the graph with matrix A = [1, 1, 1; 1, 0, 0; 1, 0, 1]. Then A006356 counts walks of length n that start at the degree 4 vertex. - Paul Barry, Oct 02 2004
In general, the g.f. for p glass plates is: A(x) = F_{p-1}(-x)/F_p(x) where F_p(x) = Sum_{k=0..p} (-1)^[(k+1)/2]*C([(p+k)/2],k)*x^k. - Paul D. Hanna, Feb 06 2006
Equals the INVERT transform of (1, 2, 1, 1, 1, ...) equivalent to a(n) = a(n-1) + 2*a(n-2) + a(n-3) + a(n-4) + ... + 1. a(6) = 70 = (31 + 2*14 + 6 + 3 + 1 + 1). - Gary W. Adamson, Apr 27 2009
a(n) = the number of terms in the n-th iterate of sequence A179542 generated from the rules a(0) = 1, then (1->1,2,3), (2->1,2), (3->1).
Example: 3rd iterate = (1,2,3,1,2,1,1,2,3,1,2,1,2,3) = 14 terms composed of a frequency of (6, 5, 3): (1's, 2's, and 3's), where a(3) = 14, and the [6, 5, 3] = top row and left column of the 3rd power of M, the matrix generator [1,1,1; 1,1,0; 1,0,0] or a(2) = 6, A006054(4) = 5, and a(1) = 3.
Given the heptagon diagonal lengths with edge = 1: (a = 1, b = 1.80193773..., c = 2.24697...) = (1, 2*cos(Pi/7), (1 + 2*cos(2*Pi/7))), and using the diagonal product formulas in [Steinbach], we obtain: c^n = c*a(n-2) + b*A006054(n) + a(n-3) corresponding to the top row of M^(n-1), in the case M^3 = [6, 5, 3]. Example: c^4 = 25.491566... = 6*c + 5*b + 3 = 13.481... + 9.00968... + 3. - Gary W. Adamson, Jul 18 2010
Equals row sums of triangle A180262. - Gary W. Adamson, Aug 21 2010
The number of the one-sided n-step prudent walks, avoiding 2 or more consecutive east steps. - Shanzhen Gao, Apr 27 2011
a(n) = [A_{7,2}^(n+2)](1,1), where A{7,2} is the 3 X 3 unit-primitive matrix (see [Jeffery]) A_{7,2} = [0,0,1; 0,1,1; 1,1,1]. The denominator of the generating function for this sequence is also the characteristic polynomial of A_{7,2}. - L. Edson Jeffery, Dec 06 2011 [See the comments for sequence A306334. - Petros Hadjicostas, Nov 17 2019]
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1] or of the 3 X 3 matrix [1, 1, 1; 1, 1, 0; 1, 0, 0]. - R. J. Mathar, Feb 03 2014
Successive sequences in this set (A006356, A006357, A006358, etc.) can be generated as follows: Begin with (1, 1, 1, 1, 1, 1, ...); and perform an operation with three steps to get the next sequence in the series. First, put alternate signs in the current series: With (1, 1, 1, ...) this equals (1, -1, 1, -1, ...); then take the inverse, getting (1, 1, 0, 0, 0, ...). Take the INVERT transform of the last step, getting (1, 2, 3, 5, 8, ...). Repeat the three steps using (1, 2, 3, 5, ...) --> (1, -2, 3, -5) --> (1, 2, 1, 1, 1, ...) --> (1, 3, 6, 14, 31, ...). Repeat the three steps using (1, 3, 6, 14, 31, ...), getting (1, 4, 10, 30, 85, ...) = A006357; and so on. - Gary W. Adamson, Aug 08 2019
Let W_n be the fence poset (a.k.a. zig-zag poset) of size n.  Let [2] be a chain of size 2.  Then a(n) is the number of antichains in the product poset W_n X [2]. See Berman- Koehler link. - Geoffrey Critzer, Jun 13 2023
a(n) is the number of double-dimer covers of the 2 X (n+1) square grid graph. See Musiker et al. link. - Nicholas Ovenhouse, Jan 07 2024
In general, the number of weakly up-down words of length n over an alphabet of size k is given by 4/(2*k+1)*|Sum_{j = 1..k} sin^2(2*j*Pi/(2*k+1))/(2*cos^2(2*j*Pi/(2*k+1)))^(n+1)| and the corresponding g. f. is given by V_(k-1)(-x/2)/W_k(x/2) if k is even and -W_(k-1)(-x/2) / V_k(x/2) if k is odd, where V_m(x) and W_m(x) are the Chebyshev polynomials of the third and fourth kind, respectively (see Paul D. Hanna's comment above and the Fried link). - Sela Fried, Apr 01 2025

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd edition, p. 291 (very briefly without generalizations).
J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.
Jay Kappraff, Beyond Measure, A Guided Tour Through Nature, Myth and Number, World Scientific, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
J. Berman and P. Köhler, On Dedekind Numbers and Two Sequences of Knuth, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.
Sela Fried, A formula for the number of up-down words, arXiv:2503.02005 [math.CO], 2025.
Emma L. L. Gao, Sergey Kitaev, and Philip B. Zhang, Pattern-avoiding alternating words, arXiv:1505.04078 [math.CO], 2015.
Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Manfred Goebel, Rewriting Techniques and Degree Bounds for Higher Order Symmetric Polynomials, Applicable Algebra in Engineering, Communication and Computing (AAECC), Volume 9, Issue 6 (1999), 559-573.
V. E. Hoggatt Jr. and M. Bicknell-Johnson, Reflections across two and three glass plates, Fibonacci Quarterly, volume 17 (1979), 118-142.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 451
L. E. Jeffery, Unit-primitive matrices
B. Junge and V. E. Hoggatt, Jr., Polynomials arising from reflections across multiple plates, Fib. Quart., 11 (1973), 285-291.
Peter Köhler, The Central Decomposition of FD_01(n), Order (2021).
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
Leo Moser, Problem B-6: some reflections, Fib. Quart. Vol. 1, No. 4 (1963), 75-76.
Leo Moser and Max Wyman, Multiple reflections, Fib. Quart., 11 (1973).
Gregg Musiker, Ralf Schiffler, Nicholas Ovenhouse, and Sylvester Zhang, Higher Dimer Covers on Snake Graphs, arXiv:2306.14389 [math.CO], 2023.
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.
Lingjuan Shi and Kai Deng, The Numbers of Perfect and Maximal Matchings in Double Hexagonal Chains, Match Comm. Math. Comp. Chem. (2025) 659-685. See p. 8.
P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
R. Witula, D. Slota and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.
Index entries for linear recurrences with constant coefficients, signature (2,1,-1).

Cf. A000217, A000330, A050446, A050447, A006054, A077998, A052534, A052994, A052949.
See also A006357-A006359, A025030, A030112-A030116.
Cf. A038196 (3-wave sequence).
Cf. A179542. - Gary W. Adamson, Jul 18 2010
Cf. A180262. - Gary W. Adamson, Aug 21 2010
Cf. A033303, A190360, A306334.

a006056 n = a006056_list !! n
a006056_list = 1 : 3 : 6 : zipWith (+) (map (2 *) $ drop 2 a006056_list)
   (zipWith (-) (tail a006056_list) a006056_list)
-- Reinhard Zumkeller, Oct 14 2011

[ n eq 1 select 1 else n eq 2 select 3 else n eq 3 select 6 else 2*Self(n-1)+Self(n-2)- Self(n-3): n in [1..40] ] ; // Vincenzo Librandi, Aug 20 2011

A006356:=-(-1-z+z**2)/(1-2*z-z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation

LinearRecurrence[{2,1,-1},{1,3,6},30] (* or *) CoefficientList[ Series[ (1+x-x^2)/(1-2x-x^2+x^3),{x,0,30}],x] (* Harvey P. Dale, Jul 06 2011 *)
Table[If[n==0, a2=0; a1=1; a0=1, a3=a2; a2=a1; a1=a0; a0=2*a1+a2-a3], {n, 0, 29}] (* Jean-François Alcover, Apr 30 2013 *)

a(n):=sum(sum((sum(binomial(j,-3*k+2*j+i)*(-1)^(j-k)*binomial(k,j),j,0,k))*binomial(n+k-i-1,k-1),i,k,n),k,1,n); /* Vladimir Kruchinin, May 05 2011 */

{a(n)=local(p=3);polcoeff(sum(k=0,p-1,(-1)^((k+1)\2)*binomial((p+k-1)\2,k)* (-x)^k)/sum(k=0,p,(-1)^((k+1)\2)*binomial((p+k)\2,k)*x^k+x*O(x^n)),n)} \\ Paul D. Hanna, Feb 06 2006

Vec((1+x-x^2)/(1-2*x-x^2+x^3)+O(x^66)) \\ Joerg Arndt, Apr 30 2013

from math import comb
def A006356(n): return sum(comb(j,a)*comb(k,j)*comb(n+k-i,k-1)*(-1 if j-k&1 else 1) for k in range(1,n+2) for i in range(k,n+2) for j in range(k+1) if (a:=-3*k+2*j+i)>=0) # Chai Wah Wu, Feb 19 2024

a(n) is asymptotic to z(3)*w(3)^n where w(3) = (1/2)/cos(3*Pi/7) and z(3) is the root 1 < X < 2 of P(3, X) = 1 - 14*X - 49*X^2 + 49*X^3. w(3) = 2.2469796.... z(3) = 1.220410935...
G.f.: (1 + x - x^2)/(1 - 2*x - x^2 + x^3). - Paul D. Hanna, Feb 06 2006
a(n) = a(n-1) + a(n-2) + A006054(n+1). - Gary W. Adamson, Jun 05 2008
a(n) = A006054(n+2) + A006054(n+1) - A006054(n). - R. J. Mathar, Apr 07 2011
a(n-1) = Sum_{k = 1..n} Sum_{i = k..n} Sum_{j = 0..k} binomial(j, -3*k+2*j+i) * (-1)^(j-k) * binomial(k, j) * binomial(n+k-i-1, k-1). - Vladimir Kruchinin, May 05 2011
Sum_{k=0..n} a(k) = a(n+1) - a(n-1) - 1. - Greg Dresden and Mina BH Arsanious, Aug 23 2023

Recurrence, alternative description from Jacques Haubrich (jhaubrich(AT)freeler.nl)

Alternative definition added by Andrew Niedermaier, Nov 11 2008

A001412 Number of n-step self-avoiding walks on cubic lattice.

Original entry on oeis.org

1, 6, 30, 150, 726, 3534, 16926, 81390, 387966, 1853886, 8809878, 41934150, 198842742, 943974510, 4468911678, 21175146054, 100121875974, 473730252102, 2237723684094, 10576033219614, 49917327838734, 235710090502158, 1111781983442406, 5245988215191414, 24730180885580790, 116618841700433358, 549493796867100942, 2589874864863200574, 12198184788179866902, 57466913094951837030, 270569905525454674614

Offset: 0

N. J. A. Sloane

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-339.
B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 462.
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).

R. D. Schram, G. T. Barkema, and R. H. Bisseling, Table of n, a(n) for n = 0..36
N. Clisby, Enumerative combinatorics of lattice polymers, Notices AMS, 68:4 (2021), 504-515. (Excellent survey)
N. Clisby, R. Liang, and G. Slade, Self-avoiding walk enumeration via the lace expansion, J. Phys. A: Math. Theor. 40 (2007), 10973-11017, Table A5 for n<=30.
Steven R. Finch, Self-Avoiding-Walk Connective Constants
M. E. Fisher and M. F. Sykes, Excluded-volume problem and the Ising model of ferromagnetism, Phys. Rev. 114 (1959), 45-58.
A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.
B. J. Hiley and M. F. Sykes, Probability of initial ring closure in the restricted random-walk model of a macromolecule, J. Chem. Phys., 34 (1961), 1531-1537.
D. S. McKenzie and C. Domb, The second osmotic virial coefficient of athermal polymer solutions, Proceedings of the Physical Society, 92 (1967) 632-649.
A. M. Nemirovsky, Karl F. Freed, Takao Ishinabe, and Jack F. Douglas, Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.
D. Randall, Counting in Lattices: Combinatorial Problems from Statistical Mechanics, PhD Thesis (1994).
Raoul D. Schram, Gerard T. Barkema, and Rob H. Bisseling, Exact enumeration of self-avoiding walks, arXiv:1104.2184 [math-ph], 2011.
Nobu C. Shirai and Naoyuki Sakumichi, Negative Energetic Elasticity of Lattice Polymer Chain in Solvent, arXiv:2202.12483 [cond-mat.soft], 2022.
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.
M. F. Sykes, Self-avoiding walks on the simple cubic lattice, J. Chem. Phys., 39 (1963), 410-411.
M. F. Sykes, A. J. Guttmann, M. G. Watts, and P. D. Roberts, The asymptotic behavior of self-avoiding walks and returns on a lattice, J. Phys. A 5 (1972), 653-660.
M. F. Sykes, D. S. McKenzie, M. G. Watts, and J. L. Martin, The number of self-avoiding rings on a lattice, J. Phys. A 5 (1972), 661-666.

Cf. A002902, A078717, A001411, A001413.

mo = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; a[0] = 1;
a[tg_, p_: {{0, 0, 0}}] := Block[{e, mv = Complement[Last[p] + # & /@ mo, p]},
If[tg == 1, Return[Length@mv],Sum[a[tg - 1, Append[p, e]], {e, mv}]]];
a /@ Range[0, 8]
(* Robert FERREOL, Nov 30 2018, after the program of Giovanni Resta in A001411 *)

def add(L,x):
    M=[y for y in L];M.append(x)
    return(M)
plus=lambda L,M : [x+y for x,y in zip(L,M)]
mo=[[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]]
def a(n,P=[[0,0,0]]):
    if n==0: return(1)
    mv1 = [plus(P[-1],x) for x in mo]
    mv2=[x for x in mv1 if x not in P]
    if n==1: return(len(mv2))
    else: return(sum(a(n-1,add(P,x)) for x in mv2))
[a(n) for n in range(8)]
# Robert FERREOL, Nov 30 2018

A003763 Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.

Original entry on oeis.org

1, 6, 1072, 4638576, 467260456608, 1076226888605605706, 56126499620491437281263608, 65882516522625836326159786165530572, 1733926377888966183927790794055670829347983946, 1020460427390768793543026965678152831571073052662428097106

Offset: 1

Jeffrey Shallit, Feb 14 2002

Orientation of the path is not important; you can start going either clockwise or counterclockwise.
The number is zero for a 2n+1 X 2n+1 grid (but see A222200).
These are also called "closed rook tours".

			a(1) = 1 because there is only one such path visiting all nodes of a square.

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

N. J. A. Sloane, Table of n, a(n) for n = 1..13 (first 11 terms from _Artem M. Karavaev_, Sep 29 2010; a(12) and a(13) from Pettersson, 2014, added by _N. J. A. Sloane_, Jun 05 2015)
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
Artem M. Karavaev, Hamilton Cycles.
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.
A. Pönitz, Computing invariants in graphs of small bandwidth, Mathematics in Computers and Simulation, 49(1999), 179-191.
A. Pönitz, Über eine Methode zur Konstruktion... PhD Thesis (2004) C.3.
T. G. Schmalz, G. E. Hite and D. J. Klein, Compact self-avoiding circuits on two-dimensional lattices, J. Phys. A 17 (1984), 445-453.
N. J. A. Sloane, Illustration of a(2) = 6.
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles. [Broken link?]
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles. [Backup copy of top page only, on the Internet Archive]
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545 [math.CO], 2014.
Index entries for sequences related to graphs, Hamiltonian.

Other enumerations of Hamiltonian cycles on a square grid: A120443, A140519, A140521, A222200, A222201.

a(n) = A321172(2n,2n). - Robert FERREOL, Apr 01 2019

Two more terms from Andre Poenitz [André Pönitz] and Peter Tittmann (poenitz(AT)htwm.de), Mar 03 2003
a(8) from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 21 2006
a(9) and a(10) from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007

A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.

Original entry on oeis.org

1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, 69450664761521361664274701548907358996488

Offset: 1

David Radcliffe and Don Knuth

The length of the path varies.

			Suppose we start at (1,1) and end at (n,n). Let U, D, L, R denote steps that are up, down, left, right.
a(2) = 2: UR or RU.
a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU and their reflections in the x=y line.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-338.
Guttmann A J and Jensen I 2022 Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices Journal of Physics A: Mathematical and Theoretical 55 012345, (33pp) ; arXiv:2208.06744, Aug 2022.
D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 27-28.
D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
Shin-ichi Minato, The power of enumeration - BDD/ZDD-based algorithms for tackling combinatorial explosion, Chapter 3 of Applications of Zero-Suppressed Decision Diagrams, ed. T. Satsoa and J. T. Butler, Morgan & Claypool Publishers, 2014
Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.
Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).

I. Jensen, H. Iwashita, and R. Spaans, Table of n, a(n) for n = 1..27 (I. Jensen computed terms 1 to 20, H. Iwashita computed 21 and 22, R. Spaans computed 23 to 25, and H. Iwashita computed 26 and 27)
M. Bousquet-Mélou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square, arXiv:cond-mat/0506341 [cond-mat.stat-mech], 2005.
Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtube-animation demonstrating this sequence. In Japanese with English translation]
Steven R. Finch, Self-Avoiding-Walk Connective Constants
Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.
H. Iwashita, J. Kawahara, and S. Minato, ZDD-Based Computation of the Number of Paths in a Graph, TCS Technical Report, TCS-TR-A-12-60, Hokkaido University, September 18, 2012.
H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S. Minato, Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions, TCS Technical Report, TCS-TR-A-13-64, Hokkaido University, April 26, 2013.
I. Jensen, Series Expansions for Self-Avoiding Walks
Shin-ichi Minato, Power of Enumeration - Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation, IEICE Transactions on Information and Systems, Volume E100.D (2017), Issue 8, p. 1556-1562.
Shin-ichi Minato, Motivating Problems and Algorithmic Solutions, Algorithmic Foundations for Social Advancement, Springer, Singapore (2025), 17-29.
OEIS Wiki, Self-avoiding_walks
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, and Isao Tanaka, Derivative structure enumeration using binary decision diagram, arXiv:2002.12603 [physics.comp-ph], 2020.
Ruben Grønning Spaans, C program
Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.
Eric Weisstein's World of Mathematics, Self-Avoiding Walk

Main diagonal of A064298.

Cf. A064297, A271507, A001184, A000532.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A007764(n):
    if n == 1: return 1
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n * n
    paths = GraphSet.paths(start, goal)
    return paths.len()
print([A007764(n) for n in range(1, 10)])  # Seiichi Manyama, Mar 21 2020

Computed to n=12 by John Van Rosendale in 1981
Extended to n=13 by Don Knuth, Dec 07 1995
Extended to n=20 by Mireille Bousquet-Mélou, A. J. Guttmann and I. Jensen
Extended to n=22 using ZDD technique based on Knuth's The Art of Computer Programming (exercise 225 in 7.1.4) by H. Iwashita, J. Kawahara, and S. Minato, Sep 18 2012
Extended to n=25 using state space compression (with rank/unrank) and dynamic programming (based in I. Jensen) by Ruben Grønning Spaans, Feb 22 2013
Extended to n=26 by Hiroaki Iwashita, Apr 11 2013
Extended to n=27 by Hiroaki Iwashita, Nov 18 2013

A228474 Number of steps required to reach zero in the wrecker ball sequence starting with n: On the k-th step (k = 1, 2, 3, ...) move a distance of k in the direction of zero. If the result has occurred before, move a distance of k away from zero instead. Set a(n) = -1 if 0 is never reached.

Original entry on oeis.org

0, 1, 4, 2, 24, 26, 3, 1725, 12, 14, 4, 26, 123, 125, 15, 5, 119, 781802, 20, 22, 132896, 6, 51, 29, 31, 1220793, 23, 25, 7, 429, 8869123, 532009, 532007, 532009, 532011, 26, 8, 94, 213355, 213353, 248, 33, 31, 33, 1000, 9, 144, 110, 112, 82, 84, 210, 60, 34

Offset: 0

Gordon Hamilton, Aug 23 2013

This is a Recamán-like sequence (cf. A005132).
The n-th triangular number A000217(n) has a(A000217(n)) = n.
a(n) + 1 = length of row n in tables A248939 and A248973. - Reinhard Zumkeller, Oct 20 2014
Hans Havermann, running code from Hugo van der Sanden, has found that a(11281) is 3285983871526. - N. J. A. Sloane, Mar 22 2019
If a(n) != -1 then floor((a(n)-1)/2)+n is odd. - Robert Gerbicz, Mar 28 2019

			a(2) = 4 because 2 -> 1 -> -1 -> -4 -> 0.
See A248940 for the full 1725-term trajectory of 7. See A248941 for a bigger example, which shows the start of the 701802-term trajectory of 17. - _N. J. A. Sloane_, Mar 07 2019

Jon E. Schoenfield, Table of n, a(n) for n = 0..10000
Gordon Hamilton, Wrecker Ball Sequences, Video, 2013. [The sequence is mentioned about 4.5 minutes in to the video. The video begins by discussing A005132. - _N. J. A. Sloane_, Apr 25 2019]
Hans Havermann, Table of n, a(n) for n = 0..36617
Hans Havermann, Log-plot of terms through n = 36617
Hans Havermann, Sharp peaks and high plateaus An overview of large knowns and unknowns up to index 10^6.
Index entries for sequences related to Recamán's sequence

Cf. A248939 (rows = the full sequences), A248961 (row sums), A248973 (partial sums per row), A248952 (min per row), A248953 (max per row).
Cf. also A248940 (row 7), A248941 (row 17), A248942 (row 20).
Cf. also A000217, A005132 (Recamán).

a228474 = subtract 1 . length . a248939_row  -- Reinhard Zumkeller, Oct 20 2014
(C++) #include 
  int A228474(long n) { int c=0, s; for(std::map seen; n; n += seen[n-(s=n>0?c:-c)] ? s:-s) { seen[n]=true; ++c; } return c; } // M. F. Hasler, Mar 18 2019

function A228474(n)
    k, position, beenhere = 0, n, [n]
    while position != 0
        k += 1
        step = position > 0 ? k : -k
        position += (position - step) in beenhere ? step : -step
        push!(beenhere, position)
    end
    return length(beenhere) - 1
end
println([A228474(n) for n in 0:16]) # Peter Luschny, Mar 24 2019

# To compute at most the first M steps of the trajectory of n:
f:=proc(n) local M,i,j,traj,h;
  M:=200; traj:=[n]; h:=n; s:=1;
  for i from 1 to M do j:=h-s*i;
    if member(j,traj,'p') then s:=-s; fi;
    h:=h-s*i; traj:=[op(traj),h];
    if h=0 then return("steps, trajectory =", i, traj); fi;
    s:=sign(h);
  od;
  lprint("trajectory so far = ", traj); error("Need to increase M");
end;  # N. J. A. Sloane, Mar 07 2019

{0}~Join~Array[-1 + Length@ NestWhile[Append[#1, If[FreeQ[#1, #3], #3, Sign[#1[[-1]] ] (Abs[#1[[-1]] ] + #2)]] & @@ {#1, #2, Sign[#1[[-1]] ] (Abs[#1[[-1]] ] - #2)} & @@ {#, Length@ #} &, {#}, Last@ # != 0 &] &, 16] (* Michael De Vlieger, Mar 27 2019 *)

a(n)={my(M=Map(),k=0); while(n, k++; mapput(M,n,1); my(t=if(n>0, -k, +k)); n+=if(mapisdefined(M,n+t),-t,t)); k} \\ Charles R Greathouse IV, Aug 18 2014, revised Andrew Howroyd, Feb 28 2018 [Warning: requires latest PARI. - N. J. A. Sloane, Mar 09 2019]

More terms from Jon E. Schoenfield, Jan 10 2014
Escape clause in definition added by N. J. A. Sloane, Mar 07 2019
Edited by M. F. Hasler, Mar 18 2019

A047849 a(n) = (4^n + 2)/3.

Original entry on oeis.org

1, 2, 6, 22, 86, 342, 1366, 5462, 21846, 87382, 349526, 1398102, 5592406, 22369622, 89478486, 357913942, 1431655766, 5726623062, 22906492246, 91625968982, 366503875926, 1466015503702, 5864062014806, 23456248059222, 93824992236886, 375299968947542

Offset: 0

Clark Kimberling

Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - Paul Barry, Mar 10 2004
The number of closed walks of odd length of the cyclic graph is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011
A. A. Ivanov conjectures that the dimension of the universal embedding of the unitary dual polar space DSU(2n,4) is a(n). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004
Permutations with two fixed points avoiding 123 and 132.
Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - Paul Curtz, Mar 25 2008
Also the number of permutations of length n which avoid 4321 and 4123 (or 4321 and 3412, or 4123 and 3214, or 4123 and 2143). - Vincent Vatter, Aug 17 2009; minor correction by Henning Ulfarsson, May 14 2017
This sequence is related to A014916 by A014916(n) = n*a(n)-Sum_{i=0..n-1} a(i). - Bruno Berselli, Jul 27 2010, Mar 02 2012
For n >= 2, a(n) equals 2^n times the permanent of the (2n-2) X (2n-2) tridiagonal matrix with 1/sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
For n > 0, counts closed walks of length (n) at a vertex of a triangle with two (x2) loops at each vertex. - David Neil McGrath, Sep 11 2014
From Michel Lagneau, Feb 26 2015: (Start)
a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
Proof:
All integers of the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} are of the form 2^k(2m+1) where k and m integers. The greatest odd divisor of a such integer is 2m+1. Reciprocally, if 2m+1 is an odd integer <= 2^n, there exists a unique integer in the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:
   a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.
We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)
The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - Peter Bala, Aug 12 2021
Let q = 2^(2n+1) and Omega_n be the Suzuki ovoid with q^2 + 1 points. Then a(n) is the number of orbits of the finite Suzuki group Sz(q) on 3-subsets of Omega_n. Link to result in References. - Paul M. Bradley, Jun 04 2023
Also the cogrowth sequence for the 8-element dihedral group D8 = . - Sean A. Irvine, Nov 04 2024

			a(2) = 6 for the number of round trips in C_6 from the six round trips from, say, vertex no. 1: 12121, 16161, 12161, 16121, 12321 and 16561. - _Wolfdieter Lang_, Nov 08 2011

Bruno Berselli, Table of n, a(n) for n = 0..1000
Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.
Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019.
Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, Riordan graphs I: structural properties, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (2019).
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48. See Conjecture 5.5.
Kittitat Iamthong, Ji-Hwan Jung, and Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020.
D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Mathematics 268 (2003), 171-183.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
Wikipedia, Permutation classes avoiding two patterns of length 4.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.

Cf. A014916, A073724, A020988, A039301.

[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015

(4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* Harvey P. Dale, Nov 27 2015 *)

PARI
```
a(n)=(4^n+2)/3;
```

def A047849(n): return (pow(4, n) +2)//3
print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025

def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025

n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n >= 1.
From Henry Bottomley, Aug 29 2000: (Start)
a(n) = (4^n + 2)/3.
a(n) = 4*a(n-1) - 2.
a(n) = 5*a(n-1) - 4*a(n-2).
a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)
a(n) = A047848(1,n).
With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - Paul Barry, Aug 26 2003
a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - Philippe Deléham, Feb 25 2004
Second binomial transform of A078008. Binomial transform of 1, 1, 3, 9, 81, ... (3^n/3 + 2*0^n/3). a(n) = A078008(2n). - Paul Barry, Mar 14 2004
G.f.: (1-3*x)/((1-x)*(1-4*x)). - Herbert Kociemba, Jun 06 2004
a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - Philippe Deléham, Sep 15 2006
a(n) = (A001045(2*n+1) + 1)/2. - Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.
Sum_{i=0..n} a(i) = A073724(n). (End)
For n >= 3, a(n) equals [2, 1, 1; 1, 2, 1; 1, 1, 2]^(n - 2)*{1, 1, 2}*{1, 1, 2}. - John M. Campbell, Jul 09 2011
a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - Oboifeng Dira, May 29 2020
From Elmo R. Oliveira, Dec 21 2023: (Start)
E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
a(n) = A178789(n+1)/3. (End)
a(n) = A000302(n) - A020988(n). - John Reimer Morales, Aug 03 2025

New name from Charles R Greathouse IV, Dec 22 2011

A063886 Number of n-step walks on a line starting from the origin but not returning to it.

Original entry on oeis.org

1, 2, 2, 4, 6, 12, 20, 40, 70, 140, 252, 504, 924, 1848, 3432, 6864, 12870, 25740, 48620, 97240, 184756, 369512, 705432, 1410864, 2704156, 5408312, 10400600, 20801200, 40116600, 80233200, 155117520, 310235040, 601080390, 1202160780, 2333606220, 4667212440

Offset: 0

Henry Bottomley, Aug 28 2001

A Chebyshev transform of A007877(n+1). The g.f. is transformed to (1+x)/((1-x)(1+x^2)) under the mapping G(x)->(1/(1+x^2))G(1/(1+x^2)). - Paul Barry, Oct 12 2004
a(n-1) = 2*C(n-2, floor((n-2)/2)) is also the number of bit strings of length n in which the number of 00 substrings is equal to the number of 11 substrings. For example, when n = 4 we have 4 such bit strings: 0011, 0101, 1010, and 1100. - Angel Plaza, Apr 23 2009
Hankel transform is A120617. - Paul Barry, Aug 10 2009
The Hankel transform of a(n) is (-2)^C(n+1,2). The Hankel transform of (-1)^C(n+1,2)*a(n) is (-1)^C(n+1,2)*A164584(n). - Paul Barry, Aug 17 2009
For n > 1, a(n) is also the number of n-step walks starting from the origin and returning to it exactly once. - Geoffrey Critzer, Jan 24 2010
-a(n) is the Z-sequence for the Riordan array A130777. (See the W. Lang link under A006232 for A- and Z-sequences for Riordan matrices). - Wolfdieter Lang, Jul 12 2011
Number of subsets of {1,...,n} in which the even elements appear as often at even positions as at odd positions. - Gus Wiseman, Mar 17 2018

			a(4) = 6 because there are six length four walks that do not return to the origin: {-1, -2, -3, -4}, {-1, -2, -3, -2}, {-1, -2, -1, -2}, {1, 2, 1, 2}, {1, 2, 3, 2}, {1, 2, 3, 4}. There are also six such walks that return exactly one time: {-1, -2, -1, 0}, {-1, 0, -1, -2}, {-1, 0, 1, 2}, {1, 0, -1, -2}, {1, 0, 1, 2}, {1, 2, 1, 0}. - _Geoffrey Critzer_, Jan 24 2010
The a(5) = 12 subsets in which the even elements appear as often at even positions as at odd positions: {}, {1}, {3}, {5}, {1,3}, {1,5}, {2,4}, {3,5}, {1,2,4}, {1,3,5}, {2,4,5}, {1,2,4,5}. - _Gus Wiseman_, Mar 17 2018

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Emeric Deutsch, Problem 11424, The American Mathematical Monthly, Vol. 116, No. 3 (March 2009), p. 277.
D. Perrin, A conjecture on rational sequences, pp. 267-274 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.

Apart from initial terms, same as A182027.
Cf. A000108, A000246, A000712, A000984, A001405, A001700, A002420, A006232, A007877, A026010, A028329, A045931, A047073, A089849, A097613, A106180, A120617, A130777, A130780, A138364, A164584, A171966, A239241, A300787, A300788, A300789.
Cf. A307768 (complementary event).

[1] cat [2*Binomial(n-1, Floor((n-1)/2)): n in [1..40]]; // G. C. Greubel, Jun 07 2023

seq(seq(binomial(2*j,j)*i, i=1..2),j=0..16); # Zerinvary Lajos, Apr 28 2007
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n+1,
       4*a(n-2) +2*(a(n-1) -4*a(n-2))/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 10 2014
# third program:
A063886 := series(BesselI(0, 2*x)*(1 + x*2 + x*Pi*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x), x = 0, 34): seq(n!*coeff(A063886, x, n), n = 0 .. 33); # Mélika Tebni, Jun 17 2024

Table[Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == 0 &]], {n, 0, 20}] (* Geoffrey Critzer, Jan 24 2010 *)
CoefficientList[Series[Sqrt[(1+2x)/(1-2x)],{x,0,40}],x] (* Harvey P. Dale, Apr 28 2016 *)

PARI
```
a(n)=(n==0)+2*binomial(n-1,(n-1)\2)
```

a(n) = 2^n*prod(k=0,n-1,(k/n+1/n)^((-1)^k)); \\ Michel Marcus, Dec 03 2013

from math import ceil
from sympy import binomial
def a(n):
    if n==0: return 1
    return 2*binomial(n-1,(n-1)//2)
print([a(n) for n in range(18)])
# David Nacin, Feb 29 2012

[2*binomial(n-1, (n-1)//2) + int(n==0) for n in range(41)] # G. C. Greubel, Jun 07 2023

G.f.: sqrt((1+2*x)/(1-2*x)).
a(n+1) = 2*C(n, floor(n/2)) = 2*A001405(n); a(2n) = C(2n, n) = A000984(n) = 4*a(2n-2)-|A002420(n)| = 4*a(2n-2)-2*A000108(n-1) = 2*A001700(n-1); a(2n+1) = 2*a(2n) = A028329(n).
2*a(n) = A047073(n+1).
a(n) = Sum_{k=0..n} abs(A106180(n,k)). - Philippe Deléham, Oct 06 2006
a(n) = Sum_{k=0..n} (k+1)binomial(n, (n-k)/2) ( 1-cos((k+1)*Pi/2) (1+(-1)^(n-k))/(n+k+2) ). - Paul Barry, Oct 12 2004
G.f.: 1/(1-2*x/(1+x/(1+x/(1-x/(1-x/(1+x/(1+x/(1-x/(1-x/(1+ ... (continued fraction). - Paul Barry, Aug 10 2009
G.f.: 1 + 2*x/(G(0)-x+x^2) where G(k)= 1 - 2*x^2 - x^4/G(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Aug 10 2012
D-finite with recurrence: n*a(n) = 2*a(n-1) + 4*(n-2)*a(n-2). - R. J. Mathar, Dec 03 2012
From Sergei N. Gladkovskii, Jul 26 2013: (Start)
G.f.: 1/G(0), where G(k) = 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: G(0), where G(k) = 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: W(0)/2*(1+2*x), where W(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)/(x*(2*k+1))/W(k+1) )), abs(x) < 1/2; (continued fraction). (End)
a(n) = 2^n*Product_{k=0..n-1} (k/n + 1/n)^((-1)^k). - Peter Luschny, Dec 02 2013
G.f.: G(0), where G(k) = 1 + 2*x*(4*k+1)/((2*k+1)*(1+2*x) - (2*k+1)*(4*k+3)*x*(1+2*x)/((4*k+3)*x + (k+1)*(1+2*x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 19 2014
From Peter Bala, Mar 29 2024: (Start)
a(n) = 2^n * Sum_{k = 0..n} (-1)^(n+k)*binomial(1/2, k)*binomial(- 1/2, n-k) = 2^n * A000246(n)/n!.
a(n) = (1/2^n) * binomial(2*n, n) * hypergeom([-1/2, -n], [1/2 - n], -1). (End)
E.g.f.: BesselI(0, 2*x)*(1 + x*(2 + Pi)*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x). - Stefano Spezia, May 11 2024
a(n) = A089849(n) + A138364(n). - Mélika Tebni, Jun 17 2024
From Amiram Eldar, Aug 15 2025: (Start)
Sum_{n>=0} 1/a(n) = Pi/(3*sqrt(3)) + 2.
Sum_{n>=0} (-1)^n/a(n) = 2/3 + Pi/(9*sqrt(3)). (End)

A068911 Number of n-step walks (each step +-1 starting from 0) which are never more than 2 or less than -2.

Original entry on oeis.org

1, 2, 4, 6, 12, 18, 36, 54, 108, 162, 324, 486, 972, 1458, 2916, 4374, 8748, 13122, 26244, 39366, 78732, 118098, 236196, 354294, 708588, 1062882, 2125764, 3188646, 6377292, 9565938, 19131876, 28697814, 57395628, 86093442, 172186884, 258280326, 516560652

Offset: 0

Henry Bottomley, Mar 06 2002

From Johannes W. Meijer, May 29 2010: (Start)
a(n) is the number of ways White can force checkmate in exactly (n+1) moves, n >= 0, ignoring the fifty-move and the triple repetition rules, in the following chess position: White Ka1, Ra8, Bc1, Nb8, pawns a6, a7, b2, c6, d2, f6, g5 and h6; Black Ke8, Nh8, pawns b3, c7, d3, f7, g6 and h7. (After Noam D. Elkies, see link; diagram 5).
Counts all paths of length n, n >= 0, starting at the third node on the path graph P_5, see the Maple program. (End)
From Alec Jones, Feb 25 2016: (Start)
The a(n) are the n-th terms in a "Fibonacci snake" drawn on a rectilinear grid. The n-th term is computed as the sum of the previous terms in cells adjacent to the n-th cell (diagonals included). (This sequence excludes the first term of the snake.)
For example:
  1 ...  1      1  ...   1 4      1 4 6 ...  1 4 6       1 4 6   ...  and so on.
         1 ...  1 2      1 2 ...  1 2        1 2 12 ...  1 2 12 18 (End)
From Gus Wiseman, Oct 06 2023: (Start)
Also the number of subsets of {1..n} containing no two distinct elements summing to n. The a(0) = 1 through a(4) = 12 subsets are:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,3}  {4}
                  {2,3}  {1,2}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,2,4}
                         {2,3,4}
For n+1 instead of n we have A038754, complement A167762.
Including twins gives A117855, complement A366131.
The complement is counted by A365544.
For all subsets (not just pairs) we have A365377, complement A365376. (End)

			The a(3) = 6 walks: (0,-1,-2,-1), (0,-1,0,-1), (0,-1,0,1), (0,1,0,-1), (0,1,0,1), (0,1,2,1). - _Gus Wiseman_, Oct 10 2023

Alois P. Heinz, Table of n, a(n) for n = 0..4191
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
Robert Dorward et al., A Generalization of Zeckendorf's Theorem via Circumscribed m-gons, arXiv:1508.07531 [math.NT], 2015. See Example 1.3 p. 4.
Noam D. Elkies, New Directions in Enumerative Chess Problems, arXiv:math/0508645 [math.CO], 2005; The Electronic Journal of Combinatorics, 11 (2), 2004-2005.
Sean A. Irvine, Walks on Graphs.
D. Panario, M. Sahin, Q. Wang, and W. Webb, General conditional recurrences, Applied Mathematics and Computation, Volume 243, Sep 15 2014, Pages 220-231.
Noriaki Sannomiya, H. Katsura, and Y. Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv preprint arXiv:1612.02285 [cond-mat.str-el], 2016-2017. See Table I, line 3.
Index entries for linear recurrences with constant coefficients, signature (0,3).

Cf. A000007, A016116 (without initial term), A068912, A068913 for similar.
Equals A060647(n-1)+1.
Cf. also A028495, A038754, A048328, A078038, A124302, A306293.
First differences are A117855.
Cf. A004526, A004737, A008967, A046663, A088809, A365376, A365377, A365381, A365541, A365544, A366130.

[Floor((5-(-1)^n)*3^Floor(n/2)/3): n in [0..40]]; // Bruno Berselli, Feb 26 2016, after Charles R Greathouse IV

with(GraphTheory): G:= PathGraph(5): A:=AdjacencyMatrix(G): nmax:=34; for n from 0 to nmax do B(n):=A^n; a(n):=add(B(n)[3,k], k=1..5) od: seq(a(n), n=0..nmax); # Johannes W. Meijer, May 29 2010
# second Maple program:
a:= proc(n) a(n):= `if`(n<2, n+1, (4-irem(n, 2))/2*a(n-1)) end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 03 2019

Join[{1},Transpose[NestList[{Last[#],3First[#]}&,{2,4},40]][[1]]] (* Harvey P. Dale, Oct 24 2011 *)
Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#,{2}],n]&]],{n,0,15}] (* Gus Wiseman, Oct 06 2023 *)

a(n)=[4,6][n%2+1]*3^(n\2)\3 \\ Charles R Greathouse IV, Feb 26 2016

def A068911(n): return 3**(n>>1)<<1 if n&1 else (3**(n-1>>1)<<2 if n else 1) # Chai Wah Wu, Aug 30 2024

a(n) = A068913(2, n) = 2*A038754(n-1) = 3*a(n-2) = a(n-1)*a(n-2)/a(n-3) starting with a(0)=1, a(1)=2, a(2)=4 and a(3)=6.
For n>0: a(2n) = 4*3^(n-1) = 2*a(2n-1); a(2n+1) = 2*3^n = 3*a(2n)/2 = 2*a(2n)-A000079(n-2).
From Paul Barry, Feb 17 2004: (Start)
G.f.: (1+x)^2/(1-3x^2).
a(n) = 2*3^((n+1)/2)*((1-(-1)^n)/6 + sqrt(3)*(1+(-1)^n)/9) - (1/3)*0^n.
The sequence 0, 1, 2, 4, ... has a(n) = 2*3^(n/2)*((1+(-1)^n)/6 + sqrt(3)*(1-(-1)^n)/9) - (2/3)*0^n + (1/3)*Sum_{k=0..n} binomial(n, k)*k*(-1)^k. (End)
a(n) = 2^((3 + (-1)^n)/2)*3^((2*n - 3 - (-1)^n)/4) - ((1 - (-1)^(2^n)))/6. - Luce ETIENNE, Aug 30 2014
For n > 2, indexing from 0, a(n) = a(n-1) + a(n-2) if n is odd, a(n-1) + a(n-2) + a(n-3) if n is even. - Alec Jones, Feb 25 2016
a(n) = 2*a(n-1) if n is even, a(n-1) + a(n-2) if n is odd. - Vincenzo Librandi, Feb 26 2016
E.g.f.: (4*cosh(sqrt(3)*x) + 2*sqrt(3)*sinh(sqrt(3)*x) - 1)/3. - Stefano Spezia, Feb 17 2022

A052179 Triangle of numbers arising in enumeration of walks on cubic lattice.

Original entry on oeis.org

1, 4, 1, 17, 8, 1, 76, 50, 12, 1, 354, 288, 99, 16, 1, 1704, 1605, 700, 164, 20, 1, 8421, 8824, 4569, 1376, 245, 24, 1, 42508, 48286, 28476, 10318, 2380, 342, 28, 1, 218318, 264128, 172508, 72128, 20180, 3776, 455, 32, 1, 1137400, 1447338

Offset: 0

N. J. A. Sloane, Jan 26 2000

Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 4*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 4*T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
Triangle read by rows: T(n,k) = number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and four types of steps H=(1,0); example: T(3,1)=50 because we have UDU, UUD, 16 HHU paths, 16 HUH paths and 16 UHH paths. - Philippe Deléham, Sep 25 2007
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007
Riordan array ((1-4x-sqrt(1-8x+12x^2))/(2x^2), (1-4x-sqrt(1-8x+12x^2))/(2x)). Inverse of A159764. - Paul Barry, Apr 21 2009
6^n = (n-th row terms) dot (first n+1 terms in (1,2,3,...)). Example: 6^3 =  216 = (76, 50, 12, 1) dot (1, 2, 3, 4) = (76 + 100 + 36 + 4) = 216. - Gary W. Adamson, Jun 15 2011
A subset of the "family of triangles" (Deléham comment of Sep 25 2007) is the succession of binomial transforms beginning with triangle A053121, (0,0); giving -> A064189, (1,1); -> A039598, (2,2); -> A091965, (3,3); -> A052179, (4,4); -> A125906, (5,5) ->, etc.; generally the binomial transform of the triangle generated from (n,n) = that generated from ((n+1),(n+1)). - Gary W. Adamson, Aug 03 2011

			Triangle begins:
    1;
    4,   1;
   17,   8,   1;
   76,  50,  12,   1;
  354, 288,  99,  16,   1;
  ...
Production matrix begins:
  4, 1;
  1, 4, 1;
  0, 1, 4, 1;
  0, 0, 1, 4, 1;
  0, 0, 0, 1, 4, 1;
  0, 0, 0, 0, 1, 4, 1;
  0, 0, 0, 0, 0, 1, 4, 1;
- _Philippe Deléham_, Nov 04 2011

G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened
Rigoberto Flórez, Leandro Junes, José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6.

Cf. A039598, A053121, A064189, A091965.

T:= proc(n, k) option remember; `if`(min(n, k)<0, 0,
     `if`(max(n, k)=0, 1, T(n-1, k-1)+4*T(n-1, k)+T(n-1, k+1)))
    end:
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Oct 28 2021

t[0, 0] = 1; t[n_, k_] /; k < 0 || k > n = 0; t[n_, 0] := t[n, 0] = 4*t[n-1, 0] + t[n-1, 1]; t[n_, k_] := t[n, k] = t[n-1, k-1] + 4*t[n-1, k] + t[n-1, k+1]; Flatten[ Table[t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, Oct 10 2011, after Philippe Deleham *)

Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A005572(m+n). - Philippe Deléham, Sep 15 2005
n-th row = M^n * V, where M = the infinite tridiagonal matrix with all 1's in the super and subdiagonals and (4,4,4,...) in the main diagonal. E.g., Row 3 = (76, 50, 12, 1) since M^3 * V = [76, 50, 12, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 04 2006
Sum_{k=0..n} T(n,k) = A005573(n). - Philippe Deléham, Feb 04 2007
Sum_{k=0..n} T(n,k)*(k+1) = 6^n. - Philippe Deléham, Mar 27 2007
Sum_{k=0..n} T(n,k)*x^k = A033543(n), A064613(n), A005572(n), A005573(n) for x = -2, -1, 0, 1 respectively. - Philippe Deléham, Nov 28 2009
As an infinite lower triangular matrix = the binomial transform of A091965 and 4th binomial transform of A053121. - Gary W. Adamson, Aug 03 2011
G.f.: 2/(1 - 4*x - 2*x*y + sqrt(1 - 8*x + 12*x^2)). - Daniel Checa, Aug 17 2022
G.f. for the m-th column: x^m*(A(x))^(m+1), where A(x) is the g.f. of the sequence counting the walks on the cubic lattice starting and finishing on the xy plane and never going below it (A005572). Explicitly, the g.f. is x^m*((1 - 4*x - sqrt(1 - 8*x + 12*x^2))/(2*x^2))^(m+1). - Daniel Checa, Aug 28 2022

A151374 Number of walks within N^2 (the first quadrant of Z^2) starting at (0, 0), ending on the vertical axis and consisting of 2n steps taken from {(-1, -1), (-1, 0), (1, 1)}.

Original entry on oeis.org

1, 2, 8, 40, 224, 1344, 8448, 54912, 366080, 2489344, 17199104, 120393728, 852017152, 6085836800, 43818024960, 317680680960, 2317200261120, 16992801914880, 125210119372800, 926554883358720, 6882979133521920, 51309480813527040, 383705682605506560, 2877792619541299200

Offset: 0

Manuel Kauers, Nov 18 2008

A052701 shifted one place left. - R. J. Mathar, Dec 13 2008
Expansion of c(2*x), where c(x) is the g.f. of A000108. - Philippe Deléham, Feb 26 2009; simplified by Alexander Burstein, Jul 31 2018
From Joerg Arndt, Oct 22 2012: (Start)
Also the number of strings of length 2*n of two different types of balanced parentheses.
For example, a(1) = 2, since the two possible strings of length 2 are [] and (), a(2) = 8, since the 8 possible strings of length 4 are (()), [()], ([]), [[]], ()(), [](), ()[], and [][].
The number of strings of length 2*n of t different types of balanced parentheses is given by t^n * A000108(n): there are n opening parentheses in the strings, giving t^n choices for the type (the closing parentheses are chosen to match). (End)
Number of Dyck paths of length 2n in which the step U=(1,1) come in 2 colors. - José Luis Ramírez Ramírez, Jan 31 2013
Row sums of triangle in A085880. - Philippe Deléham, Nov 15 2013
Hankel transform is 2^(n+n^2) = A053763(n+1). - Philippe Deléham, Nov 15 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
J. Bouttier, P. Di Francesco and E. Guitter, Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nucl. Phys. B, Vol. 675, No. 3 (2003), pp. 631-660. See p. 631, eq. (3.3).
Marek Bożejko, Maciej Dołęga, Wiktor Ejsmont and Światosław R. Gal, Reflection length with two parameters in the asymptotic representation theory of type B/C and applications, arXiv:2104.14530 [math.RT], 2021.
Vedran Čačić and Vjekoslav Kovač, On the fraction of IL formulas that have normal forms, arXiv:1309.3408 [math.LO], 2013.
Stefano Capparelli and Alberto Del Fra, Dyck Paths, Motzkin Paths, and the Binomial Transform, Journal of Integer Sequences, Vol. 18 (2015), Article 15.8.5.
Grégory Chatel and Vincent Pilaud, Cambrian Hopf algebras, Adv. Math. 311, 598-633 (2017). Prop. 3.
Zhi Chen and Hao Pan, Identities involving weighted Catalan-Schröder and Motzkin Paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=b=2.
Nicolas Crampe, Julien Gaboriaud and Luc Vinet, Racah algebras, the centralizer Z_n(sl_2) and its Hilbert-Poincaré series, arXiv:2105.01086 [math.RT], 2021.
Hsien-Kuei Hwang, Mihyun Kang and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Georg Muntingh, Implicit Divided Differences, Little Schröder Numbers and Catalan Numbers, J. Int. Seq., Vol. 15 (2012), Article 12.6.5; arXiv preprint, arXiv:1204.2709 [math.CO], 2012.
L. Poulain d'Andecy, Centralisers and Hecke algebras in Representation Theory, with applications to Knots and Physics, arXiv:2304.00850 [math.RT], 2023. See p. 64.

Cf. A000108, A046521, A052701, A053763, A085880.

[2^n * Catalan(n): n in [0..25]]; // Vincenzo Librandi, Oct 24 2012

A151374_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 2*(a[w-1]+add(a[j]*a[w-j-1],j=1..w-1)) od;
convert(a,list)end: A151374_list(23); # Peter Luschny, May 19 2011

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

my(x='x+O('x^66)); Vec(sqrt(2-8*x-2*sqrt(1-8*x))/(4*x)) \\ Joerg Arndt, May 11 2013

def A151374():
    a, n = 1, 1
    while True:
        yield a
        n += 1
        a = a * (8*n - 12) // n
A = A151374()
print([next(A) for  in range(24)]) # _Peter Luschny, Nov 30 2016

a(n) = 2^n * A000108(n). - Philippe Deléham, Feb 01 2009
From Gary W. Adamson, Jul 12 2011: (Start)
a(n) is the top left term in M^n, M = the following infinite square production matrix:
   2, 2, 0, 0, 0, 0, ...
   2, 2, 2, 0, 0, 0, ...
   2, 2, 2, 2, 0, 0, ...
   2, 2, 2, 2, 2, 0, ...
   2, 2, 2, 2, 2, 2, ...
   ...
(End)
E.g.f.: KummerM(1/2, 2, 8*x). - Peter Luschny, Aug 26 2012
From Sergei N. Gladkovskii, Apr 05 2013: (Start)
E.g.f.: Let F(x)=Sum_{n>=0} a(n)*x^n/(2*n)!, then F(x) = E(0)/(1-sqrt(x)) where E(k) = 1 - sqrt(x)/(1 - sqrt(x)/(sqrt(x) - (k+1)*(k+2)/2/E(k+1) )); (continued fraction ).
G.f.: 1 + 4*x/(G(0)-4*x) where G(k) = k*(8*x+1) + 4*x + 2 - 2*x*(2*k+3)*(2*k+4)/G(k+1); (continued fraction). (End)
G.f.: sqrt(2-8*x-2*sqrt(1-8*x))/(4*x). - Mark van Hoeij, May 10 2013
G.f.: (1-sqrt(1-8*x))/(4*x). - Philippe Deléham, Nov 15 2013
D-finite with recurrence (n+1)*a(n) + 4*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Mar 05 2014
a(n) = 4^n*2F1((1-n)/2,-n/2;1;1)/(n+1). - Benedict W. J. Irwin, Jul 12 2016
a(n) ~ 8^n*n^(-3/2)/sqrt(Pi). - Ilya Gutkovskiy, Jul 12 2016
From Peter Bala, Aug 17 2021: (Start)
a(n) = Sum_{k = 0..floor(n/2)} A046521(n,2*k)*Catalan(2*k).
G.f.: A(x) = 1/sqrt(1 - 4*x)*e(x/(1 - 4*x)), where e(x) = (c(x) + c(-x))/2 is the even part of the function c(x) = (1 - sqrt(1 - 4*x))/(2*x), the g.f. of the Catalan numbers A000108. Inversely, (c(x) + c(-x))/2 = 1/sqrt(1 + 4*x)*A(x/(1 + 4*x)).
x*A(x) = Series reversion of (x - 2*x^2). (End)
Sum_{n>=0} 1/a(n) = 68/49 + 96*arctan(1/sqrt(7)) / (49*sqrt(7)). - Vaclav Kotesovec, Nov 23 2021
Sum_{n>=0} (-1)^n/a(n) = 20/27 - 16*log(2)/81. - Amiram Eldar, Jan 25 2022
G.f.: 1/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-...))))))))) (continued fraction). - Nikolaos Pantelidis, Nov 20 2022
a(n) = 2*Sum_{k=1..n} a(k-1)*a(n-k), a(0) = 1. - Mehdi Naima, Jan 16 2023

cp's OEIS Frontend

A006356 a(n) = 2*a(n-1) + a(n-2) - a(n-3) for n >= 3, starting with a(0) = 1, a(1) = 3, and a(2) = 6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Formula

Extensions

A001412 Number of n-step self-avoiding walks on cubic lattice.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Python

A003763 Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

A228474 Number of steps required to reach zero in the wrecker ball sequence starting with n: On the k-th step (k = 1, 2, 3, ...) move a distance of k in the direction of zero. If the result has occurred before, move a distance of k away from zero instead. Set a(n) = -1 if 0 is never reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Julia

Maple

Mathematica

PARI

Extensions

A047849 a(n) = (4^n + 2)/3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI