A334967 -id:A334967 - cp's OEIS frontend

A124771 Number of distinct subsequences for compositions in standard order.

1, 2, 2, 3, 2, 4, 4, 4, 2, 4, 3, 6, 4, 6, 6, 5, 2, 4, 4, 6, 4, 6, 6, 8, 4, 6, 6, 9, 6, 9, 8, 6, 2, 4, 4, 6, 3, 7, 7, 8, 4, 7, 4, 9, 7, 8, 9, 10, 4, 6, 7, 9, 7, 9, 8, 12, 6, 9, 9, 12, 8, 12, 10, 7, 2, 4, 4, 6, 4, 7, 7, 8, 4, 6, 6, 10, 6, 10, 10, 10, 4, 7, 6, 10, 6, 8, 9, 12, 7, 10, 9, 12, 10, 12, 12, 12, 4

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.
From Vladimir Shevelev, Dec 18 2013: (Start)
Every number in binary is a concatenation of parts of the form 10...0 with k>=0 zeros. For example, 5=(10)(1), 11=(10)(1)(1), 7=(1)(1)(1). We call d>0 a c-divisor of m, if d consists of some consecutive parts of m taking from the left to the right. Note that, to d=0 corresponds an empty set of parts. So it is natural to consider 0 as a c-divisor of every m. For example, 5=(10)(1) is a divisor of 23=(10)(1)(1)(1). Analogously, 1,2,3,7,11,23 are c-divisors of 23. But 6=(1)(10) is not a c-divisor of 23.
One can prove a one-to-one correspondence between distinct subsequences for  composition no. n in standard order and c-divisors of n. So, the sequence lists also numbers of c-divisors of nonnegative integers.
(End)
These are contiguous subsequences, or restrictions to a subinterval. The case for all subsequences is A334299. - Gus Wiseman, Jun 02 2020

			Composition number 11 is 2,1,1; the subsequences are (empty); 1; 2; 1,1; 2,1; 2,1,1; so a(11) = 6.
The table starts:
1
2
1 2
1 3 3 3
Let n=11=(10)(1)(1). We have the following c-divisors of 11: 0,1,2,3,5,11. Thus a(11)=6. Note, that 3=(1)(1) is not a c-divisor of 13=(1)(10)(1) since, although it contains parts of 3=(1)(1), but in non-consecutive order. The c-divisors of 13 are 0,1,2,5,6,13. So, a(13)=6.
From _Gus Wiseman_, Jun 01 2020: (Start)
The c-divisors of n are given in column n below:
  0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0
     1  2  1  4  1  1  1  8  1  2   1   1   1   1   1   16  1   2
           3     2  2  3     4  10  2   4   2   2   3       8   4
                 5  6  7     9      3   12  5   3   7       17  18
                                    5       6   6   15
                                    11      13  14
(End)

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

Cf. A000005, A011782 (row lengths), A066099, A114994, A233249, A233312.
Not allowing empty subsequences gives A124770.
Dominates A333257.
The case for not just contiguous subsequences is A334299.
Positions of first appearances are A335279.
Compositions where every subinterval has a different sum are A333222.
Knapsack compositions are A333223.
Cf. A000120, A003022, A029931, A070939, A108917, A124767, A325680, A325770, A333224, A334967, A334968.

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, Jun 01 2020 *)

a(n) = A124770(n) + 1.
From Vladimir Shevelev, Dec 18 2013: (Start)
a(2^n) = 2. Note that in concatenation representations of integers in binary, numbers {2^k}, k>=0, play the role of primes. So the formula is an analog of A000005(prime(n))=2.
a(2^n-1) = n+1; for n>=2, a(2^n+1) = 4.
For c-equivalent numbers n_1 and n_2 (i.e., differed only by order of parts) we have a(n_1) = a(n_2). For example, a(24)=a(17)=4. If the canonical representation of n is n=(1)^k_1[*](10)^k_2[*](100)^k_3[*]... , where [*] denotes operation of concatenation (cf. A233569), then a(n)<=(k_1+1)*(k_2+1)*...
(End)

A334299 Number of distinct subsequences (not necessarily contiguous) of compositions in standard order (A066099).

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 4, 4, 2, 4, 3, 6, 4, 7, 6, 5, 2, 4, 4, 6, 4, 6, 7, 8, 4, 7, 6, 10, 6, 10, 8, 6, 2, 4, 4, 6, 3, 8, 8, 8, 4, 8, 4, 9, 8, 12, 11, 10, 4, 7, 8, 10, 8, 11, 12, 13, 6, 10, 9, 14, 8, 13, 10, 7, 2, 4, 4, 6, 4, 8, 8, 8, 4, 6, 6, 12, 7, 14, 12, 10, 4

Offset: 0

Gus Wiseman, Jun 01 2020

nonn

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.

			Triangle begins:
  1
  2
  2 3
  2 4 4 4
  2 4 3 6 4 7 6 5
  2 4 4 6 4 6 7 8 4 7 6 10 6 10 8 6
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 subsequences of the composition with STC-number n:
  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
     0  0  1  0  2  2  3  0  4   2   5   4   6   6   7
           0     1  1  1     1   0   3   1   5   3   3
                 0  0  0     0       2   0   3   2   1
                                     1       2   1   0
                                     0       1   0
                                             0

Row lengths are A011782.
Looking only at contiguous subsequences gives A124771.
Compositions where every subinterval has a different sum are A333222.
Knapsack compositions are A333223.
Contiguous positive subsequence-sums are counted by A333224.
Contiguous subsequence-sums are counted by A333257.
Disallowing empty subsequences gives A334300.
Subsequence-sums are counted by A334968.
Cf. A000120, A029931, A048793, A066099, A070939, A108917, A325676, A334967.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[Subsets[stc[n]]]],{n,0,100}]

