OFFSET
0,2
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}
The complement is counted by A365544.
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.
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).
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).
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
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
EXAMPLE
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
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 *)
PROG
(PARI) a(n)=[4, 6][n%2+1]*3^(n\2)\3 \\ Charles R Greathouse IV, Feb 26 2016
(Magma) [Floor((5-(-1)^n)*3^Floor(n/2)/3): n in [0..40]]; // Bruno Berselli, Feb 26 2016, after Charles R Greathouse IV
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Henry Bottomley, Mar 06 2002
STATUS
approved