cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A124771 Number of distinct subsequences for compositions in standard order.

This page as a plain text file.
%I A124771 #21 Jun 05 2020 09:56:23
%S A124771 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,
%T A124771 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,
%U A124771 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
%N A124771 Number of distinct subsequences for compositions in standard order.
%C A124771 The standard order of compositions is given by A066099.
%C A124771 From _Vladimir Shevelev_, Dec 18 2013: (Start)
%C A124771 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.
%C A124771 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.
%C A124771 (End)
%C A124771 These are contiguous subsequences, or restrictions to a subinterval. The case for all subsequences is A334299. - _Gus Wiseman_, Jun 02 2020
%H A124771 Alois P. Heinz, <a href="/A124771/b124771.txt">Rows n = 0..14, flattened</a>
%F A124771 a(n) = A124770(n) + 1.
%F A124771 From _Vladimir Shevelev_, Dec 18 2013: (Start)
%F A124771 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.
%F A124771 a(2^n-1) = n+1; for n>=2, a(2^n+1) = 4.
%F A124771 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)*...
%F A124771 (End)
%e A124771 Composition number 11 is 2,1,1; the subsequences are (empty); 1; 2; 1,1; 2,1; 2,1,1; so a(11) = 6.
%e A124771 The table starts:
%e A124771 1
%e A124771 2
%e A124771 1 2
%e A124771 1 3 3 3
%e A124771 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.
%e A124771 From _Gus Wiseman_, Jun 01 2020: (Start)
%e A124771 The c-divisors of n are given in column n below:
%e A124771   0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0
%e A124771      1  2  1  4  1  1  1  8  1  2   1   1   1   1   1   16  1   2
%e A124771            3     2  2  3     4  10  2   4   2   2   3       8   4
%e A124771                  5  6  7     9      3   12  5   3   7       17  18
%e A124771                                     5       6   6   15
%e A124771                                     11      13  14
%e A124771 (End)
%t A124771 stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A124771 Table[Length[Union[ReplaceList[stc[n],{___,s___,___}:>{s}]]],{n,0,100}] (* _Gus Wiseman_, Jun 01 2020 *)
%Y A124771 Cf. A000005, A011782 (row lengths), A066099, A114994, A233249, A233312.
%Y A124771 Not allowing empty subsequences gives A124770.
%Y A124771 Dominates A333257.
%Y A124771 The case for not just contiguous subsequences is A334299.
%Y A124771 Positions of first appearances are A335279.
%Y A124771 Compositions where every subinterval has a different sum are A333222.
%Y A124771 Knapsack compositions are A333223.
%Y A124771 Cf. A000120, A003022, A029931, A070939, A108917, A124767, A325680, A325770, A333224, A334967, A334968.
%K A124771 easy,nonn,tabf,base
%O A124771 0,2
%A A124771 _Franklin T. Adams-Watters_, Nov 06 2006