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

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

Author

Henry Bottomley, Mar 06 2002

Keywords

• nonn
• easy
• walk

Comments

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)

Examples

			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
		

Links

• 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).

Crossrefs

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.

Programs

Magma

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

Maple

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

Mathematica

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 *)

PARI

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

Python

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

Formula

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