A334268 Number of compositions of n where every distinct subsequence (not necessarily contiguous) has a different sum.

1, 1, 2, 4, 5, 10, 10, 24, 24, 43, 42, 88, 72, 136, 122, 242, 213, 392, 320, 630, 490, 916, 742, 1432, 1160, 1955, 1604, 2826, 2310, 3850, 2888, 5416, 4426, 7332, 5814, 10046, 7983, 12946, 10236, 17780, 14100, 22674, 17582, 30232, 23674, 37522, 29426, 49832

Offset

0,3

Comments

A composition of n is a finite sequence of positive integers summing to n.

The contiguous case is A325676.

Links

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

Example

The a(1) = 1 through a(6) = 19 compositions:
  (1)  (2)    (3)      (4)        (5)          (6)
       (1,1)  (1,2)    (1,3)      (1,4)        (1,5)
              (2,1)    (2,2)      (2,3)        (2,4)
              (1,1,1)  (3,1)      (3,2)        (3,3)
                       (1,1,1,1)  (4,1)        (4,2)
                                  (1,1,3)      (5,1)
                                  (1,2,2)      (1,1,4)
                                  (2,2,1)      (2,2,2)
                                  (3,1,1)      (4,1,1)
                                  (1,1,1,1,1)  (1,1,1,1,1,1)

Maple

b:= proc(n, s) option remember; `if`(n=0, 1, add((h->
      `if`(nops(h)=nops(map(l-> add(i, i=l), h)),
       b(n-j, h), 0))({s[], map(l-> [l[], j], s)[]}), j=1..n))
    end:
a:= n-> b(n, {[]}):
seq(a(n), n=0..23);  # Alois P. Heinz, Jun 03 2020

Mathematica

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

Crossrefs

These compositions are ranked by A334967.

Compositions where every restriction to a subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222. The case of partitions is counted by A325768 and ranked by A325779.

Positive subset-sums of partitions are counted by A276024 and A299701.

Knapsack partitions are counted by A108917 and A325592 and ranked by A299702, while the strict case is counted by A275972 and ranked by A059519 and A301899.

Knapsack compositions are counted by A325676 and A325687 and ranked by A333223. The case of partitions is counted by A325769 and ranked by A325778, for which the number of distinct consecutive subsequences is given by A325770.

Cf. A003022, A029931, A103295, A143823, A325680, A333224.

Sequence in context: A189767 A173817 A198383 * A220696 A275482 A156799

Adjacent sequences: A334265 A334266 A334267 * A334269 A334270 A334271

Keyword

nonn

Author

Gus Wiseman, Jun 02 2020

Extensions

a(18)-a(47) from Alois P. Heinz, Jun 03 2020

Status

approved