|
| |
|
|
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.
|
|
9
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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).
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.
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.
A364350 counts combination-free strict partitions, complement A364913.
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
