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.

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

Author

Naohiro Nomoto, Nov 16 2003

Keywords

• easy
• nonn

Comments

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

Examples

			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)
		

Links

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

Crossrefs

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.

Programs

Mathematica

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 *)

Python

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

Formula

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

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

Extensions

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

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