A354904 -id:A354904 - cp's OEIS frontend

A354912 Numbers k such that the k-th composition in standard order is the sequence of run-sums of some other composition.

0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 16, 17, 18, 20, 21, 22, 24, 25, 26, 32, 33, 34, 36, 37, 38, 40, 41, 42, 44, 45, 48, 49, 50, 52, 54, 64, 65, 66, 68, 69, 70, 72, 73, 74, 76, 77, 80, 81, 82, 84, 85, 86, 88, 89, 90, 96, 97, 98, 100, 101, 102, 104, 105, 106, 108

Offset: 0

Gus Wiseman, Jun 22 2022

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.

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).

			The terms and their corresponding compositions begin:
   0: ()
   1: (1)
   2: (2)
   4: (3)
   5: (2,1)
   6: (1,2)
   8: (4)
   9: (3,1)
  10: (2,2)
  12: (1,3)
  13: (1,2,1)
  16: (5)
  17: (4,1)
  18: (3,2)
  20: (2,3)
  21: (2,2,1)
  22: (2,1,2)
For example, the 21st composition in standard order (2,2,1) equals the run-sums of (1,1,2,1), so 21 is in the sequence. On the other hand, no composition has run-sums equal to the 29th composition (1,1,2,1), so 29 is not in the sequence.

The standard compositions used here are A066099, run-sums A353847/A353932.
These are the positions of nonzero terms in A354578.
The complement is A354904, counted by A354909.
These compositions are counted by A354910.
A003242 counts anti-run compositions, ranked by A333489.
A124767 counts runs in standard compositions.
A238279 and A333755 count compositions by number of runs.
A351014 counts distinct runs of standard compositions, firsts A351015.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
A353853-A353859 pertain to composition run-sum trajectory.
Cf. A000120, A029837, A124771, A239312, A333381, A334299, A351597, A353832, A353849, A353860, A354905.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],MemberQ[Total/@Split[#]&/@ Join@@Permutations/@IntegerPartitions[Total[stc[#]]],stc[#]]&]

A354578 Number of ways to choose a divisor of each part of the n-th composition in standard order such that no adjacent divisors are equal.

Original entry on oeis.org

1, 1, 2, 0, 2, 1, 1, 0, 3, 1, 2, 0, 1, 1, 0, 0, 2, 2, 3, 0, 3, 1, 1, 0, 2, 1, 1, 0, 0, 0, 0, 0, 4, 1, 4, 0, 2, 2, 1, 0, 4, 2, 2, 0, 1, 1, 0, 0, 1, 2, 2, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 3, 0, 5, 2, 2, 0, 5, 1, 3, 0, 1, 1, 0, 0, 3, 3, 5, 0, 3, 1, 1

Offset: 0

Gus Wiseman, Jun 11 2022

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4). Then a(n) is the number of integer compositions whose run-sums constitute the n-th composition in standard order (graded reverse-lexicographic, A066099).

			The terms 2^(n - 1) through 2^n - 1 sum to 2^n. As a triangle:
  1
  1
  2 0
  2 1 1 0
  3 1 2 0 1 1 0 0
  2 2 3 0 3 1 1 0 2 1 1 0 0 0 0 0
The a(n) compositions for selected n:
  n=1: n=2:   n=8:       n=32:          n=68:        n=130:
----------------------------------------------------------------------
  (1)  (2)    (4)        (6)            (4,3)        (6,2)
       (1,1)  (2,2)      (3,3)          (2,2,3)      (3,3,2)
              (1,1,1,1)  (2,2,2)        (4,1,1,1)    (6,1,1)
                         (1,1,1,1,1,1)  (1,1,1,1,3)  (3,3,1,1)
                                        (2,2,1,1,1)  (2,2,2,1,1)
                                                     (1,1,1,1,1,1,2)

First column is 1 followed by A000005.
Row-sums are A011782.
Standard compositions are listed by A066099.
Positions of 0's are A354904.
Positions of first appearances are A354905.
A003242 counts anti-run compositions, ranked by A333489.
A005811 counts runs in binary expansion.
A300273 ranks collapsible partitions, counted by A275870.
A353838 ranks partitions with all distinct run-sums, counted by A353837.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353840-A353846 pertain to partition run-sum trajectory.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
A353853-A353859 pertain to composition run-sum trajectory.
A353860 counts collapsible compositions.
A353863 counts run-sum-complete partitions.
A354584 gives run-sums of prime indices, rows ranked by A353832.
Cf. A029837, A124767, A175413, A238279/A333755, A333381, A353847, A353849.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
antirunQ[y_]:=Length[Split[y]]==Length[y];
Table[Length[Select[Tuples[Divisors/@stc[n]],antirunQ]],{n,0,30}]

A354905 First position of n in A354578, where A354578(k) is the number of integer compositions whose run-sums constitute the k-th composition in standard order (graded reverse-lexicographic, A066099).

Original entry on oeis.org

3, 0, 2, 8, 32, 68, 130, 290, 274, 580, 520, 1298, 2080, 1096, 2082, 4168, 2178, 4164, 4386, 35137, 8328, 8786, 10274, 8772, 16712, 20562, 8712, 16658, 33320, 41554, 33288, 82210, 34856, 66628, 33312, 66642, 34850, 69704, 140306, 133448, 69714, 74308, 133154

Offset: 0

Gus Wiseman, Jun 21 2022

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.

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).

			The terms and their corresponding compositions begin:
     3: (1,1)
     0: ()
     2: (2)
     8: (4)
    32: (6)
    68: (4,3)
   130: (6,2)
   290: (3,4,2)
   274: (4,3,2)
   580: (3,4,3)
   520: (6,4)
  1298: (2,4,3,2)
The inverse run-sum compositions for n = 2, 8, 32, 68, 130, 290:
  (2)   (4)     (6)       (43)     (62)       (342)
  (11)  (22)    (33)      (223)    (332)      (3411)
        (1111)  (222)     (4111)   (611)      (11142)
                (111111)  (11113)  (3311)     (32211)
                          (22111)  (22211)    (111411)
                                   (1111112)  (311112)
                                              (1112211)

The standard compositions used here are A066099, run-sums A353847/A353932.
This is the position of the first appearance of n in A354578.
A011782 counts compositions.
A003242 counts anti-run compositions, ranked by A333489.
A005811 counts runs in binary expansion.
A353838 ranks partitions with all distinct run-sums, counted by A353837.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
A353853-A353859 pertain to composition run-sum trajectory.
A354904 lists positions of zeros in A354578, complement A354912.
A354908 ranks collapsible compositions, counted by A353860.
Cf. A000005, A029837, A124767, A238279/A333755, A274174, A333381, A353832, A353849, A353863, A354584.

nn=1000;
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
antirunQ[y_]:=Length[Split[y]]==Length[y];
q=Table[Length[Select[Tuples[Divisors/@stc[n]],antirunQ]],{n,0,nn}];
w=Last[Select[Table[Take[q+1,i],{i,nn}],Union[#]==Range[Max@@#]&]-1];
Table[Position[w,k][[1,1]]-1,{k,0,Max@@w}]

A355748 Number of ways to choose a sequence of divisors, one of each part of the n-th composition in standard order.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 3, 2, 4, 2, 2, 2, 2, 1, 2, 3, 4, 2, 4, 4, 4, 2, 3, 2, 4, 2, 2, 2, 2, 1, 4, 2, 6, 3, 4, 4, 4, 2, 6, 4, 8, 4, 4, 4, 4, 2, 2, 3, 4, 2, 4, 4, 4, 2, 3, 2, 4, 2, 2, 2, 2, 1, 2, 4, 4, 2, 6, 6, 6, 3, 6, 4, 8, 4, 4, 4, 4, 2, 4, 6, 8, 4, 8, 8, 8

Offset: 0

Gus Wiseman, Jul 23 2022

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.

			Composition number 152 in standard order is (3,1,4), and the a(152) = 6 choices are: (1,1,1), (1,1,2), (1,1,4), (3,1,1), (3,1,2), (3,1,4).

Positions of 1's are A000079 (after the first).
The anti-run case is A354578, zeros A354904, firsts A354905.
An unordered version (using prime indices) is A355731:
- firsts A355732,
- resorted A355733,
- weakly increasing A355735,
- relatively prime A355737,
- strict A355739.
A000005 counts divisors.
A003963 multiplies together the prime indices of n.
A005811 counts runs in binary expansion.
A029837 adds up standard compositions, lengths A000120.
A066099 lists the compositions in standard order.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
Cf. A124767, A175413, A238279, A274174, A326841, A333381, A333755, A353847, A353849, A355747.

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

A354909 Number of integer compositions of n that are not the run-sums of any other composition.

Original entry on oeis.org

0, 0, 1, 1, 3, 7, 16, 33, 74, 155, 329, 688, 1439, 2975, 6154, 12654, 25964, 53091, 108369, 220643, 448520

Offset: 0

Gus Wiseman, Jun 19 2022

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).

			The a(0) = 0 through a(6) = 16 compositions:
  .  .  (11)  (111)  (112)   (113)    (114)
                     (211)   (311)    (411)
                     (1111)  (1112)   (1113)
                             (1121)   (1122)
                             (1211)   (1131)
                             (2111)   (1221)
                             (11111)  (1311)
                                      (2112)
                                      (2211)
                                      (3111)
                                      (11112)
                                      (11121)
                                      (11211)
                                      (12111)
                                      (21111)
                                      (111111)

The version for binary words is A000918, complement A000126.
These compositions are ranked by A354904 = positions of zeros in A354578.
The complement is counted by A354910, ranked by A354912.
A003242 counts anti-run compositions, ranked by A333489.
A238279 and A333755 count compositions by number of runs.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353853-A353859 pertain to composition run-sum trajectory.
A353932 lists run-sums of standard compositions, rows ranked by A353847.
Cf. A005811, A027336, A066099, A124767, A274174, A351597, A353849, A353850, A353860, A354905, A354907.

Table[Length[Complement[Join@@Permutations/@IntegerPartitions[n], Total/@Split[#]&/@Join@@Permutations/@IntegerPartitions[n]]],{n,0,15}]

A354910 Number of compositions of n that are the run-sums of some other composition.

Original entry on oeis.org

1, 1, 1, 3, 5, 9, 16, 31, 54, 101, 183, 336, 609, 1121, 2038, 3730, 6804, 12445, 22703, 41501, 75768

Offset: 0

Gus Wiseman, Jun 20 2022

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).

			The a(0) = 0 through a(6) = 16 compositions:
  ()  (1)  (2)  (3)   (4)    (5)    (6)
                (12)  (13)   (14)   (15)
                (21)  (22)   (23)   (24)
                      (31)   (32)   (33)
                      (121)  (41)   (42)
                             (122)  (51)
                             (131)  (123)
                             (212)  (132)
                             (221)  (141)
                                    (213)
                                    (222)
                                    (231)
                                    (312)
                                    (321)
                                    (1212)
                                    (2121)

The version for binary words is A000126, complement A000918
The complement is counted by A354909, ranked by A354904.
These compositions are ranked by A354912 = nonzeros of A354578.
A003242 counts anti-run compositions, ranked by A333489.
A238279 and A333755 count compositions by number of runs.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353853-A353859 pertain to composition run-sum trajectory.
A353932 lists run-sums of standard compositions, rows ranked by A353847.
Cf. A005811, A027336, A066099, A239312, A274174, A351014, A351597, A353849, A353850, A353864, A354905, A354907.

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

cp's OEIS Frontend

A354912 Numbers k such that the k-th composition in standard order is the sequence of run-sums of some other composition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354578 Number of ways to choose a divisor of each part of the n-th composition in standard order such that no adjacent divisors are equal.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354905 First position of n in A354578, where A354578(k) is the number of integer compositions whose run-sums constitute the k-th composition in standard order (graded reverse-lexicographic, A066099).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A355748 Number of ways to choose a sequence of divisors, one of each part of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354909 Number of integer compositions of n that are not the run-sums of any other composition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354910 Number of compositions of n that are the run-sums of some other composition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica