login
A124771
Number of distinct subsequences for compositions in standard order.
39
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,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
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.
Sequence in context: A164341 A333257 A334968 * A334299 A066589 A007897
KEYWORD
easy,nonn,tabf,base
AUTHOR
STATUS
approved