A364350 - OEIS

A364350

Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.

1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 5, 3, 6, 5, 7, 6, 9, 7, 11, 10, 14, 12, 16, 15, 20, 17, 24, 22, 27, 29, 32, 30, 41, 36, 49, 45, 50, 52, 65, 63, 70, 77, 80, 83, 104, 98, 107, 116, 126, 134, 152, 148, 162, 180, 196, 195, 227, 227, 238, 272, 271, 293, 333, 325

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

A way of writing n as a (presumed nonnegative) linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i >= 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(1,1),(0,2)) are a way of writing 5 as a linear combination of (1,1,1,2), namely 5 = 3*1 + 1*1 + 1*1 + 0*2. Of course, there are A000041(n) ways to write n as a linear combination of (1..n).

LINKS

Table of n, a(n) for n=0..64.

EXAMPLE

The a(16) = 6 through a(22) = 12 strict partitions:

(16) (17) (18) (19) (20) (21) (22)

(9,7) (9,8) (10,8) (10,9) (11,9) (12,9) (13,9)

(10,6) (10,7) (11,7) (11,8) (12,8) (13,8) (14,8)

(11,5) (11,6) (13,5) (12,7) (13,7) (15,6) (15,7)

(13,3) (12,5) (14,4) (13,6) (14,6) (16,5) (16,6)

(7,5,4) (13,4) (7,6,5) (14,5) (17,3) (17,4) (17,5)

(14,3) (8,7,3) (15,4) (8,7,5) (19,2) (18,4)

(15,2) (16,3) (9,6,5) (11,10) (19,3)

(7,6,4) (17,2) (9,7,4) (8,7,6) (12,10)

(8,6,5) (11,5,4) (9,7,5) (9,7,6)

(9,6,4) (10,7,4) (9,8,5)

(10,8,3) (7,6,5,4)

(11,6,4)

(11,7,3)

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], UnsameQ@@#&&And@@Table[combs[#[[k]], Delete[#, k]]=={}, {k, Length[#]}]&]], {n, 0, 15}]

PROG

(Python)

from sympy.utilities.iterables import partitions

def A364350(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):

if max(p.values(), default=0)==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 of subsets instead of combinations of partitions we have A151897.

For sums instead of combinations we have A237667, binary A236912.

For subsets instead of partitions we have A326083, complement A364914.

The complement in strict partitions is A364839, non-strict A364913.

A more strict variation is A364915.

The case of all positive coefficients is A365006.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A108917 counts knapsack partitions, ranks A299702.

A116861 and A364916 count linear combinations of strict partitions.

A323092 (ranks A320340) and A120641 count double-free partitions.

A364912 counts linear combinations of partitions of k.

Cf. A007865, A085489, A237113, A275972, A363226, A364272, A364533, A364910, A364911, A365002, A365004.

Sequence in context: A244327 A319318 A029164 * A053262 A007359 A213424

Adjacent sequences: A364347 A364348 A364349 * A364351 A364352 A364353

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 15 2023

EXTENSIONS

More terms and offset corrected by Martin Fuller, Sep 11 2023

STATUS

approved