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

A365381 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} with a subset summing to k.

Original entry on oeis.org

1, 2, 1, 4, 2, 2, 1, 8, 4, 4, 5, 2, 2, 1, 16, 8, 8, 10, 10, 7, 5, 5, 2, 2, 1, 32, 16, 16, 20, 20, 23, 15, 15, 12, 12, 8, 5, 5, 2, 2, 1, 64, 32, 32, 40, 40, 46, 47, 38, 33, 35, 29, 28, 21, 17, 14, 13, 8, 5, 5, 2, 2, 1, 128, 64, 64, 80, 80, 92, 94, 102, 79, 82, 76, 75, 68, 64, 53, 48, 43, 34, 33, 23, 19, 15, 13, 8, 5, 5, 2, 2, 1

Offset: 0

Gus Wiseman, Sep 08 2023

Row lengths are A000124(n) = 1 + n*(n+1)/2.

			Triangle begins:
   1
   2  1
   4  2  2  1
   8  4  4  5  2  2  1
  16  8  8 10 10  7  5  5  2  2  1
  32 16 16 20 20 23 15 15 12 12  8  5  5  2  2  1
  64 32 32 40 40 46 47 38 33 35 29 28 21 17 14 13  8  5  5  2  2  1
Array begins:
     k=0   k=1  k=2  k=3  k=4  k=5  k=6  k=7  k=8  k=9
-------------------------------------------------------
n=0:  1
n=1:  2     1
n=2:  4     2    2    1
n=3:  8     4    4    5    2    2    1
n=4:  16    8    8    10   10   7    5    5    2    2
n=5:  32    16   16   20   20   23   15   15   12   12
n=6:  64    32   32   40   40   46   47   38   33   35
n=7:  128   64   64   80   80   92   94   102  79   82
n=8:  256   128  128  160  160  184  188  204  207  184
n=9:  512   256  256  320  320  368  376  408  414  440
The T(5,8) = 12 subsets are:
  {3,5}  {1,2,5}  {1,2,3,4}  {1,2,3,4,5}
         {1,3,4}  {1,2,3,5}
         {1,3,5}  {1,2,4,5}
         {2,3,5}  {1,3,4,5}
         {3,4,5}  {2,3,4,5}

Row lengths are A000124 = number of distinct sums of subsets of {1..n}.
Central column/main diagonal is A365376.
A000009 counts sets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A365046 counts combination-full subsets, differences of A364914.
Cf. A007865, A085489, A093971, A103580, A131577, A151897, A326080, A364272, A364534, A365073, A365377, A365380.

Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],k]&]],{n,0,8},{k,0,n*(n+1)/2}]

A365541 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.

Original entry on oeis.org

1, 2, 2, 2, 4, 4, 7, 4, 4, 8, 8, 14, 14, 14, 8, 8, 16, 16, 28, 28, 37, 28, 28, 16, 16, 32, 32, 56, 56, 74, 74, 74, 56, 56, 32, 32, 64, 64, 112, 112, 148, 148, 175, 148, 148, 112, 112, 64, 64, 128, 128, 224, 224, 296, 296, 350, 350, 350, 296, 296, 224, 224, 128, 128

Offset: 2

Gus Wiseman, Sep 15 2023

Rows are palindromic.

			Triangle begins:
    1
    2    2    2
    4    4    7    4    4
    8    8   14   14   14    8    8
   16   16   28   28   37   28   28   16   16
   32   32   56   56   74   74   74   56   56   32   32
Row n = 4 counts the following subsets:
  {1,2}      {1,3}      {1,4}      {2,4}      {3,4}
  {1,2,3}    {1,2,3}    {2,3}      {1,2,4}    {1,3,4}
  {1,2,4}    {1,3,4}    {1,2,3}    {2,3,4}    {2,3,4}
  {1,2,3,4}  {1,2,3,4}  {1,2,4}    {1,2,3,4}  {1,2,3,4}
                        {1,3,4}
                        {2,3,4}
                        {1,2,3,4}

Row lengths are A005408.
The case counting only length-2 subsets is A008967.
Column k = n + 1 appears to be A167762.
The version for all subsets (instead of just pairs) is A365381.
Column k = n is A365544.
A000009 counts subsets summing to n.
A007865/A085489/A151897 count certain types of sum-free subsets.
A046663 counts partitions with no submultiset summing to k, strict A365663.
A093971/A088809/A364534 count certain types of sum-full subsets.
A365543 counts partitions with a submultiset summing to k, strict A365661.
Cf. A068911, A095944, A238628, A288728, A326083, A364272, A365376, A365377.

Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#,{2}],k]&]], {n,2,11}, {k,3,2n-1}]

