login
Number of partitions of n such that no part is a sum of two or more other parts.
57

%I #24 Aug 11 2023 10:03:31

%S 1,1,2,3,4,6,7,11,12,17,19,29,28,41,42,61,61,87,85,120,117,160,156,

%T 224,216,288,277,380,363,483,474,622,610,783,755,994,986,1235,1191,

%U 1549,1483,1876,1865,2306,2279,2806,2732,3406,3413,4091,4013,4991,4895,5872

%N Number of partitions of n such that no part is a sum of two or more other parts.

%C From _Gus Wiseman_, Aug 09 2023: (Start)

%C Includes all knapsack partitions (A108917), but first differs at a(12) = 28, A108917(12) = 25. The difference is accounted for by the non-knapsack partitions: (4332), (5331), (33222).

%C These are partitions not containing the sum of any non-singleton submultiset of the parts, a variation of non-binary sum-free partitions where parts cannot be re-used, ranked by A364531. The complement is counted by A237668. The binary version is A236912. For re-usable parts we have A364350.

%C (End)

%H Giovanni Resta, <a href="/A237667/b237667.txt">Table of n, a(n) for n = 0..100</a>

%H Giovanni Resta, <a href="/A237667/a237667.c.txt">C program for computing a(0)-a(100)</a>

%e For n = 6, the nonqualifiers are 123, 1113, 1122, 11112, leaving a(6) = 7.

%e From _Gus Wiseman_, Aug 09 2023: (Start)

%e The partition y = (5,3,1,1) has submultiset (3,1,1) with sum in y, so is not counted under a(10).

%e The partition y = (5,3,3,1) has no non-singleton submultiset with sum in y, so is counted under a(12).

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

%e (1) (2) (3) (4) (5) (6) (7) (8)

%e (11) (21) (22) (32) (33) (43) (44)

%e (111) (31) (41) (42) (52) (53)

%e (1111) (221) (51) (61) (62)

%e (311) (222) (322) (71)

%e (11111) (411) (331) (332)

%e (111111) (421) (521)

%e (511) (611)

%e (2221) (2222)

%e (4111) (3311)

%e (1111111) (5111)

%e (11111111)

%e (End)

%t Map[Count[Map[MemberQ[#,Apply[Alternatives,Map[Apply[Plus,#]&, DeleteDuplicates[DeleteCases[Subsets[#],_?(Length[#]<2&)]]]]]&, IntegerPartitions[#]],False]&,Range[20]] (* _Peter J. C. Moses_, Feb 10 2014 *)

%t Table[Length[Select[IntegerPartitions[n],Intersection[#,Total/@Subsets[#,{2,Length[#]}]]=={}&]],{n,0,15}] (* _Gus Wiseman_, Aug 09 2023 *)

%Y For subsets of {1..n} we have A151897, binary A085489.

%Y The binary version is A236912, ranks A364461.

%Y The binary complement is A237113, ranks A364462.

%Y The complement is counted by A237668, ranks A364532.

%Y The binary version with re-usable parts is A364345, strict A364346.

%Y The strict case is A364349, binary A364533.

%Y These partitions have ranks A364531.

%Y The complement for subsets is A364534, binary A088809.

%Y A000041 counts partitions, strict A000009.

%Y A008284 counts partitions by length, strict A008289.

%Y A108917 counts knapsack partitions, ranks A299702.

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

%Y Cf. A002865, A007865, A179009, A325862, A326083, A363225, A363226, A364348, A364350, A364670.

%K nonn

%O 0,3

%A _Clark Kimberling_, Feb 11 2014

%E a(21)-a(53) from _Giovanni Resta_, Feb 22 2014