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,4

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

Links

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

Formula

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

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

Example

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)

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

Prog

(Python)
from sympy.utilities.iterables import partitions
def A070880(n): return (1<<n-1)-len({tuple(sorted(set(p))) for p in partitions(n)}) # Chai Wah Wu, Sep 10 2023

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.

Sequence in context: A294414 A299336 A222629 * A321335 A171686 A027164

Adjacent sequences: A070877 A070878 A070879 * A070881 A070882 A070883

Keyword

easy,nonn

Author

Naohiro Nomoto, Nov 16 2003

Extensions

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

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

Status

approved