cp's OEIS Frontend

A124770 Number of distinct nonempty subsequences for compositions in standard order.

%I A124770 #12 May 05 2020 02:02:43
%S A124770 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,
%T A124770 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,
%U A124770 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
%N A124770 Number of distinct nonempty subsequences for compositions in standard order.
%C A124770 The standard order of compositions is given by A066099.
%C A124770 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
%H A124770 Alois P. Heinz, <a href="/A124770/b124770.txt">Rows n = 0..14, flattened</a>
%F A124770 a(n) = A124771(n) - 1. - _Gus Wiseman_, Apr 03 2020
%e A124770 Composition number 11 is 2,1,1; the nonempty subsequences are 1; 2; 1,1; 2,1; 2,1,1; so a(11) = 5.
%e A124770 The table starts:
%e A124770   0
%e A124770   1
%e A124770   1 2
%e A124770   1 3 3 3
%e A124770   1 3 2 5 3 5 5 4
%e A124770   1 3 3 5 3 5 5 7 3 5 5 8 5 8 7 5
%e A124770 From _Gus Wiseman_, Apr 03 2020: (Start)
%e A124770 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:
%e A124770   1  2  1  4  1  1  1  8  1  2   1   1   1   1   1   16  1   2   1   2
%e A124770         3     2  2  3     4  10  2   4   2   2   3       8   4   4   4
%e A124770               5  6  7     9      3   12  6   3   7       17  18  3   20
%e A124770                                  5       5   6   15              9
%e A124770                                  11      13  14                  19
%e A124770 (End)
%t A124770 stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A124770 Table[Length[Union[ReplaceList[stc[n],{___,s__,___}:>{s}]]],{n,0,100}] (* _Gus Wiseman_, Apr 03 2020 *)
%Y A124770 Row lengths are A011782.
%Y A124770 Allowing empty subsequences gives A124771.
%Y A124770 Dominates A333224, the version counting subsequence-sums instead of subsequences.
%Y A124770 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.
%Y A124770 Positive subset-sums of partitions are counted by A276024 and A299701.
%Y A124770 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.
%Y A124770 Cf. A000120, A003022, A029931, A048793, A066099, A070939, A103295, A108917, A143823, A325680.
%K A124770 easy,nonn,tabf
%O A124770 0,4
%A A124770 _Franklin T. Adams-Watters_, Nov 06 2006