A366131 -id:A366131 - 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

A117855 Number of nonzero palindromes of length n (in base 3).

Original entry on oeis.org

2, 2, 6, 6, 18, 18, 54, 54, 162, 162, 486, 486, 1458, 1458, 4374, 4374, 13122, 13122, 39366, 39366, 118098, 118098, 354294, 354294, 1062882, 1062882, 3188646, 3188646, 9565938, 9565938, 28697814, 28697814, 86093442, 86093442, 258280326, 258280326, 774840978

Offset: 1

Martin Renner, May 02 2006

See A225367 for the sequence that counts all base 3 palindromes, including 0 (and thus also the number of n-digit terms in A006072). -- A nonzero palindrome of length L=2k-1 or of length L=2k is determined by the first k digits, which then determine the last k digits by symmetry. Since the first digit cannot be 0, there are 2*3^(k-1) possibilities. - M. F. Hasler, May 05 2013
From Gus Wiseman, Oct 18 2023: (Start)
Also the number of subsets of {1..n} with n not the sum of two subset elements (possibly the same). For example, the a(0) = 1 through a(4) = 6 subsets are:
  {}  {}   {}   {}     {}
      {1}  {2}  {1}    {1}
                {2}    {3}
                {3}    {4}
                {1,3}  {1,4}
                {2,3}  {3,4}
For subsets with no subset summing to n we have A365377.
Requiring pairs to be distinct gives A068911, complement A365544.
The complement is counted by A366131.
(End) [Edited by Peter Munn, Nov 22 2023]

			The a(3)=6 palindromes of length 3 are: 101, 111, 121, 202, 212, and 222. - _M. F. Hasler_, May 05 2013

Index entries for linear recurrences with constant coefficients, signature (0,3).

Cf. A050683 and A070252.
Bisections are both A025192.
A093971/A088809/A364534 count certain types of sum-full subsets.
A108411 lists powers of 3 repeated, complement A167936.
Cf. A004526, A004737, A008967, A038754, A046663, A167762, A365376, A366130.

With[{c=NestList[3#&,2,20]},Riffle[c,c]] (* Harvey P. Dale, Mar 25 2018 *)
Table[Length[Select[Subsets[Range[n]],!MemberQ[Total/@Tuples[#,2],n]&]],{n,0,10}] (* Gus Wiseman, Oct 18 2023 *)

A117855(n)=2*3^((n-1)\2) \\ - M. F. Hasler, May 05 2013

def A117855(n): return 3**(n-1>>1)<<1 # Chai Wah Wu, Oct 28 2024

a(n) = 2*3^floor((n-1)/2).
a(n) = 2*A108411(n-1).
From Colin Barker, Feb 15 2013: (Start)
a(n) = 3*a(n-2).
G.f.: -2*x*(x+1)/(3*x^2-1). (End)

More terms from Colin Barker, Feb 15 2013

A367396 Number of subsets of {1..n} whose cardinality is the sum of two distinct elements.

Original entry on oeis.org

0, 0, 0, 1, 3, 7, 17, 40, 90, 199, 435, 939, 2007, 4258, 8976, 18817, 39263, 81595, 168969, 348820, 718134, 1474863, 3022407, 6181687, 12621135, 25727686, 52369508, 106460521, 216162987, 438431215, 888359841, 1798371648, 3637518354, 7351824439, 14848255803

Offset: 0

Gus Wiseman, Nov 21 2023

nonn

			The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is not counted under a(8).
The a(0) = 0 through a(6) = 17 subsets:
  .  .  .  {1,2,3}  {1,2,3}    {1,2,3}      {1,2,3}
                    {1,2,4}    {1,2,4}      {1,2,4}
                    {1,2,3,4}  {1,2,5}      {1,2,5}
                               {1,2,3,4}    {1,2,6}
                               {1,2,3,5}    {1,2,3,4}
                               {1,3,4,5}    {1,2,3,5}
                               {1,2,3,4,5}  {1,2,3,6}
                                            {1,3,4,5}
                                            {1,3,4,6}
                                            {1,3,5,6}
                                            {1,2,3,4,5}
                                            {1,2,3,4,6}
                                            {1,2,3,5,6}
                                            {1,2,4,5,6}
                                            {1,3,4,5,6}
                                            {2,3,4,5,6}
                                            {1,2,3,4,5,6}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396*  A367400
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A002865 counts partitions whose length is a part, complement A229816.
A364534 counts sum-full subsets.
A088809 and A093971 count subsets containing semi-sums.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A236912, A237113, A237667, A237668, A304792, A363225, A364272, A365658, A366131, A366740.

Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#,{2}],Length[#]]&]],{n,0,10}]

from itertools import combinations
def A367396(n): return sum(1 for k in range(3,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if any({a,k-a}<=w for a in range(1,k+1>>1))) # Chai Wah Wu, Nov 21 2023

Conjectures from Chai Wah Wu, Nov 21 2023: (Start)
a(n) = 4*a(n-1) - 5*a(n-2) + 4*a(n-3) - 5*a(n-4) + 2*a(n-5) for n > 4.
G.f.: x^3*(x - 1)/((2*x - 1)*(x^4 - 2*x^3 + x^2 - 2*x + 1)). (End)

a(18)-a(33) from Chai Wah Wu, Nov 21 2023

a(34) from Paul Muljadi, Nov 24 2023

A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.

Original entry on oeis.org

1, 2, 4, 7, 13, 25, 47, 88, 166, 313, 589, 1109, 2089, 3934, 7408, 13951, 26273, 49477, 93175, 175468, 330442, 622289, 1171897, 2206921, 4156081, 7826746, 14739356, 27757207, 52272469, 98439697, 185381983, 349112000, 657448942, 1238110153

Offset: 0

Gus Wiseman, Nov 21 2023

			The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is counted under a(8).
The a(0) = 1 through a(4) = 13 subsets:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,2}  {4}
                  {1,3}  {1,2}
                  {2,3}  {1,3}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,3,4}
                         {2,3,4}

The version containing n appears to be A112575.
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400*
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A002865 counts partitions whose length is a part, complement A229816.
A364534 counts sum-full subsets.
A088809 and A093971 count subsets containing semi-sums.
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A237113, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366131, A366740.

Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#, {2}], Length[#]]&]], {n,0,10}]

from itertools import combinations
def A367400(n): return (n*(n+1)>>1)+1+sum(1 for k in range(3,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if not any({a,k-a}<=w for a in range(1,k+1>>1))) # Chai Wah Wu, Nov 21 2023

Conjectures from Chai Wah Wu, Nov 21 2023: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n > 3.
G.f.: (-x^3 + x^2 + 1)/(x^4 - 2*x^3 + x^2 - 2*x + 1). (End)

a(18)-a(33) from Chai Wah Wu, Nov 21 2023

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

A117855 Number of nonzero palindromes of length n (in base 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A367396 Number of subsets of {1..n} whose cardinality is the sum of two distinct elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions