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

%I #16 Dec 30 2023 21:23:13

%S 0,0,0,1,2,4,7,10,16,23,34,44,67,85,119,157,210,268,360,453,592,748,

%T 956,1195,1520,1883,2365,2920,3628,4451,5494,6702,8211,9976,12147,

%U 14666,17776,21389,25774,30887,37035,44224,52819,62836,74753,88614,105062,124160

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

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

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

%e 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).

%e 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.

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

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

%e (211) (221) (51) (331) (71)

%e (311) (321) (421) (422)

%e (2111) (411) (511) (431)

%e (2211) (2221) (521)

%e (3111) (3211) (611)

%e (21111) (4111) (3221)

%e (22111) (3311)

%e (31111) (4211)

%e (211111) (5111)

%e (22211)

%e (32111)

%e (41111)

%e (221111)

%e (311111)

%e (2111111)

%t combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]}, Select[Tuples[s],Total[Times@@@#]==n&]];

%t Table[Length[Select[IntegerPartitions[n], Function[ptn,Or@@Table[combs[ptn[[k]], DeleteCases[ptn,ptn[[k]]]]!={}, {k,Length[ptn]}]]]],{n,0,5}]

%o (Python)

%o from sympy.utilities.iterables import partitions

%o def A365068(n):

%o if n <= 1: return 0

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

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

%o s = set(p)

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

%o c += 1

%o return c # _Chai Wah Wu_, Sep 20 2023

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

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

%Y The strict case is A364839, complement A364350.

%Y Allowing equal parts in the combination gives A364913.

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

%Y The complement is A364915.

%Y A000041 counts integer partitions, strict A000009.

%Y A008284 counts partitions by length, strict A008289.

%Y A116861 and A364916 count linear combinations of strict partitions.

%Y A323092 counts double-free partitions, ranks A320340.

%Y A364912 counts linear combinations of partitions of k.

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

%K nonn

%O 0,5

%A _Gus Wiseman_, Aug 27 2023

%E a(31)-a(47) from _Chai Wah Wu_, Sep 20 2023