A367217 Number of subsets of {1..n} whose cardinality is not equal to the sum of any subset.

Original entry on oeis.org

0, 0, 1, 3, 6, 12, 24, 46, 87, 164, 308, 577, 1080, 2021, 3779, 7058, 13166, 24533, 45674, 84978, 158026, 293737, 545747, 1013467, 1881032, 3489303, 6468910, 11985988, 22195905, 41080751, 75994642, 140514019, 259693004, 479749492, 885910870, 1635281386

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

			The a(2) = 1 through a(5) = 12 subsets:
  {2}  {2}    {2}    {2}
       {3}    {3}    {3}
       {1,3}  {4}    {4}
              {1,3}  {5}
              {1,4}  {1,3}
              {3,4}  {1,4}
                     {1,5}
                     {3,4}
                     {3,5}
                     {4,5}
                     {1,4,5}
                     {2,4,5}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217*   A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A229816 counts partitions whose length is not a part, complement A002865.
A007865/A085489/A151897 count certain types of sum-free subsets.
A088809/A093971/A364534 count certain types of sum-full subsets.
A124506 appears to count combination-free subsets, differences of A326083.
A237667 counts sum-free partitions, ranks A364531.
Triangles:
A046663 counts partitions of n without a subset-sum k, strict A365663.
A365381 counts sets with a subset summing to k, without A366320.
A365541 counts sets containing two distinct elements summing to k.
Cf. A068911, A103580, A240861, A288728, A326080, A326083, A364346, A364349, A365046, A365376, A365377.

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

a(n) = 2^n - A367216(n). - Chai Wah Wu, Nov 14 2023

a(16)-a(28) from Chai Wah Wu, Nov 14 2023

a(29)-a(35) from Max Alekseyev, Feb 25 2025

A367223 Number of subsets of {1..n} whose cardinality cannot be written as a nonnegative linear combination of the elements.

Original entry on oeis.org

0, 0, 1, 2, 4, 8, 15, 27, 49, 90, 165, 301, 548, 998, 1819, 3316, 6040, 10986, 19959, 36253, 65904, 119986, 218796, 399461, 729752, 1333162, 2434411, 4441954, 8097478, 14746715, 26830230, 48773790, 88605927, 160900978, 292140427, 530487359, 963610200, 1751171679, 3183997509

Offset: 0

Gus Wiseman, Nov 14 2023

nonn

			3 cannot be written as a nonnegative linear combination of 2, 4, and 5, so {2,4,5} is counted under a(6).
The a(2) = 1 through a(6) = 15 subsets:
  {2}  {2}  {2}    {2}      {2}
       {3}  {3}    {3}      {3}
            {4}    {4}      {4}
            {3,4}  {5}      {5}
                   {3,4}    {6}
                   {3,5}    {3,4}
                   {4,5}    {3,5}
                   {2,4,5}  {3,6}
                            {4,5}
                            {4,6}
                            {5,6}
                            {2,4,5}
                            {2,4,6}
                            {2,5,6}
                            {4,5,6}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217    A367222    A367223*
  ranks:       A367224    A367225    A367226    A367227
