A329869 Number of compositions of n with runs-resistance equal to cuts-resistance minus 1.

0, 1, 2, 1, 2, 1, 4, 5, 11, 19, 36, 77, 138, 252, 528, 1072, 2204, 4634, 9575, 19732, 40754

Offset

0,3

Comments

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

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.

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.

Links

Table of n, a(n) for n=0..20.

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

Example

The a(1) = 1 through a(9) = 19 compositions:
  1   2   3   4   5   6      7       8        9
      11      22      33     11113   44       11115
                      11112  31111   11114    12222
                      21111  111211  41111    22221
                             112111  111122   51111
                                     111311   111222
                                     113111   111411
                                     211112   114111
                                     221111   211113
                                     1111121  222111
                                     1211111  311112
                                              1111131
                                              1111221
                                              1112112
                                              1121112
                                              1221111
                                              1311111
                                              2111211
                                              2112111
For example, the runs-resistance of (1221111) is 3 because we have: (1221111) -> (124) -> (111) -> (3), while the cuts-resistance is 4 because we have: (1221111) -> (2111) -> (11) -> (1) -> (), so (1221111) is counted under a(9).

Mathematica

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

Crossrefs

The version for binary indices is A329866.

Compositions counted by runs-resistance are A329744.

Compositions counted by cuts-resistance are A329861.

Cf. A003242, A098504, A114901, A242882, A318928, A319411, A319416, A319420, A319421, A329864, A329865, A329867, A329868.

Sequence in context: A143591 A085063 A263078 * A331188 A058511 A331982

Adjacent sequences: A329866 A329867 A329868 * A329870 A329871 A329872

Keyword

nonn,more

Author

Gus Wiseman, Nov 23 2019

Status

approved