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

Author

Gus Wiseman, Jun 02 2020

Keywords

• nonn
• tabf

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.

Examples

			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
		

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.

Programs

Mathematica

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

Formula

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