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

%I #107 Aug 31 2024 08:33:10

%S 1,2,4,6,12,18,36,54,108,162,324,486,972,1458,2916,4374,8748,13122,

%T 26244,39366,78732,118098,236196,354294,708588,1062882,2125764,

%U 3188646,6377292,9565938,19131876,28697814,57395628,86093442,172186884,258280326,516560652

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

%C From _Johannes W. Meijer_, May 29 2010: (Start)

%C 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).

%C Counts all paths of length n, n >= 0, starting at the third node on the path graph P_5, see the Maple program. (End)

%C From _Alec Jones_, Feb 25 2016: (Start)

%C 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:

%C 1 ... 1 1 ... 1 4 1 4 6 ... 1 4 6 1 4 6 ... and so on.

%C 1 ... 1 2 1 2 ... 1 2 1 2 12 ... 1 2 12 18 (End)

%C From _Gus Wiseman_, Oct 06 2023: (Start)

%C 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:

%C {} {} {} {} {}

%C {1} {1} {1} {1}

%C {2} {2} {2}

%C {1,2} {3} {3}

%C {1,3} {4}

%C {2,3} {1,2}

%C {1,4}

%C {2,3}

%C {2,4}

%C {3,4}

%C {1,2,4}

%C {2,3,4}

%C For n+1 instead of n we have A038754, complement A167762.

%C Including twins gives A117855, complement A366131.

%C The complement is counted by A365544.

%C For all subsets (not just pairs) we have A365377, complement A365376. (End)

%H Alois P. Heinz, <a href="/A068911/b068911.txt">Table of n, a(n) for n = 0..4191</a>

%H F. Javier de Vega, <a href="https://arxiv.org/abs/2003.13378">An extension of Furstenberg's theorem of the infinitude of primes</a>, arXiv:2003.13378 [math.NT], 2020.

%H Stoyan Dimitrov, <a href="https://arxiv.org/abs/2103.04332">Sorting by shuffling methods and a queue</a>, arXiv:2103.04332 [math.CO], 2021.

%H Robert Dorward et al., <a href="https://arxiv.org/abs/1508.07531">A Generalization of Zeckendorf's Theorem via Circumscribed m-gons</a>, arXiv:1508.07531 [math.NT], 2015. See Example 1.3 p. 4.

%H Noam D. Elkies, <a href="https://arxiv.org/abs/math/0508645">New Directions in Enumerative Chess Problems</a>, arXiv:math/0508645 [math.CO], 2005; The Electronic Journal of Combinatorics, 11 (2), 2004-2005.

%H D. Panario, M. Sahin, Q. Wang, and W. Webb, <a href="http://dx.doi.org/10.1016/j.amc.2014.05.108">General conditional recurrences</a>, Applied Mathematics and Computation, Volume 243, Sep 15 2014, Pages 220-231.

%H Noriaki Sannomiya, H. Katsura, and Y. Nakayama, <a href="http://arxiv.org/abs/1612.02285">Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion</a>, arXiv preprint arXiv:1612.02285 [cond-mat.str-el], 2016-2017. See Table I, line 3.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (0,3).

%F 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.

%F 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).

%F 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. - _Paul Barry_, Feb 17 2004

%F a(n) = 2^((3 + (-1)^n)/2)*3^((2*n - 3 - (-1)^n)/4) - ((1 - (-1)^(2^n)))/6. - _Luce ETIENNE_, Aug 30 2014

%F 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

%F 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

%F E.g.f.: (4*cosh(sqrt(3)*x) + 2*sqrt(3)*sinh(sqrt(3)*x) - 1)/3. - _Stefano Spezia_, Feb 17 2022

%e 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

%p 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

%p # second Maple program:

%p a:= proc(n) a(n):= `if`(n<2, n+1, (4-irem(n, 2))/2*a(n-1)) end:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Feb 03 2019

%t Join[{1},Transpose[NestList[{Last[#],3First[#]}&,{2,4},40]][[1]]] (* _Harvey P. Dale_, Oct 24 2011 *)

%t Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#,{2}],n]&]],{n,0,15}] (* _Gus Wiseman_, Oct 06 2023 *)

%o (PARI) a(n)=[4,6][n%2+1]*3^(n\2)\3 \\ _Charles R Greathouse IV_, Feb 26 2016

%o (Magma) [Floor((5-(-1)^n)*3^Floor(n/2)/3): n in [0..40]]; // _Bruno Berselli_, Feb 26 2016, after _Charles R Greathouse IV_

%o (Python)

%o 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

%Y Cf. A000007, A016116 (without initial term), A068912, A068913 for similar.

%Y Equals A060647(n-1)+1.

%Y Cf. also A028495, A038754, A048328, A078038, A124302, A306293.

%Y First differences are A117855.

%Y Cf. A004526, A004737, A008967, A046663, A088809, A365376, A365377, A365381, A365541, A365544, A366130.

%K nonn,easy

%O 0,2

%A _Henry Bottomley_, Mar 06 2002