login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A124771 Number of distinct subsequences for compositions in standard order. 30
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

LINKS

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

FORMULA

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)

EXAMPLE

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)

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

CROSSREFS

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.

Sequence in context: A164341 A333257 A334968 * A334299 A066589 A007897

Adjacent sequences:  A124768 A124769 A124770 * A124772 A124773 A124774

KEYWORD

easy,nonn,tabf,base

AUTHOR

Franklin T. Adams-Watters, Nov 06 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 11 13:25 EDT 2020. Contains 335626 sequences. (Running on oeis4.)