a(n) = A334300(n) + 1.

A334968 Number of possible sums of subsequences (not necessarily contiguous) of the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 4, 4, 2, 4, 3, 5, 4, 5, 5, 5, 2, 4, 4, 6, 4, 6, 6, 6, 4, 6, 6, 6, 6, 6, 6, 6, 2, 4, 4, 6, 3, 7, 7, 7, 4, 7, 4, 7, 7, 7, 7, 7, 4, 6, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 2, 4, 4, 6, 4, 8, 8, 8, 4, 6, 6, 8, 6, 8, 8, 8, 4, 8, 6, 8, 6, 8, 8

Offset: 0

Gus Wiseman, Jun 02 2020

			The 139th composition is (4,2,1,1), with possible sums of subsequences {0,1,2,3,4,5,6,7,8}, so a(139) = 9.
Triangle begins:
  1
  2
  2 3
  2 4 4 4
  2 4 3 5 4 5 5 5
  2 4 4 6 4 6 6 6 4 6 6 6 6 6 6 6
  2 4 4 6 3 7 7 7 4 7 4 7 7 7 7 7 4 6 7 7 7 7 7 7 6 7 7 7 7 7 7 7

Row lengths are A011782.
Dominated by A124771 (number of contiguous subsequences).
Dominates A333257 (the contiguous case).
Dominated by A334299 (number of subsequences).
Golomb rulers are counted by A169942 and ranked by A333222.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and ranked by A299702
Knapsack compositions are counted by A325676 and ranked by A333223.
Contiguous subsequence-sums are counted by A333224 and ranked by A333257.
Knapsack compositions are counted by A334268 and ranked by A334967.
Cf. A000120, A029931, A048793, A066099, A070939, A108917, A325769, A325770, A325778, A334300, A335279.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[Total/@Subsets[stc[n]]]],{n,0,100}]

a(n) = A299701(A333219(n)).

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

Original entry on oeis.org

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, 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, 3, 3, 5, 3, 7, 7, 7, 3, 5, 5, 11, 6, 13, 11, 9, 3, 7, 6

Offset: 0

Gus Wiseman, Jun 01 2020

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

			Triangle begins:
  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
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:
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
        1     2  2  3     4   2   5   4   6   6   7
              1  1  1     1       3   1   5   3   3
                                  2       3   2   1
                                  1       2   1
                                          1

John Tyler Rascoe, Table of n, a(n) for n = 0..8192

Row lengths are A011782.
Looking only at contiguous subsequences gives A124770.
The contiguous case with empty subsequences allowed is A124771.
Allowing empty subsequences gives A334299.
Compositions where every subinterval has a different sum are A333222.
Knapsack compositions are A333223.
Contiguous positive subsequence-sums are counted by A333224.
Contiguous subsequence-sums are counted by A333257.
Subsequence-sums are counted by A334968.
Cf. A000120, A029931, A048793, A066099, A070939, A108917, A325676, A334967.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[Rest[Subsets[stc[n]]]]],{n,0,100}]

from itertools import combinations
def comp(n):
    # see A357625
    return
def A334300(n):
    A,C = set(),comp(n)
    c = range(len(C))
    for j in c:
        for k in combinations(c, j):
            A.add(tuple(C[i] for i in k))
    return len(A) # John Tyler Rascoe, Mar 12 2025

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

A334268 Number of compositions of n where every distinct subsequence (not necessarily contiguous) has a different sum.

Original entry on oeis.org

1, 1, 2, 4, 5, 10, 10, 24, 24, 43, 42, 88, 72, 136, 122, 242, 213, 392, 320, 630, 490, 916, 742, 1432, 1160, 1955, 1604, 2826, 2310, 3850, 2888, 5416, 4426, 7332, 5814, 10046, 7983, 12946, 10236, 17780, 14100, 22674, 17582, 30232, 23674, 37522, 29426, 49832

Offset: 0

Gus Wiseman, Jun 02 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

The contiguous case is A325676.

			The a(1) = 1 through a(6) = 19 compositions:
  (1)  (2)    (3)      (4)        (5)          (6)
       (1,1)  (1,2)    (1,3)      (1,4)        (1,5)
              (2,1)    (2,2)      (2,3)        (2,4)
              (1,1,1)  (3,1)      (3,2)        (3,3)
                       (1,1,1,1)  (4,1)        (4,2)
                                  (1,1,3)      (5,1)
                                  (1,2,2)      (1,1,4)
                                  (2,2,1)      (2,2,2)
                                  (3,1,1)      (4,1,1)
                                  (1,1,1,1,1)  (1,1,1,1,1,1)

These compositions are ranked by A334967.
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 partitions are counted by A108917 and A325592 and ranked by A299702, while the strict case is counted by A275972 and ranked by A059519 and A301899.
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. A003022, A029931, A103295, A143823, A325680, A333224.

b:= proc(n, s) option remember; `if`(n=0, 1, add((h->
      `if`(nops(h)=nops(map(l-> add(i, i=l), h)),
       b(n-j, h), 0))({s[], map(l-> [l[], j], s)[]}), j=1..n))
    end:
a:= n-> b(n, {[]}):
seq(a(n), n=0..23);  # Alois P. Heinz, Jun 03 2020

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Total/@Union[Subsets[#]]&]],{n,0,15}]

a(18)-a(47) from Alois P. Heinz, Jun 03 2020

cp's OEIS Frontend

A124771 Number of distinct subsequences for compositions in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A334299 Number of distinct subsequences (not necessarily contiguous) of compositions in standard order (A066099).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A334968 Number of possible sums of subsequences (not necessarily contiguous) of the n-th composition in standard order (A066099).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A334268 Number of compositions of n where every distinct subsequence (not necessarily contiguous) has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions