login
A364915
Number of integer partitions of n such that no distinct part can be written as a nonnegative linear combination of other distinct parts.
21
1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 12, 10, 16, 16, 19, 21, 29, 25, 37, 35, 44, 46, 60, 55, 75, 71, 90, 90, 114, 110, 140, 138, 167, 163, 217, 201, 248, 241, 298, 303, 359, 355, 425, 422, 520, 496, 594, 603, 715, 706, 834, 826, 968, 972, 1153, 1147, 1334, 1315, 1530
OFFSET
0,3
FORMULA
a(n) = A000041(n) - A365068(n).
EXAMPLE
The a(1) = 1 through a(10) = 8 partitions (A=10):
1 2 3 4 5 6 7 8 9 A
11 111 22 32 33 43 44 54 55
1111 11111 222 52 53 72 64
111111 322 332 333 73
1111111 2222 522 433
11111111 3222 3322
111111111 22222
1111111111
The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is counted under a(12).
The partition (6,4,3,2) has 6=4+2, or 6=3+3, or 6=2+2+2, or 4=2+2, so is not counted under a(15).
MATHEMATICA
combs[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 0, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n], Function[ptn, !Or@@Table[combs[ptn[[k]], Delete[ptn, k]]!={}, {k, Length[ptn]}]]@*Union]], {n, 0, 15}]
PROG
(Python)
from sympy.utilities.iterables import partitions
def A364915(n):
if n <= 1: return 1
alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
for p in partitions(n, k=n-1):
s = set(p)
if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
c += 1
return c # Chai Wah Wu, Sep 23 2023
CROSSREFS
For sums instead of combinations we have A237667, binary A236912.
For subsets instead of partitions we have A326083, complement A364914.
The strict case is A364350.
The complement is A365068, strict A364839.
The positive case is A365072, strict A365006.
A000041 counts integer partitions, strict A000009.
A007865 counts binary sum-free sets w/ re-usable parts, complement A093971.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A364912 counts linear combinations of partitions of k.
Sequence in context: A145933 A300788 A120171 * A145816 A347610 A027583
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 22 2023
EXTENSIONS
a(37)-a(59) from Chai Wah Wu, Sep 25 2023
STATUS
approved