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

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

Alois P. Heinz, Rows n = 0..14, flattened

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.

Cf. A000120, A003022, A029931, A048793, A066099, A070939, A103295, A108917, A143823, A325680.

Sequence in context: A035566 A110783 A333224 * A334300 A308093 A264154

Adjacent sequences: A124767 A124768 A124769 * A124771 A124772 A124773

Keyword

easy,nonn,tabf

Author

Franklin T. Adams-Watters, Nov 06 2006

Status

approved