A353864 Number of rucksack partitions of n: every consecutive constant subsequence has a different sum.

1, 1, 2, 3, 4, 6, 8, 11, 14, 19, 25, 33, 39, 51, 65, 82, 101, 126, 154, 191, 232, 284, 343, 416, 496, 600, 716, 855, 1018, 1209, 1430, 1691, 1991, 2345, 2747, 3224, 3762, 4393, 5116, 5946, 6897, 7998, 9257, 10696, 12336, 14213, 16343, 18781, 21538, 24687, 28253, 32291, 36876, 42057

Offset: 0

Author

Gus Wiseman, May 23 2022

Keywords

• nonn

Comments

In a knapsack partition (A108917), every submultiset has a different sum, so these are run-knapsack partitions or rucksack partitions for short. Another variation of knapsack partitions is A325862.

Examples

			The a(0) = 1 through a(7) = 11 partitions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)       (7)
           (11)  (21)   (22)    (32)     (33)      (43)
                 (111)  (31)    (41)     (42)      (52)
                        (1111)  (221)    (51)      (61)
                                (311)    (222)     (322)
                                (11111)  (321)     (331)
                                         (411)     (421)
                                         (111111)  (511)
                                                   (2221)
                                                   (4111)
                                                   (1111111)
		

Crossrefs

Knapsack partitions are counted by A108917, ranked by A299702.

The strong case is A353838, counted by A353837, complement A353839.

The perfect case is A353865, ranked by A353867.

These partitions are ranked by A353866.

A000041 counts partitions, strict A000009.

A300273 ranks collapsible partitions, counted by A275870.

A304442 counts partitions with all equal run-sums, ranked by A353833.

A353832 represents the operation of taking run-sums of a partition.

A353836 counts partitions by number of distinct run-sums.

A353840-A353846 pertain to partition run-sum trajectory.

A353852 ranks compositions with all distinct run-sums, counted by A353850.

A353863 counts partitions whose weak run-sums cover an initial interval.

Cf. A008284, A018818, A225485, A325239, A325277, A325280, A325862, A353834.

Programs

Mathematica

msubs[s_]:=Join@@@Tuples[Table[Take[t,i],{t,Split[s]},{i,0,Length[t]}]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@Total/@Select[msubs[#],SameQ@@#&]&]],{n,0,30}]

Extensions

a(50)-a(53) from Robert Price, Apr 03 2025