keyword:walk - cp's OEIS frontend

A054879 Closed walks of length 2n along the edges of a cube based at a vertex.

1, 3, 21, 183, 1641, 14763, 132861, 1195743, 10761681, 96855123, 871696101, 7845264903, 70607384121, 635466457083, 5719198113741, 51472783023663, 463255047212961, 4169295424916643, 37523658824249781, 337712929418248023, 3039416364764232201, 27354747282878089803, 246192725545902808221

Offset: 0

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

a(n) is the number of words of length 2n on alphabet {0,1,2} with an even number (possibly zero) of each letter. - Geoffrey Critzer, Dec 20 2012

Equivalently, the cogrowth sequence of the 8-element group C2^3. - Sean A. Irvine, Nov 04 2024

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
G. Benkart and D. Moon, A Schur-Weyl Duality Approach to Walking on Cubes, arXiv preprint arXiv:1409.8154 [math.RT], 2014 and Ann. Combin. 20 (3) (2016) 397-417
R. B. Brent, Generalizing Tuenter's Binomial Sums, J. Int. Seq. 18 (2015) # 15.3.2.
G. R. Franssens, On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]
Ji-Hwan Jung, Oriented Riordan graphs and their fractal property, arXiv:2009.01677 [math.CO], 2020.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 5.
L. Reyzin, Number of closed walks on an n-cube, Mathoverflow.
Index entries for linear recurrences with constant coefficients, signature (10,-9).

Cf. A081294, A092812, A121822, A122983.

[(3^(2*n)+3)/4: n in [0..25]]; // Vincenzo Librandi, Jun 30 2011

