A334968 Number of possible sums of subsequences (not necessarily contiguous) of the n-th composition in standard order (A066099).

1, 2, 2, 3, 2, 4, 4, 4, 2, 4, 3, 5, 4, 5, 5, 5, 2, 4, 4, 6, 4, 6, 6, 6, 4, 6, 6, 6, 6, 6, 6, 6, 2, 4, 4, 6, 3, 7, 7, 7, 4, 7, 4, 7, 7, 7, 7, 7, 4, 6, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 2, 4, 4, 6, 4, 8, 8, 8, 4, 6, 6, 8, 6, 8, 8, 8, 4, 8, 6, 8, 6, 8, 8

Offset

0,2

Comments

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

Links

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

Formula

a(n) = A299701(A333219(n)).

Example

The 139th composition is (4,2,1,1), with possible sums of subsequences {0,1,2,3,4,5,6,7,8}, so a(139) = 9.
Triangle begins:
  1
  2
  2 3
  2 4 4 4
  2 4 3 5 4 5 5 5
  2 4 4 6 4 6 6 6 4 6 6 6 6 6 6 6
  2 4 4 6 3 7 7 7 4 7 4 7 7 7 7 7 4 6 7 7 7 7 7 7 6 7 7 7 7 7 7 7

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Length[Union[Total/@Subsets[stc[n]]]], {n, 0, 100}]

Crossrefs

Row lengths are A011782.

Dominated by A124771 (number of contiguous subsequences).

Dominates A333257 (the contiguous case).

Dominated by A334299 (number of subsequences).

Golomb rulers are counted by A169942 and ranked by A333222.

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

Knapsack partitions are counted by A108917 and ranked by A299702

Knapsack compositions are counted by A325676 and ranked by A333223.

Contiguous subsequence-sums are counted by A333224 and ranked by A333257.

Knapsack compositions are counted by A334268 and ranked by A334967.

Cf. A000120, A029931, A048793, A066099, A070939, A108917, A325769, A325770, A325778, A334300, A335279.

Sequence in context: A140060 A164341 A333257 * A124771 A334299 A066589

Adjacent sequences: A334965 A334966 A334967 * A334969 A334970 A334971

Keyword

nonn,tabf

Author

Gus Wiseman, Jun 02 2020

Status

approved