login
Number of distinct nonempty subsequences (not necessarily contiguous) in the n-th composition in standard order (A066099).
3

%I #6 Jun 04 2020 06:39:50

%S 0,1,1,2,1,3,3,3,1,3,2,5,3,6,5,4,1,3,3,5,3,5,6,7,3,6,5,9,5,9,7,5,1,3,

%T 3,5,2,7,7,7,3,7,3,8,7,11,10,9,3,6,7,9,7,10,11,12,5,9,8,13,7,12,9,6,1,

%U 3,3,5,3,7,7,7,3,5,5,11,6,13,11,9,3,7,6

%N Number of distinct nonempty subsequences (not necessarily contiguous) in the n-th composition in standard order (A066099).

%C Looking only at contiguous subsequences, or restrictions to a subinterval, gives A124770.

%C 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.

%F a(n) = A334299(n) - 1.

%e Triangle begins:

%e 1

%e 1 2

%e 1 3 3 3

%e 1 3 2 5 3 6 5 4

%e 1 3 3 5 3 5 6 7 3 6 5 9 5 9 7 5

%e If the k-th composition in standard order is c, then we say that the STC-number of c is k. The n-th column below lists the STC-numbers of the nonempty subsequences of the composition with STC-number n:

%e 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

%e 1 2 2 3 4 2 5 4 6 6 7

%e 1 1 1 1 3 1 5 3 3

%e 2 3 2 1

%e 1 2 1

%e 1

%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t Table[Length[Union[Rest[Subsets[stc[n]]]]],{n,0,100}]

%Y Row lengths are A011782.

%Y Looking only at contiguous subsequences gives A124770.

%Y The contiguous case with empty subsequences allowed is A124771.

%Y Allowing empty subsequences gives A334299.

%Y Compositions where every subinterval has a different sum are A333222.

%Y Knapsack compositions are A333223.

%Y Contiguous positive subsequence-sums are counted by A333224.

%Y Contiguous subsequence-sums are counted by A333257.

%Y Subsequence-sums are counted by A334968.

%Y Cf. A000120, A029931, A048793, A066099, A070939, A108917, A325676, A334967.

%K nonn,tabf

%O 0,4

%A _Gus Wiseman_, Jun 01 2020