login
A124770
Number of distinct nonempty subsequences for compositions in standard order.
18
0, 1, 1, 2, 1, 3, 3, 3, 1, 3, 2, 5, 3, 5, 5, 4, 1, 3, 3, 5, 3, 5, 5, 7, 3, 5, 5, 8, 5, 8, 7, 5, 1, 3, 3, 5, 2, 6, 6, 7, 3, 6, 3, 8, 6, 7, 8, 9, 3, 5, 6, 8, 6, 8, 7, 11, 5, 8, 8, 11, 7, 11, 9, 6, 1, 3, 3, 5, 3, 6, 6, 7, 3, 5, 5, 9, 5, 9, 9, 9, 3, 6, 5, 9, 5, 7, 8, 11, 6, 9, 8, 11, 9, 11, 11, 11, 3, 5, 6, 8, 5, 9
OFFSET
0,4
COMMENTS
The standard order of compositions is given by A066099.
The k-th composition in standard order (row k of 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. - Gus Wiseman, Apr 03 2020
LINKS
FORMULA
a(n) = A124771(n) - 1. - Gus Wiseman, Apr 03 2020
EXAMPLE
Composition number 11 is 2,1,1; the nonempty subsequences are 1; 2; 1,1; 2,1; 2,1,1; so a(11) = 5.
The table starts:
0
1
1 2
1 3 3 3
1 3 2 5 3 5 5 4
1 3 3 5 3 5 5 7 3 5 5 8 5 8 7 5
From Gus Wiseman, Apr 03 2020: (Start)
If the k-th composition in standard order is c, then we say that the STC-number of c is k. The STC-numbers of the distinct subsequences of the composition with STC-number k are given in column k below:
1 2 1 4 1 1 1 8 1 2 1 1 1 1 1 16 1 2 1 2
3 2 2 3 4 10 2 4 2 2 3 8 4 4 4
5 6 7 9 3 12 6 3 7 17 18 3 20
5 5 6 15 9
11 13 14 19
(End)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Length[Union[ReplaceList[stc[n], {___, s__, ___}:>{s}]]], {n, 0, 100}] (* Gus Wiseman, Apr 03 2020 *)
CROSSREFS
Row lengths are A011782.
Allowing empty subsequences gives A124771.
Dominates A333224, the version counting subsequence-sums instead of subsequences.
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 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.
Sequence in context: A035566 A110783 A333224 * A334300 A308093 A264154
KEYWORD
easy,nonn,tabf
AUTHOR
STATUS
approved