A354580 Number of rucksack compositions of n: every distinct partial run has a different sum.

1, 1, 2, 4, 6, 12, 22, 39, 68, 125, 227, 402, 710, 1280, 2281, 4040, 7196, 12780, 22623, 40136, 71121, 125863, 222616, 393305, 695059, 1227990, 2167059, 3823029, 6743268, 11889431, 20955548, 36920415, 65030404, 114519168, 201612634, 354849227

Offset: 0

Author

Gus Wiseman, Jun 13 2022

Keywords

• nonn

Comments

We define a partial run of a sequence to be any contiguous constant subsequence. The term rucksack is short for run-knapsack.

Examples

			The a(0) = 1 through a(5) = 12 compositions:
  ()  (1)  (2)    (3)      (4)        (5)
           (1,1)  (1,2)    (1,3)      (1,4)
                  (2,1)    (2,2)      (2,3)
                  (1,1,1)  (3,1)      (3,2)
                           (1,2,1)    (4,1)
                           (1,1,1,1)  (1,1,3)
                                      (1,2,2)
                                      (1,3,1)
                                      (2,1,2)
                                      (2,2,1)
                                      (3,1,1)
                                      (1,1,1,1,1)
		

Links

• Max Alekseyev, Table of n, a(n) for n = 0..65

Crossrefs

The knapsack version is A325676, ranked by A333223.

The non-partial version for partitions is A353837, ranked by A353838 (complement A353839).

The non-partial version is A353850, ranked by A353852.

The version for partitions is A353864, ranked by A353866.

The complete version for partitions is A353865, ranked by A353867.

These compositions are ranked by A354581.

A003242 counts anti-run compositions, ranked by A333489.

A011782 counts compositions.

A108917 counts knapsack partitions, ranked by A299702, strict A275972.

A238279 and A333755 count compositions by number of runs.

A275870 counts collapsible partitions, ranked by A300273.

A353836 counts partitions by number of distinct run-sums.

A353847 is the composition run-sum transformation.

A353851 counts compositions with all equal run-sums, ranked by A353848.

A353853-A353859 pertain to composition run-sum trajectory.

A353860 counts collapsible compositions, ranked by A354908.

Cf. A143823, A169942, A242882, A325545, A325680, A325682, A325685, A325687, A329739, A351017, A353849.

Programs

Mathematica

Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n],UnsameQ@@Total/@Union@@Subsets/@Split[#]&]],{n,0,15}]

Extensions

Terms a(16) onward from Max Alekseyev, Sep 10 2023