A007865/A085489/A151897 count certain types of sum-free subsets.
A088809/A093971/A364534 count certain types of sum-full subsets.
A124506 appears to count combination-free subsets, differences of A326083.
A365046 counts combination-full subsets, differences of A364914.
Triangles:
A116861 counts positive linear combinations of strict partitions of k.
A364916 counts linear combinations of strict partitions of k.
A366320 counts subsets without a subset summing to k, with A365381.
Cf. A068911, A088314, A103580, A237667, A326020, A326080, A364350, A365073, A365312, A365377, A365380.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]], combs[Length[#],Union[#]]=={}&]], {n,0,10}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A367223(n):
    c, mlist = 0, []
    for m in range(1,n+1):
        t = set()
        for p in partitions(m):
            t.add(tuple(sorted(p.keys())))
        mlist.append([set(d) for d in t])
    for k in range(1,n+1):
        for w in combinations(range(1,n+1),k):
            ws = set(w)
            for s in mlist[k-1]:
                if s <= ws:
                    break
            else:
                c += 1
    return c # Chai Wah Wu, Nov 16 2023

a(n) = 2^n - A367222(n).

a(14)-a(33) from Chai Wah Wu, Nov 15 2023

a(34)-a(38) from Max Alekseyev, Feb 25 2025

A365376 Number of subsets of {1..n} with a subset summing to n.

Original entry on oeis.org

1, 1, 2, 5, 10, 23, 47, 102, 207, 440, 890, 1847, 3730, 7648, 15400, 31332, 62922, 127234, 255374, 514269, 1030809, 2071344, 4148707, 8321937, 16660755, 33384685, 66812942, 133789638, 267685113, 535784667, 1071878216, 2144762139, 4290261840, 8583175092, 17168208940, 34342860713

Offset: 0

Gus Wiseman, Sep 08 2023

nonn

			The a(1) = 1 through a(4) = 10 sets:
  {1}  {2}    {3}      {4}
       {1,2}  {1,2}    {1,3}
              {1,3}    {1,4}
              {2,3}    {2,4}
              {1,2,3}  {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}

The case containing n is counted by A131577.
The version with re-usable parts is A365073.
The complement is counted by A365377.
The complement w/ re-usable parts is A365380.
Main diagonal of A365381.
A000009 counts sets summing to n, multisets A000041.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237668, A326080, A364534.

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

isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(1)));
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023

from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365376(n):
    if n == 0: return 1
    nset = set(range(1,n+1))
    s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
    for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
        if sum(a) >= n:
            aset = set(a)
            for p in s:
                if p.issubset(aset):
                    c += 1
                    break
    return c # Chai Wah Wu, Sep 09 2023

a(n) = 2^n-A365377(n). - Chai Wah Wu, Sep 09 2023

a(16)-a(25) from Michel Marcus, Sep 09 2023
a(26)-a(32) from Chai Wah Wu, Sep 09 2023
a(33)-a(35) from Chai Wah Wu, Sep 10 2023

A366320 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 3, 6, 6, 7, 8, 8, 6, 6, 9, 11, 11, 14, 14, 15, 16, 16, 12, 12, 9, 17, 17, 20, 20, 24, 27, 27, 30, 30, 31, 32, 32, 24, 24, 18, 17, 26, 31, 29, 35, 36, 43, 47, 50, 51, 56, 59, 59, 62, 62, 63

Offset: 1

Gus Wiseman, Oct 12 2023

			Triangle begins:
   1
   2  2  3
   4  4  3  6  6  7
   8  8  6  6  9 11 11 14 14 15
  16 16 12 12  9 17 17 20 20 24 27 27 30 30 31
  32 32 24 24 18 17 26 31 29 35 36 43 47 50 51 56 59 59 62 62 63
Row n = 3 counts the following subsets:
  {}     {}     {}   {}     {}     {}
  {2}    {1}    {1}  {1}    {1}    {1}
  {3}    {3}    {2}  {2}    {2}    {2}
  {2,3}  {1,3}       {3}    {3}    {3}
                     {1,2}  {1,2}  {1,2}
                     {2,3}  {1,3}  {1,3}
                                   {2,3}

Row lengths are A000217.
The diagonal T(n,n) is A365377, complement A365376.
The complement is counted by A365381.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 counts combination-free subsets, differences of A326083.
A365046 counts combination-full subsets, differences of A364914.
Cf. A007865, A085489, A093971, A103580, A151897, A326080, A364534, A365073, A365380.

Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#],k]&]],{n,8},{k,n*(n+1)/2}]

A365544 Number of subsets of {1..n} containing two distinct elements summing to n.

Original entry on oeis.org

0, 0, 0, 2, 4, 14, 28, 74, 148, 350, 700, 1562, 3124, 6734, 13468, 28394, 56788, 117950, 235900, 484922, 969844, 1979054, 3958108, 8034314, 16068628, 32491550, 64983100, 131029082, 262058164, 527304974, 1054609948, 2118785834, 4237571668, 8503841150, 17007682300

Offset: 0

Gus Wiseman, Sep 20 2023

			The a(1) = 0 through a(5) = 14 subsets:
  .  .  {1,2}    {1,3}      {1,4}
        {1,2,3}  {1,2,3}    {2,3}
                 {1,3,4}    {1,2,3}
                 {1,2,3,4}  {1,2,4}
                            {1,3,4}
                            {1,4,5}
                            {2,3,4}
                            {2,3,5}
                            {1,2,3,4}
                            {1,2,3,5}
                            {1,2,4,5}
                            {1,3,4,5}
                            {2,3,4,5}
                            {1,2,3,4,5}

