A365068 - OEIS

A365068

Number of integer partitions of n with some part that can be written as a nonnegative linear combination of the other distinct parts.

0, 0, 0, 1, 2, 4, 7, 10, 16, 23, 34, 44, 67, 85, 119, 157, 210, 268, 360, 453, 592, 748, 956, 1195, 1520, 1883, 2365, 2920, 3628, 4451, 5494, 6702, 8211, 9976, 12147, 14666, 17776, 21389, 25774, 30887, 37035, 44224, 52819, 62836, 74753, 88614, 105062, 124160

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

OFFSET

0,5

COMMENTS

These may be called "non-binary nonnegative combination-full" partitions.

Does not necessarily include all non-strict partitions (A047967).

LINKS

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

EXAMPLE

The partition (5,4,3,3) has no part that can be written as a nonnegative linear combination of the others, so is not counted under a(15).

The partition (6,4,3,2) has 6 = 1*2 + 1*4, so is counted under a(15). The combinations 6 = 2*3 = 3*2 and 4 = 2*2 can also be used.

The a(3) = 1 through a(8) = 16 partitions:

(21) (31) (41) (42) (61) (62)

(211) (221) (51) (331) (71)

(311) (321) (421) (422)

(2111) (411) (511) (431)

(2211) (2221) (521)

(3111) (3211) (611)

(21111) (4111) (3221)

(22111) (3311)

(31111) (4211)

(211111) (5111)

(22211)

(32111)

(41111)

(221111)

(311111)

(2111111)

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]], DeleteCases[ptn, ptn[[k]]]]!={}, {k, Length[ptn]}]]]], {n, 0, 5}]

PROG

(Python)

from sympy.utilities.iterables import partitions

def A365068(n):

if n <= 1: return 0

alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 0

for p in partitions(n, k=n-1):

s = set(p)

if any(set(t).issubset(s-{q}) for q in s for t in alist[q]):

c += 1

return c # Chai Wah Wu, Sep 20 2023

CROSSREFS

The complement for sums instead of combinations is A237667, binary A236912.

For sums instead of combinations we have A237668, binary A237113.

The strict case is A364839, complement A364350.

Allowing equal parts in the combination gives A364913.

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

The complement is A364915.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A116861 and A364916 count linear combinations of strict partitions.

A323092 counts double-free partitions, ranks A320340.

A364912 counts linear combinations of partitions of k.

Cf. A108917, A151897, A364272, A364910, A364911, A365006.

Sequence in context: A000376 A000375 A244488 * A131752 A062365 A049630

Adjacent sequences: A365065 A365066 A365067 * A365069 A365070 A365071

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 27 2023

EXTENSIONS

a(31)-a(47) from Chai Wah Wu, Sep 20 2023

STATUS

approved