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

Offset

0,3

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.

Links

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

Example

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)

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}]

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.

Sequence in context: A239467 A035945 A094707 * A303663 A117995 A033834

Adjacent sequences: A353861 A353862 A353863 * A353865 A353866 A353867

Keyword

nonn

Author

Gus Wiseman, May 23 2022

Status

approved