Index entries for linear recurrences with constant coefficients, signature (2,3,-6).

For strict partitions we have A140106 shifted left.
The version for partitions is A004526.
The complement is counted by A068911.
For all subsets of elements we have A365376.
Main diagonal k = n of A365541.
A000009 counts subsets summing to n.
A007865/A085489/A151897 count certain types of sum-free subsets.
A093971/A088809/A364534 count certain types of sum-full subsets.
A365381 counts subsets with a subset summing to k.
Cf. A008967, A095944, A167762, A238628, A288728, A326083, A364272, A365377.

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

def A365544(n): return (1<>1)<<1 if n&1 else 3**(n-1>>1)<<2) if n else 0 # Chai Wah Wu, Aug 30 2024

a(n) = 2^n - A068911(n).
From Alois P. Heinz, Aug 30 2024: (Start)
G.f.: 2*x^3/((2*x-1)*(3*x^2-1)).
a(n) = 2 * A167762(n-1) for n>=1. (End)

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

A070880 Consider the 2^(n-1)-1 nonempty subsets S of {1, 2, ..., n-1}; a(n) gives number of such S for which it is impossible to partition n into parts from S such that each s in S is used at least once.

Original entry on oeis.org

0, 0, 1, 3, 10, 22, 52, 110, 234, 482, 987, 1997, 4035, 8113, 16288, 32644, 65388, 130886, 261922, 524013, 1048250, 2096752, 4193831, 8388033, 16776543, 33553621, 67107918, 134216596, 268434139, 536869354, 1073740011, 2147481510, 4294964833, 8589931699

Offset: 1

Naohiro Nomoto, Nov 16 2003

Also the number of nonempty subsets of {1..n-1} that cannot be linearly combined using all positive coefficients to obtain n. - Gus Wiseman, Sep 10 2023

			a(4)=3 because there are three different subsets S of {1,2,3} satisfying the condition: {3}, {2,3} & {1,2,3}. For the other subsets S, such as {1,2}, there is a partition of 4 which uses them all (such as 4 = 1+1+2).
From _Gus Wiseman_, Sep 10 2023: (Start)
The a(6) = 22 subsets:
  {4}  {2,3}  {1,2,4}  {1,2,3,4}  {1,2,3,4,5}
  {5}  {2,5}  {1,2,5}  {1,2,3,5}
       {3,4}  {1,3,4}  {1,2,4,5}
       {3,5}  {1,3,5}  {1,3,4,5}
       {4,5}  {1,4,5}  {2,3,4,5}
              {2,3,4}
              {2,3,5}
              {2,4,5}
              {3,4,5}
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..100

For sets with sum < n instead of maximum < n we have A088528.
The complement is counted by A365042, including empty set A088314.
Allowing empty sets gives A365045, nonnegative version apparently A124506.
Without re-usable parts we have A365377(n) - 1.
For nonnegative (instead of positive) coefficients we have A365380(n) - 1.
A326083 counts combination-free subsets, complement A364914.
A364350 counts combination-free strict partitions, complement A364913.
Cf. A007865, A085489, A093971, A151897, A326020, A326080, A364534, A365044.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n-1]]], combp[n,#]=={}&]],{n,7}] (* Gus Wiseman, Sep 10 2023 *)

from sympy.utilities.iterables import partitions
def A070880(n): return (1<Chai Wah Wu, Sep 10 2023

a(n) = 2^(n-1) - A088314(n). - Charlie Neder, Feb 08 2019

a(n) = A365045(n) - 1. - Gus Wiseman, Sep 10 2023

Edited by N. J. A. Sloane, Sep 09 2017

a(20)-a(34) from Alois P. Heinz, Feb 08 2019

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

A365381 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} with a subset summing to k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A365541 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367217 Number of subsets of {1..n} whose cardinality is not equal to the sum of any subset.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A367223 Number of subsets of {1..n} whose cardinality cannot be written as a nonnegative linear combination of the elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A365376 Number of subsets of {1..n} with a subset summing to n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A366320 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A365544 Number of subsets of {1..n} containing two distinct elements summing to n.

Views

Author

Keywords

Examples