cp's OEIS Frontend

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

%I A334300 #13 Mar 12 2025 17:14:14
%S A334300 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 A334300 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 A334300 3,3,5,3,7,7,7,3,5,5,11,6,13,11,9,3,7,6
%N A334300 Number of distinct nonempty subsequences (not necessarily contiguous) in the n-th composition in standard order (A066099).
%C A334300 Looking only at contiguous subsequences, or restrictions to a subinterval, gives A124770.
%C A334300 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.
%H A334300 John Tyler Rascoe, <a href="/A334300/b334300.txt">Table of n, a(n) for n = 0..8192</a>
%F A334300 a(n) = A334299(n) - 1.
%e A334300 Triangle begins:
%e A334300   1
%e A334300   1 2
%e A334300   1 3 3 3
%e A334300   1 3 2 5 3 6 5 4
%e A334300   1 3 3 5 3 5 6 7 3 6 5 9 5 9 7 5
%e A334300 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 A334300   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
%e A334300         1     2  2  3     4   2   5   4   6   6   7
%e A334300               1  1  1     1       3   1   5   3   3
%e A334300                                   2       3   2   1
%e A334300                                   1       2   1
%e A334300                                           1
%t A334300 stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A334300 Table[Length[Union[Rest[Subsets[stc[n]]]]],{n,0,100}]
%o A334300 (Python)
%o A334300 from itertools import combinations
%o A334300 def comp(n):
%o A334300     # see A357625
%o A334300     return
%o A334300 def A334300(n):
%o A334300     A,C = set(),comp(n)
%o A334300     c = range(len(C))
%o A334300     for j in c:
%o A334300         for k in combinations(c, j):
%o A334300             A.add(tuple(C[i] for i in k))
%o A334300     return len(A) # _John Tyler Rascoe_, Mar 12 2025
%Y A334300 Row lengths are A011782.
%Y A334300 Looking only at contiguous subsequences gives A124770.
%Y A334300 The contiguous case with empty subsequences allowed is A124771.
%Y A334300 Allowing empty subsequences gives A334299.
%Y A334300 Compositions where every subinterval has a different sum are A333222.
%Y A334300 Knapsack compositions are A333223.
%Y A334300 Contiguous positive subsequence-sums are counted by A333224.
%Y A334300 Contiguous subsequence-sums are counted by A333257.
%Y A334300 Subsequence-sums are counted by A334968.
%Y A334300 Cf. A000120, A029931, A048793, A066099, A070939, A108917, A325676, A334967.
%K A334300 nonn,look,tabf
%O A334300 0,4
%A A334300 _Gus Wiseman_, Jun 01 2020