nn = 40; Select[Range[0, nn]! CoefficientList[Series[Cosh[x]^3, {x, 0, nn}], x], # > 0 &]  (* Geoffrey Critzer, Dec 20 2012 *)
Table[(3^(2n)+3)/4,{n,0,30}] (* or *) LinearRecurrence[{10,-9},{1,3},30] (* Harvey P. Dale, Mar 17 2023 *)

a(n) = (3^(2*n)+3)/4.
G.f.: 1/4*1/(1-9*x)+3/4*1/(1-x).
a(n) = Sum_{k=0..n} 3^k*4^(n-k)*A121314(n,k). - Philippe Deléham, Aug 26 2006
E.g.f.: cosh^3(x). O.g.f.: 1/(1-3*1*x/(1-2*2*x/(1-1*3*x))) (continued fraction). - Peter Bala, Nov 13 2006
(-1)^n*a(n) = Sum_{k=0..n} A086872(n,k)*(-4)^(n-k). - Philippe Deléham, Aug 17 2007
a(n) = (1/2^3)*Sum_{j = 0..3} binomial(3,j)*(3 - 2*j)^(2*n). See Reyzin link. - Peter Bala, Jun 03 2019
a(n) = 9*a(n-1) - 6. - Klaus Purath, Mar 13 2021

A100982 Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant.

Original entry on oeis.org

1, 1, 2, 3, 7, 12, 30, 85, 173, 476, 961, 2652, 8045, 17637, 51033, 108950, 312455, 663535, 1900470, 5936673, 13472296, 39993895, 87986917, 257978502, 820236724, 1899474678, 5723030586, 12809477536, 38036848410, 84141805077, 248369601964

Offset: 1

Steven Finch, Jan 13 2005

Eric Roosendaal counted all admissible sequences up to order j=1000 (2005). Note: there is a typo in both Wagon and Chamberland in the definition of Wagon's constant 9.477955... The expression floor(1 + 2*i + i*log_2(3)) should be replaced by floor(1 + i + i*log_2(3)).
The length of all admissible sequences of order j is A020914(j). - T. D. Noe, Sep 11 2006
Conjecture: a(n) is given for each n > 3 by a formula using a(2)..a(n-1). This allows us to create an iterative algorithm which generates a(n) for each n > 6. This has been proved for each n <= 53. For higher values of n the algorithm must be slightly modified. - Mike Winkler, Jan 03 2018
Theorem 1: a(k) is given for each k > 1 by a formula using a(1)..a(k-1). Namely, a(1)=1 and a(k+1) = Sum_{m=1..k} (-1)^(m-1)*binomial(floor((k-m+1)*(log(3)/log(2))) + m - 1, m)*a(k-m+1) for k >= 1. - Vladimir M. Zarubin, Sep 25 2015
Theorem 2: a(n) can be generated for each n > 2 algorithmically in a Pascal's triangle-like manner from the two starting values 0 and 1. This result is based on the fact that the Collatz residues (mod 2^k) can be evolved according to a binary tree. There is a direct connection with A076227, A056576 and A022921. - Mike Winkler, Sep 12 2017
A177789 shows another theorem and algorithm for generating a(n). - Mike Winkler, Sep 12 2017

			The unique admissible sequence of order 1 is 3/2, 1/2.
The unique admissible sequence of order 2 is 3/2, 3/2, 1/2, 1/2.
The two admissible sequences of order 3 are 3/2, 3/2, 3/2, 1/2, 1/2 and 3/2, 3/2, 1/2, 3/2, 1/2.
a(13) = 8045 = binomial(floor(5*(13-2)/3), 13-2)
- Sum_{i=2..6} binomial(floor((3*(13-i)+0)/2), 13-i)*a(i)
- Sum_{i=7..11} binomial(floor((3*(13-i)-1)/2), 13-i)*a(i)
- Sum_{i=12..12} binomial(floor((3*(13-i)-2)/2), 13-i)*a(i)
= 31824 - 4368*1 - 3003*2 - 715*3 - 495*7 - 120*12 - 28*30 - 21*85 - 5*173 - 4*476 - 1*961 - 0*2652. (Conjecture)
From _Mike Winkler_, Sep 12 2017: (Start)
The next table shows how Theorem 2 works. No entry is equal to zero.
n =       3  4  5   6   7   8   9  10  11   12 .. |A076227(k)=
--------------------------------------------------|
k =  2 |  1                                       |     1
k =  3 |  1  1                                    |     2
k =  4 |     2  1                                 |     3
k =  5 |        3   1                             |     4
k =  6 |        3   4   1                         |     8
k =  7 |            7   5   1                     |    13
k =  8 |               12   6   1                 |    19
k =  9 |               12  18   7   1             |    38
k = 10 |                   30  25   8   1         |    64
k = 11 |                   30  55  33   9    1    |   128
:      |                        :   :   :    : .. |    :
--------------------------------------------------|---------
a(n) =    2  3  7  12  30  85 173 476 961 2652 .. |
The entries (k,n) in this table are generated by the rule (k+1,n) = (k,n) + (k,n-1). The last value of (k+1,n) is given by k+1 = A056576(n-1), or the highest value in column n is given twice only if A022921(n-2) = 2. Then a(n) is equal to the sum of the entries in column n. For n = 7 there is 1 = 0 + 1, 5 = 1 + 4, 12 = 5 + 7, 12 = 12 + 0. Therefore a(7) = 1 + 5 + 12 + 12 = 30. The sum of row k is equal to A076227(k). (End)
From _Ruud H.G. van Tol_, Dec 04 2023: (Start)
A tree view.
n-tree--A098294--ids-----paths-----------------a(n)
0 ._          0  0       0                       -
1 |_          1  1       10                      1
2 |_._        2  2       1100                    1
3 |_|_        2  3-4     11010     -   11100     2
4 |_|_._      3  5-7     1101100   -  1111000    3
5 |_|_|_      3  8-14    11011010  - 11111000    7
6 |_|_|_._    4  15-26   1101101100-1111110000  12
7 |_|_|_|_._  5  27-56   ...                    30
8 |_|_|_|_|_  5  57-141  ...                    85
...
For n>=1, the endpoints are at A098294(n) to the right.
(End)

T. D. Noe, Table of n, a(n) for n = 1..500
M. Chamberland, Una actualizacio del problema 3x+1, Butl. Soc. Catalana Mat. 18 (2003) 19-45.
M. Chamberland, English translation
Ruud H.G. van Tol, Sequence as counts of lattice walks
Ruud H.G. van Tol, A100982 Musings
Stan Wagon, The Collatz problem, Math. Intelligencer 7 (1985) 72-76.
Mike Winkler, On a stopping time algorithm of the 3n + 1 function, 2011.
Mike Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence, arXiv:1412.0519 [math.GM], 2014.
Mike Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015.
Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017.

Cf. A122790 (Wagon's constant), A076227, A056576, A022921, A098294, A177789.

Cf. A060941, A293946.

(* based on Eric Roosendaal's algorithm *) nn=100; Clear[x,y]; Do[x[i]=0, {i,0,nn+1}]; x[1]=1; t=Table[Do[y[cnt]=x[cnt]+x[cnt-1], {cnt,p+1}]; Do[x[cnt]=y[cnt], {cnt,p+1}]; admis=0; Do[If[(p+1-cnt)*Log[3]T. D. Noe, Sep 11 2006 *)

/* translation of the above code from T. D. Noe */
{limit=100; n=1; x=y=vector(limit+1); x[1]=1; for(b=2, limit, for(c=2, b+1, y[c]=x[c]+x[c-1]); for(c=2, b+1, x[c]=y[c]); a_n=0; for(c=1, b+1, if((b+1-c)*log(3)Mike Winkler, Feb 28 2015

/* algorithm for the Conjecture */
{limit=53; zn=vector(limit); zn[2]=1; zn[3]=2; zn[4]=3; zn[5]=7; zn[6]=12; f=1; e1=-1; e2=-2; for(n=7, limit, m=floor((n-1)*log(3)/log(2))-(n-1); j=(m+n-2)!/(m!*(n-2)!); if(n>6*f, if(frac(n/2)==0, e=e1, e=e2)); if(frac((n-6 )/12)==0, f++; e1=e1+2); if(frac((n-12)/12)==0, f++; e2=e2+2); Sum=a=b=0; c=1; d=5; until(c>=n-1, for(i=2+a*5+b, 1+d+a*5, if(i>11 && frac((i+2)/6)==0, b++); delta=e-a; Sum=Sum+binomial(floor((3*(n-i)+delta)/2),n-i)*zn[i]; c++); a++; for(k=3, 50, if(n>=k*6 && a==k-1, d=k+3))); zn[n]=j-Sum; print(n" "zn[n]))} \\ Mike Winkler, Jan 03 2018

/* cf. code for Theorem 2 */
{limit=100; /*or limit>100*/ p=q=vector(limit); c=2; w=log(3)/log(2); for(n=3, limit, p[1]=Sum=1; for(i=2, c, p[i]=p[i-1]+q[i]; Sum=Sum+p[i]); a_n=Sum; print(n" "a_n); for(i=1, c, q[i]=p[i]); d=floor(n*w)-floor((n-1)*w); if(d==2, c++)); } \\ Mike Winkler, Apr 14 2015

/* algorithm for Theorem 1 */
n=20; a=vector(n); log32=log(3)/log(2);
{a[1]=1; for ( k=1, n-1, a[k+1]=sum( m=1,k,(-1)^(m-1)*binomial( floor( (k-m+1)*log32)+m-1,m)*a[k-m+1] ); print(k" "a[k]) );
} \\ Vladimir M. Zarubin, Sep 25 2015

/* algorithm for Theorem 2 */
{limit=30; /*or limit>30*/ R=matrix(limit,limit); R[2,1]=0; R[2,2]=1; for(n=2, limit, print; print1("For n="n" in column n: "); Kappa_n=floor(n*log(3)/log(2)); a_n=0; for(k=n, Kappa_n, R[k+1,n]=R[k,n]+R[k,n-1]; print1(R[k+1,n]", "); a_n=a_n+R[k+1,n]); print; print(" and the sum is a(n)="a_n))} \\ Mike Winkler, Sep 12 2017

A sequence s(k), where k=1, 2, ..., n, is *admissible* if it satisfies s(k)=3/2 exactly j times, s(k)=1/2 exactly n-j times, s(1)*s(2)*...*s(n) < 1 but s(1)*s(2)*...*s(m) > 1 for all 1 < m < n.
a(n) = (m+n-2)!/(m!*(n-2)!) - Sum_{i=2..n-1} binomial(floor((3*(n-i)+b)/2), n-i)*a(i), where m = floor((n-1)*log_2(3))-(n-1) and b assumes different integer values within the sum at intervals of 5 or 6 terms. (Conjecture)
a(n) = Sum_{k=n-1..A056576(n-1)} (k,n). (Theorem 2, cf. example)
a(k) = 2*A076227(A020914(k)-1) - A076227(A020914(k)), for k > 0. - Vladimir M. Zarubin, Sep 29 2019
a(1)=1, a(n) = Sum_{k=0..A020914(n-1)-n-2} A325904(k)*binomial(A020914(n-1)-k-2, n-2) for n>1. - Benjamin Lombardo, Oct 18 2019

Two more terms from Jules Renucci (jules.renucci(AT)wanadoo.fr), Nov 02 2005

More terms from T. D. Noe, Sep 11 2006

A109499 Number of closed walks of length n on the complete graph on 5 nodes from a given node.

Original entry on oeis.org

1, 0, 4, 12, 52, 204, 820, 3276, 13108, 52428, 209716, 838860, 3355444, 13421772, 53687092, 214748364, 858993460, 3435973836, 13743895348, 54975581388, 219902325556, 879609302220, 3518437208884, 14073748835532

Offset: 0

Mitch Harris, Jun 30 2005

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Christopher R. Kitching, Henri Kauhanen, Jordan Abbott, Deepthi Gopal, Ricardo Bermúdez-Otero, and Tobias Galla, Estimating transmission noise on networks from stationary local order, arXiv:2405.12023 [cond-mat.stat-mech], 2024. See p. 48.
Index entries for linear recurrences with constant coefficients, signature (3,4).

Cf. A108020 (bisection), A109502.

Cf. A001045, A078008, A097073, A115341, A015518, A054878, A015521 (forms k=4^n-k). - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

a:=[1,0];; for n in [3..30] do a[n]:=3*a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Mar 23 2019

[(4^n + 4*(-1)^n)/5: n in [0..30]]; // Vincenzo Librandi, Aug 12 2011

CoefficientList[Series[(1-3*x)/(1-3*x-4*x^2), {x,0,30}], x] (* or *) LinearRecurrence[{3,4}, {1,0}, 30] (* G. C. Greubel, Dec 30 2017 *)

a(n)=(4^n+4*(-1)^n)/5 \\ Charles R Greathouse IV, Oct 01 2012

[(4^n+4*(-1)^n)/5 for n in (0..30)] # G. C. Greubel, Mar 23 2019

G.f.: (1 - 3*x)/(1 - 3*x - 4*x^2).
a(n) = (4^n + 4*(-1)^n)/5.
a(n+1) = 4*A015521(n). - Paul Curtz, Nov 01 2009
a(n) = 3*a(n-1) + 4*a(n-1). - G. C. Greubel, Dec 30 2017
a(n) = A108020((n - 1) / 2) = 'ccc...c' (n digits) in base 16, for odd n. - Georg Fischer, Mar 23 2019
E.g.f.: (exp(4*x) + 4*exp(-x))/5. - G. C. Greubel, Mar 23 2019

Corrected by Franklin T. Adams-Watters, Sep 18 2006

A139271 a(n) = 2n(4*n-3).

Original entry on oeis.org

0, 2, 20, 54, 104, 170, 252, 350, 464, 594, 740, 902, 1080, 1274, 1484, 1710, 1952, 2210, 2484, 2774, 3080, 3402, 3740, 4094, 4464, 4850, 5252, 5670, 6104, 6554, 7020, 7502, 8000, 8514, 9044, 9590, 10152, 10730, 11324, 11934, 12560, 13202, 13860, 14534, 15224

Offset: 0

Omar E. Pol, Apr 26 2008

Sequence found by reading the line from 0, in the direction 0, 2, ..., in the square spiral whose vertices are the triangular numbers A000217. Opposite numbers to the members of A033585 in the same spiral.
Twice decagonal numbers (or twice 10-gonal numbers). - Omar E. Pol, May 15 2008
a(n) is the number of walks in a cubic lattice of n dimensions that reach the point of origin for the first time after 4 steps. - Shel Kaphan, Mar 20 2023

G. C. Greubel, Table of n, a(n) for n = 0..5000
Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A000217, A014634, A014635, A033585, A033586, A033587, A035008, A051870, A069129, A085250, A139272, A139273, A139274, A139275, A139276, A139278, A139279, A139280, A139281, A139282.
Cf. A001107.
Cf. numbers of the form n*(n*k-k+4)/2 listed in A226488 (this sequence is the case k=16). - Bruno Berselli, Jun 10 2013
Row n=2 of A361397.

Table[8n^2-6n,{n,0,40}] (* or *) LinearRecurrence[{3,-3,1},{0,2,20},50] (* Harvey P. Dale, Sep 26 2016 *)

a(n)=2*n*(4*n-3) \\ Charles R Greathouse IV, Jun 17 2017

a(n) = 8*n^2 - 6*n.
Sequences of the form a(n) = 8*n^2 + c*n have generating functions x{c+8+(8-c)x} / (1-x)^3 and recurrence a(n) = 3a(n-1) - 3a(n-2) + a(n-3). The inverse binomial transform is 0, c+8, 16, 0, 0, ... (0 continued). This applies to A139271-A139278, positive or negative c. - R. J. Mathar, May 12 2008
a(n) = A001107(n)*2. - Omar E. Pol, May 15 2008
a(n) = 16*n + a(n-1) - 14 (with a(0)=0). - Vincenzo Librandi, Aug 03 2010
From G. C. Greubel, Jul 18 2017: (Start)
G.f.: (2*x)*(7*x+1)/(1-x)^3.
E.g.f.: (8*x^2 + 2*x)*exp(x). (End)
Sum_{n>=1} 1/a(n) = Pi/12 + log(2)/2. - Amiram Eldar, Mar 28 2023

Corrected by Harvey P. Dale, Sep 26 2016

A002899 Number of n-step polygons on f.c.c. lattice.

Original entry on oeis.org

1, 0, 12, 48, 540, 4320, 42240, 403200, 4038300, 40958400, 423550512, 4434978240, 46982827584, 502437551616, 5417597053440, 58831951546368, 642874989479580, 7063600894137216, 77991775777488144, 864910651813116480

Offset: 0

N. J. A. Sloane

a(n) is the number of 2 X n matrices with entries from {1,2,3,4}, with (1) second row a (multiset) permutation of the first, and (2) no constant columns. - David Callan, Aug 25 2009

a(n) is the constant coefficient in the expansion of (x + y + z + 1/x + 1/y + 1/z + x/y + y/z + z/x + y/x + z/y + x/z)^n. - Seiichi Manyama, Oct 26 2019

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

Christoph Koutschan, Table of n, a(n) for n = 0..931
David H. Bailey, Jonathan M. Borwein, David Broadhurst and M. L. Glasser, Elliptic integral evaluations of Bessel moments, arXiv:0801.0891 [hep-th], 2008.
C. Domb, On the theory of cooperative phenomena in crystals, Advances in Phys., 9 (1960), 149-361.
Yen Lee Loh, A general method for calculating lattice Green functions on the branch cut, arXiv:1706.03083 [math-ph], 2017.
Index entries for sequences related to f.c.c. lattice

Cf. A002895, A002898.

f[n_] := Sum[ Binomial[n, k]*(-4)^(n - k)*Sum[ Binomial[k, j]^2*Binomial[2k - 2j, k - j]*Binomial[2j, j], {j, 0, k}], {k, 0, n}]; Array[f, 20, 0]

{a(n)=sum(k=0, n, binomial(n, k)*(-4)^(n-k)*sum(j=0, k, binomial(k, j)^2*binomial(2*k-2*j, k-j)*binomial(2*j, j)))};
print(vector(20, n, a(n-1))) \\ David Broadhurst, Feb 06 2008; fixed by Vaclav Kotesovec, Apr 08 2016

G.f.: hypergeom([1/6, 1/3],[1],108*x^2*(4*x+1))^2. - Mark van Hoeij, Oct 29 2011
Recurrence: n^3*a(n) - 2*n*(2*n-1)*(n-1)*a(n-1) - 16*(n-1)*(5*n^2-10*n+6)*a(n-2) - 96*(n-1)*(n-2)*(2*n-3)*a(n-3) = 0. - R. J. Mathar, Dec 10 2013
a(n) ~ 2^(2*n-2) * 3^(n+3/2) / (Pi^(3/2) * n^(3/2)). - Vaclav Kotesovec, Apr 08 2016

More terms from David Broadhurst, Feb 06 2008

A258206 Number of strictly non-overlapping holeless polyhexes of perimeter 2n, counted up to rotations and turning over.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 3, 2, 12, 14, 50, 97, 312, 744, 2291, 6186, 18714, 53793, 162565, 482416, 1467094, 4436536, 13594266, 41640513, 128564463, 397590126, 1236177615, 3852339237, 12053032356, 37802482958, 118936687722, 375079338476

Offset: 1

Antti Karttunen, May 31 2015

Differs from A057779 for the first time at n=12 as here a(12) = 97, one less than A057779(12) because this sequence excludes polyhexes with holes, the smallest which contains six hexagons in a ring, enclosing a hole of one hex, having thus perimeter of 18+6 = 24 (= 2*12) edges.
Differs from A258019 for the first time at n=13 as here a(13) = 312, one less than A258019(13) because this sequence counts only strictly non-overlapping and non-touching polyhex-patterns, while A258019(13) already includes one specimen of helicene-like self-reaching structures.
If one counts these structures by the number of hexagons (instead of perimeter length), one obtains sequence 1, 1, 3, 7, 22, 81, ... (A018190).
a(n) is also the number of 2n-step 2-dimensional closed self-avoiding paths on honeycomb lattice, reduced for symmetry. - Luca Petrone, Jan 08 2016

S. J. Cyvin, J. Brunvoll and B. N. Cyvin, Theory of Coronoid Hydrocarbons, Springer-Verlag, 1991. See sections 4.7 Annulene and 6.5 Annulenes.

Hugo Pfoertner, Illustration of polygons of perimeter <= 20.

Cf. A000228, A057779, A018190, A258019, A258204, A258205, A316193.

(define (A258206 n) (* (/ 1 2) (+ (A258204 n) (A258205 n))))

a(n) = (1/2) * (A258204(n) + A258205(n)).
Other observations. For all n >= 1:
a(n) <= A057779(n).
a(n) <= A258019(n).

a(14)-a(15) from Luca Petrone, Jan 08 2016
a(16)-a(23) from Cyvin, Brunvoll & Cyvin added by Andrey Zabolotskiy, Mar 01 2023
a(24)-a(32) from Bert Dobbelaere, May 12 2025

A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.

Original entry on oeis.org

1, 1, 3, 6, 20, 50, 175, 490, 1764, 5292, 19404, 60984, 226512, 736164, 2760615, 9202050, 34763300, 118195220, 449141836, 1551580888, 5924217936, 20734762776, 79483257308, 281248448936, 1081724803600, 3863302870000, 14901311070000, 53644719852000

Offset: 0

N. J. A. Sloane

Number of n-step walks that start at the origin, constrained to stay in the first octant (0 <= y <= x). (Conjectured) - Benjamin Phillabaum, Mar 11 2011, corrected by Robert Israel, Oct 07 2015
For n >= 1, a(n-1) is the number of Dyck Paths with semilength n having floor((n+2)/2) U's in odd numbered positions. Example: (U is in odd numbered position and u is in even numbered position) Dyck path with n=5, floor ((5+2)/2)=3: UuddUuUddd. - Roger Ford, May 27 2017
The ratio of the number of n-step walks on the octant with an equal number of North steps and South steps to the total number of n-step walks on the octant is A005817(n)/a(n).  For the reduced ratio, if n is divisible by 4 or n-1 is divisible by 4 the ratio is 1:floor(n/4)+1 and for all other values of n the ratio is 2:floor(n/2)+2.  Example n = 4: A005817(4) = 10; EEEE, EEEW, EEWE, EWEE, EWEW, EEWW, ENSE, ENES, ENSW, EENS; a(4) = 20; 10:20 reduces to 1:2. - Roger Ford, Nov 04 2019

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Slides for Séminaire de Combinatoire Ph. Flajolet, Mar 28 2013.
Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech, Hypergeometric expressions for generating functions of walks with small steps in the quarter plane, Eur. J. Comb. 61, 242-275 (2017)
Sergi Elizalde, The degree of symmetry of lattice paths, arXiv:2002.12874 [math.CO], 2020.
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 Column 1 of Figure 5.
Heinrich Niederhausen, A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number of Contacts with the Diagonal, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.3.

See A138350 for a signed version.
Bisections are A000891 and A000888/2.
Cf. A005559, A005560, A005561, A005562, A093768.
Cf. A000108, A005817. Column y=0 of A052174.

[Binomial(n+1, Ceiling(n/2))*Binomial(n, Floor(n/2)) - Binomial(n+1, Ceiling((n-1)/2))*Binomial(n, Floor((n-1)/2)): n in [0..30]]; // Vincenzo Librandi, Sep 30 2015

A:= proc(n,x,y) option remember;
    local j, xpyp, xp,yp, res;
    xpyp:= [[x-1,y],[x+1,y],[x,y-1],[x,y+1]];
    res:= 0;
    for j from 1 to 4 do
      xp:= xpyp[j,1];
      yp:= xpyp[j,2];
      if xp < 0 or xp > yp or xp + yp > n then next fi;
      res:= res + procname(n-1,xp,yp)
    od;
return res
end proc:
A(0,0,0) := 1:
seq(add(add(A(n,x,y), y = x .. n - x), x = 0 .. floor(n/2)), n = 0 .. 50); # Robert Israel, Oct 07 2015

a[n_] := 1/2*Binomial[2*Floor[n/2]+1, Floor[n/2]+1]*CatalanNumber[1/2*(n+Mod[n, 2])]*(Mod[n, 2]+2); Table[a[n]//Abs, {n, 0, 27}] (* Jean-François Alcover, Mar 13 2014 *)

a(n)=binomial(n+1,ceil(n/2))*binomial(n,floor(n/2)) - binomial(n+1,ceil((n-1)/2))*binomial(n,floor((n-1)/2))

from sympy import ceiling as c, binomial
def a(n):
    return binomial(n + 1, c(n/2))*binomial(n, n//2) - binomial(n + 1, c((n - 1)/2))*binomial(n, (n - 1)//2)
print([a(n) for n in range(51)]) # Indranil Ghosh, Jul 02 2017

a(n) = C(n+1, ceiling(n/2))*C(n, floor(n/2)) - C(n+1, ceiling((n-1)/2))*C(n, floor((n-1)/2)). - Paul D. Hanna, Apr 16 2004
G.f.: (1/(4x^2))*((16*x^2-1)*(hypergeom([1/2, 1/2],[1],16*x^2)+2*x*(4*x-1)*hypergeom([3/2, 3/2],[2],16*x^2))-2*x+1). - Mark van Hoeij, Oct 13 2009
E.g.f (conjectured): BesselI(1,2*x)*(BesselI(0,2*x)+BesselI(1,2*x))/x. - Benjamin Phillabaum, Feb 25 2011
Conjecture: (2*n+1)*(n+3)*(n+2)*a(n) - 4*(2*n^2+4*n+3)*a(n-1) - 16*n*(2*n+3)*(n-1)*a(n-2) = 0. - R. J. Mathar, Apr 02 2017
Conjecture: (n+3)*(n+2)*a(n) - 4*(n^2+3*n+1)*a(n-1) + 16*(-n^2+n+1)*a(n-2) + 64*(n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Apr 02 2017
a(n) = Sum_{k=0..floor(n/2)} n!/(k!*k!*(floor(n/2)-k)!*(floor((n+1)/2)-k)!*(k+1)) (conjectured). - Roger Ford, Aug 04 2017
a(n) = A000108(floor((n+1)/2))*A000108(floor(n/2))*(2*(floor(n/2))+1). - Roger Ford, Nov 15 2019
a(n) = Product_{k=3..n} (4*floor((k-1)/2) + 2) / (floor((k+2)/2)). - Roger Ford, Apr 29 2024

A005573 Number of walks on cubic lattice (starting from origin and not going below xy plane).

Original entry on oeis.org

1, 5, 26, 139, 758, 4194, 23460, 132339, 751526, 4290838, 24607628, 141648830, 817952188, 4736107172, 27487711752, 159864676803, 931448227590, 5435879858958, 31769632683132, 185918669183370, 1089302293140564

Offset: 0

N. J. A. Sloane

Binomial transform of A026378, second binomial transform of A001700. - Philippe Deléham, Jan 28 2007

The Hankel transform of [1,1,5,26,139,758,...] is [1,4,15,56,209,...](see A001353). - Philippe Deléham, Apr 13 2007

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 = 0..1000
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch and Jim Brawner, Problem 10795: Three-Dimensional Lattice Walks in the Upper Half-Space, Amer. Math. Monthly, 108 (Dec. 2001), 980.
Rigoberto Flórez, Leandro Junes, and 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, 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.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 97.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (Sqrt((1-2*x)/(1-6*x)) -1)/(2*x) )); // G. C. Greubel, May 02 2019

CoefficientList[Series[(Sqrt[(1-2x)/(1-6x)]-1)/(2x),{x,0,20}],x] (* Harvey P. Dale, Jun 24 2011 *)
a[n_] := 6^n Hypergeometric2F1[1/2, -n, 2, 2/3]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 11 2017 *)

my(x='x+O('x^30)); Vec((sqrt((1-2*x)/(1-6*x)) -1)/(2*x)) \\ G. C. Greubel, May 02 2019

((sqrt((1-2*x)/(1-6*x)) -1)/(2*x)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 02 2019

From Emeric Deutsch, Jan 09 2003; corrected by Roland Bacher: (Start)
a(n) = Sum_{i=0..n} (-1)^i*6^(n-i)*binomial(n, i)*binomial(2*i, i)/(i+1);
g.f. A(x) satisfies: x(1-6x)A^2 + (1-6x)A - 1 = 0. (End)
From Henry Bottomley, Aug 23 2001: (Start)
a(n) = 6*a(n-1) - A005572(n-1).
a(n) = Sum_{j=0..n} 4^(n-j)*binomial(n, floor(n/2))*binomial(n, j). (End)
a(n) = Sum_{k=0..n} binomial(n, k)*binomial(2*k+1, k)*2^(n-k).
a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*Catalan(k)*6^(n-k).
D-finite with recurrence (n+1)*a(n) = (8*n+2)*a(n-1)-(12*n-12)*a(n-2). - Vladeta Jovovic, Jul 16 2004
a(n) = Sum_{k=0..n} A052179(n,k). - Philippe Deléham, Jan 28 2007
Conjecture: a(n)= 6^n * hypergeom([1/2,-n],[2], 2/3). - Benjamin Phillabaum, Feb 20 2011
From Paul Barry, Apr 21 2009: (Start)
G.f.: (sqrt((1-2*x)/(1-6*x)) - 1)/(2*x).
G.f.: 1/(1-5*x-x^2/(1-4*x-x^2/(1-4*x-x^2/(1-4*x-x^2/(1-... (continued fraction). (End)
G.f.: 1/(1 - 4*x - x*(1 - 2*x)/(1 - 2*x - x*(1 - 2*x)/(1 - 2*x - x*(1 - 2*x)/(1 - 2*x - x*(1 - 2*x)/(1...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Jul 02 2010
a(n) ~ 6^(n+1/2)/sqrt(Pi*n). - Vaclav Kotesovec, Oct 05 2012
G.f.: G(0)/(2*x) - 1/(2*x), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-2*x) - 2*x*(1-2*x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-2*x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 24 2013
a(n) = 2^n*hypergeom([-n, 3/2], [2], -2). - Peter Luschny, Apr 26 2016
E.g.f.: exp(4*x)*(BesselI(0,2*x) + BesselI(1,2*x)). - Ilya Gutkovskiy, Sep 20 2017

More terms from Henry Bottomley, Aug 23 2001

cp's OEIS Frontend

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A037245 Number of unrooted self-avoiding walks of n steps on square lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A054879 Closed walks of length 2n along the edges of a cube based at a vertex.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A100982 Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

PARI

Formula

Extensions

A109499 Number of closed walks of length n on the complete graph on 5 nodes from a given node.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A139271 a(n) = 2*n*(4*n-3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A002899 Number of n-step polygons on f.c.c. lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A139271 a(n) = 2n(4*n-3).