A306293 -id:A306293 - cp's OEIS frontend

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

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

A306306 Number of binary words of length n such that in every prefix and in every suffix the difference between the number of 1's and the number of 0's is in the interval [-2,3].

Original entry on oeis.org

1, 2, 4, 7, 12, 21, 35, 62, 102, 184, 299, 551, 882, 1666, 2615, 5085, 7782, 15658, 23219, 48603, 69402, 151945, 207695, 477987, 622062, 1511741, 1864139, 4803125, 5588322, 15319484, 16756775, 49018968, 50253942, 157270414, 150729059, 505697248, 452121642

Offset: 0

Alois P. Heinz, Feb 05 2019

			a(3) = 7: 001, 010, 011, 100, 101, 110, 111.
a(4) = 12: 0010, 0011, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110.
a(5) = 21: 00101, 00110, 00111, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101.
a(6) = 35: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 010111, 011001, 011010, 011011, 011100, 011101, 011110, 100011, 100101, 100110, 100111, 101001, 101010, 101011, 101100, 101101, 101110, 110001, 110010, 110011, 110100, 110101, 110110, 111001, 111010.
a(7) = 62: 0010101, 0010110, 0010111, ..., 1110010, 1110011, 1110100, 1110101.

Alois P. Heinz, Table of n, a(n) for n = 0..3912
Index entries for linear recurrences with constant coefficients, signature (0,14,0,-81,0,250,0,-443,0,451,0,-249,0,65,0,-6)

Cf. A306293, A306315.

G.f.: -(x^16 -10*x^14 +31*x^12 +54*x^11 -27*x^10 -153*x^9 -27*x^8 +165*x^7 +59*x^6 -85*x^5 -37*x^4 +21*x^3 +10*x^2 -2*x-1) / ((x-1) *(x+1) *(3*x^2-1) *(2*x^2-1) *(x^2+x-1) *(x^2-x-1) *(x^3-2*x^2-x+1) *(x^3+2*x^2-x-1)).

a(n) >= A306293(n).

A306315 Number of binary words of length n such that the difference between the number of 1's and the number of 0's is in the interval [-2,3] for every prefix and in the interval [-3,2] for every suffix.

Original entry on oeis.org

1, 2, 4, 6, 12, 18, 35, 54, 103, 162, 307, 486, 926, 1458, 2823, 4374, 8688, 13122, 26962, 39366, 84285, 118098, 265147, 354294, 838625, 1062882, 2664636, 3188646, 8499263, 9565938, 27197074, 28697814, 87261592, 86093442, 280596321, 258280326, 903916589

Offset: 0

Alois P. Heinz, Feb 06 2019

			a(3) = 6: 001, 010, 011, 100, 101, 110.
a(4) = 12: 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101, 1110.
a(5) = 18: 00101, 00110, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 11000, 11001, 11010, 11100.
a(6) = 35: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 011000, 011001, 011010, 011100, 100010, 100011, 100100, 100101, 100110, 101000, 101001, 101010, 101011, 101100, 101101, 101110, 110001, 110010, 110011, 110100, 110101, 110110, 111000, 111001, 111010.

Alois P. Heinz, Table of n, a(n) for n = 0..3911
Index entries for linear recurrences with constant coefficients, signature (0,11,0,-46,0,90,0,-81,0,28,0,-3)

Odd bisection gives A008776.

Cf. A306293, A306306.

LinearRecurrence[{0,11,0,-46,0,90,0,-81,0,28,0,-3},{1,2,4,6,12,18,35,54,103,162,307,486},40] (* Harvey P. Dale, Sep 17 2019 *)

G.f.: -(2*x^11-18*x^9+9*x^8+48*x^7+3*x^6-44*x^5-14*x^4+16*x^3+7*x^2-2*x-1) / ((3*x^2-1) *(x^2+x-1) *(x^2-x-1) *(x^3-2*x^2-x+1) *(x^3+2*x^2-x-1)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A306306 Number of binary words of length n such that in every prefix and in every suffix the difference between the number of 1's and the number of 0's is in the interval [-2,3].

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A306315 Number of binary words of length n such that the difference between the number of 1's and the number of 0's is in the interval [-2,3] for every prefix and in the interval [-3,2] for every suffix.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula