A329744 -id:A329744 - cp's OEIS frontend

A329870 Runs-resistance of the binary expansion of n without the first digit.

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

Offset: 2

Gus Wiseman, Nov 25 2019

nonn

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.

			Minimal representatives with each image are:
    2: (0)
    4: (0,0) -> (2)
    5: (0,1) -> (1,1) -> (2)
    9: (0,0,1) -> (2,1) -> (1,1) -> (2)
   18: (0,0,1,0) -> (2,1,1) -> (1,2) -> (1,1) -> (2)
   41: (0,1,0,0,1) -> (1,1,2,1) -> (2,1,1) -> (1,2) -> (1,1) -> (2)
  150: (0,0,1,0,1,1,0) -> (2,1,1,2,1) -> (1,2,1,1) -> (1,1,2) -> (2,1) -> (1,1) -> (2)

Keeping the first digit gives A318928.
Cuts-resistance is A319420.
Compositions counted by runs-resistance are A329744.
Binary words counted by runs-resistance are A319411 and A329767.
Cf. A107907, A319416, A329860, A329861, A329865, A329867.

Table[Length[NestWhileList[Length/@Split[#]&,Rest[IntegerDigits[n,2]],Length[#]>1&]]-1,{n,2,100}]

A329743 Number of compositions of n with runs-resistance n - 3.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 9, 16, 8

Offset: 0

Gus Wiseman, Nov 21 2019

A composition of n is a finite sequence of positive integers with sum n.

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.

			The a(3) = 1 through a(8) = 8 compositions:
  (3)  (22)    (14)   (114)    (1123)    (12113)
       (1111)  (23)   (411)    (1132)    (12212)
               (32)   (1113)   (1141)    (13112)
               (41)   (1221)   (1411)    (21131)
               (131)  (2112)   (2122)    (21221)
               (212)  (3111)   (2212)    (31121)
                      (11112)  (2311)    (121112)
                      (11211)  (3211)    (211121)
                      (21111)  (11131)
                               (11212)
                               (11221)
                               (12211)
                               (13111)
                               (21211)
                               (111121)
                               (121111)
For example, repeatedly taking run-lengths starting with (1,2,1,1,3) gives (1,2,1,1,3) -> (1,1,2,1) -> (2,1,1) -> (1,2) -> (1,1) -> (2), which is 5 steps, and 5 = 8 - 3, so (1,2,1,1,3) is counted under a(8).

Column k = n - 3 of A329744.
Column k = 3 of A329750.
Compositions with runs-resistance 2 are A329745.
Cf. A000740, A008965, A098504, A242882, A318928, A329746, A329747, A329767.

runsres[q_]:=If[Length[q]==1,0,Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],runsres[#]==n-3&]],{n,10}]

A332871 Number of compositions of n whose run-lengths are not weakly increasing.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 8, 24, 55, 128, 282, 625, 1336, 2855, 6000, 12551, 26022, 53744, 110361, 225914, 460756, 937413, 1902370, 3853445, 7791647, 15732468, 31725191, 63907437, 128613224, 258626480, 519700800, 1043690354, 2094882574, 4202903667, 8428794336, 16897836060

Offset: 0

Gus Wiseman, Feb 29 2020

nonn

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

Also compositions whose run-lengths are not weakly decreasing.

			The a(4) = 1 through a(6) = 8 compositions:
  (112)  (113)   (114)
         (221)   (1113)
         (1112)  (1131)
         (1121)  (1221)
                 (2112)
                 (11112)
                 (11121)
                 (11211)
For example, the composition (2,1,1,2) has run-lengths (1,2,1), which are not weakly increasing, so (2,1,1,2) is counted under a(6).

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The version for the compositions themselves (not run-lengths) is A056823.
The version for unsorted prime signature is A112769, with dual A071365.
The case without weakly decreasing run-lengths either is A332833.
The complement is counted by A332836.
Compositions that are not unimodal are A115981.
Compositions with equal run-lengths are A329738.
Compositions whose run-lengths are not unimodal are A332727.
Cf. A001523, A072704, A100883, A181819, A329744, A329766, A332641, A332669, A332726, A332745, A332746, A332834, A332835.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!LessEqual@@Length/@Split[#]&]],{n,0,10}]

a(n) = 2^(n - 1) - A332836(n).

Terms a(21) and beyond from Andrew Howroyd, Dec 30 2020

A329768 Number of finite sequences of positive integers whose sum minus runs-resistance is n.

Original entry on oeis.org

8, 17, 42, 104, 242, 541, 1212, 2664, 5731, 12314

Offset: 1

Gus Wiseman, Nov 21 2019

A composition of n is a finite sequence of positive integers with sum n.

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.

			The a(1) = 8 and a(2) = 17 compositions whose sum minus runs-resistance is n:
  (1)        (2)
  (1,1)      (1,3)
  (1,2)      (3,1)
  (2,1)      (1,1,1)
  (1,1,2)    (1,1,3)
  (2,1,1)    (1,2,1)
  (1,1,2,1)  (1,2,2)
  (1,2,1,1)  (2,2,1)
             (3,1,1)
             (1,1,1,2)
             (1,1,3,1)
             (1,3,1,1)
             (2,1,1,1)
             (1,1,1,2,1)
             (1,2,1,1,1)
             (1,2,1,1,2)
             (2,1,1,2,1)

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Column sums of A329750.

Cf. A000740, A008965, A098504, A242882, A318928, A329744, A329745, A329746, A329747, A329767.

A330028 Number of compositions of n with cuts-resistance <= 2.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 23, 45, 86, 159, 303, 568, 1069, 2005, 3769, 7066, 13251, 24821, 46482, 86988, 162758

Offset: 0

Gus Wiseman, Nov 27 2019

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

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)

Sum of first three columns of A329861.
Compositions with cuts-resistance 1 are A003242.
Compositions with cuts-resistance 2 are A329863.
Compositions with runs-resistance 2 are A329745.
Numbers whose binary expansion has cuts-resistance 2 are A329862.
Binary words with cuts-resistance 2 are A027383.
Cuts-resistance of binary expansion is A319416.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]<=2&]],{n,0,10}]

A330937 Number of strictly recursively normal integer partitions of n.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 15, 20, 27, 35, 49, 58, 81, 100, 126, 160, 206, 246, 316, 374, 462, 564, 696, 813, 1006, 1195, 1441, 1701, 2058, 2394, 2896, 3367, 4007, 4670, 5542, 6368, 7540, 8702, 10199, 11734, 13760, 15734, 18384, 21008, 24441, 27893, 32380, 36841

Offset: 0

Gus Wiseman, Mar 09 2020

nonn

A sequence is strictly recursively normal if either it empty, its run-lengths are distinct (strict), or its run-lengths cover an initial interval of positive integers (normal) and are themselves a strictly recursively normal sequence.

			The a(1) = 1 through a(9) = 15 partitions:
  (1)  (2)  (3)   (4)    (5)    (6)    (7)     (8)     (9)
            (21)  (31)   (32)   (42)   (43)    (53)    (54)
                  (211)  (41)   (51)   (52)    (62)    (63)
                         (221)  (321)  (61)    (71)    (72)
                         (311)  (411)  (322)   (332)   (81)
                                       (331)   (422)   (432)
                                       (421)   (431)   (441)
                                       (511)   (521)   (522)
                                       (3211)  (611)   (531)
                                               (3221)  (621)
                                               (4211)  (711)
                                                       (3321)
                                                       (4221)
                                                       (4311)
                                                       (5211)
                                                       (32211)

The narrow instead of strict version is A332272.
A wide instead of strict version is A332295(n) - 1 for n > 1.
Cf. A107429, A181819, A316496, A317081, A317245, A317491, A329744, A329746, A329766, A332277, A332576.

normQ[m_]:=m=={}||Union[m]==Range[Max[m]];
recnQ[ptn_]:=With[{qtn=Length/@Split[ptn]},Or[ptn=={},UnsameQ@@qtn,And[normQ[qtn],recnQ[qtn]]]];
Table[Length[Select[IntegerPartitions[n],recnQ]],{n,0,30}]

A335518 Number of matching pairs of patterns, the first of length n and the second of length k.

Original entry on oeis.org

1, 1, 1, 3, 3, 3, 13, 13, 25, 13, 75, 75, 185, 213, 75, 541, 541, 1471, 2719, 2053, 541, 4683, 4683, 13265, 32973, 40367, 22313, 4683, 47293, 47293, 136711, 408265, 713277, 625295, 271609, 47293

Offset: 0

Gus Wiseman, Jun 23 2020

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			Triangle begins:
     1
     1     1
     3     3     3
    13    13    25    13
    75    75   185   213    75
   541   541  1471  2719  2053   541
  4683  4683 13265 32973 40367 22313  4683
Row n =2 counts the following pairs:
  ()<=(1,1)  (1)<=(1,1)  (1,1)<=(1,1)
  ()<=(1,2)  (1)<=(1,2)  (1,2)<=(1,2)
  ()<=(2,1)  (1)<=(2,1)  (2,1)<=(2,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Columns k = 0 and k = 1 are both A000670.
Row sums are A335517.
Patterns are ranked by A333217.
Patterns matched by a standard composition are counted by A335454.
Patterns contiguously matched by compositions are counted by A335457.
Minimal patterns avoided by a standard composition are counted by A335465.
Patterns matched by prime indices are counted by A335549.
Cf. A011782, A034691, A056986, A124771, A269134, A329744, A333257, A334299.

mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Union[mstype/@Subsets[y,{k}]]],{y,Join@@Permutations/@allnorm[n]}],{n,0,5},{k,0,n}]

A375408 Numbers k such that the k-th composition in standard order is not weakly increasing or weakly decreasing.

Original entry on oeis.org

13, 22, 25, 27, 29, 38, 41, 44, 45, 46, 49, 50, 51, 53, 54, 55, 57, 59, 61, 70, 76, 77, 78, 81, 82, 83, 86, 88, 89, 90, 91, 92, 93, 94, 97, 98, 99, 101, 102, 103, 105, 107, 108, 109, 110, 111, 113, 114, 115, 117, 118, 119, 121, 123, 125, 134, 140, 141, 142

Offset: 1

Gus Wiseman, Sep 18 2024

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.

			The terms and corresponding compositions begin:
  13: (1,2,1)
  22: (2,1,2)
  25: (1,3,1)
  27: (1,2,1,1)
  29: (1,1,2,1)
  38: (3,1,2)
  41: (2,3,1)
  44: (2,1,3)
  45: (2,1,2,1)
  46: (2,1,1,2)
  49: (1,4,1)
  50: (1,3,2)
  51: (1,3,1,1)
  53: (1,2,2,1)
  54: (1,2,1,2)
  55: (1,2,1,1,1)
  57: (1,1,3,1)
  59: (1,1,2,1,1)

Eric Weisstein's World of Mathematics, Unimodal Sequence.

The version for run-lengths of compositions is A332833.
Compositions of this type are counted by A332834, complement maybe A329398.
A001523 counts unimodal compositions, ranks too dense.
A011782 counts compositions.
A114994 ranks weakly decreasing compositions, complement A335485.
A115981 counts non-unimodal compositions, ranked by A335373.
A225620 ranks weakly increasing compositions, complement A335486.
A238130, A238279, A333755 count compositions by number of runs.
A332835 counts compositions with weakly incr. or weakly decr. run-lengths.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1).
- Parts are listed by A066099.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of strict compositions are A233564.
- Ranks of constant compositions are A272919.
- Anti-runs are ranked by A333489, counted by A003242.
- Run-length transform is A333627, sum A070939.
Cf. A001511, A002051, A065120, A329744, A332745, A332836, A332870, A333218.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!LessEqual@@stc[#]&&!GreaterEqual@@stc[#]&]

Intersection of A335485 and A335486.

cp's OEIS Frontend

A329870 Runs-resistance of the binary expansion of n without the first digit.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329743 Number of compositions of n with runs-resistance n - 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A332871 Number of compositions of n whose run-lengths are not weakly increasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A329768 Number of finite sequences of positive integers whose sum minus runs-resistance is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A330028 Number of compositions of n with cuts-resistance <= 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330937 Number of strictly recursively normal integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A335518 Number of matching pairs of patterns, the first of length n and the second of length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A375408 Numbers k such that the k-th composition in standard order is not weakly increasing or weakly decreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula