A329869 - OEIS

A329869

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

%I #4 Nov 24 2019 10:00:52

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

%T 40754

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

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

%C 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.

%C 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.

%H Claude Lenormand, <a href="/A318921/a318921.pdf">Deux transformations sur les mots</a>, Preprint, 5 pages, Nov 17 2003.

%e The a(1) = 1 through a(9) = 19 compositions:

%e 1 2 3 4 5 6 7 8 9

%e 11 22 33 11113 44 11115

%e 11112 31111 11114 12222

%e 21111 111211 41111 22221

%e 112111 111122 51111

%e 111311 111222

%e 113111 111411

%e 211112 114111

%e 221111 211113

%e 1111121 222111

%e 1211111 311112

%e 1111131

%e 1111221

%e 1112112

%e 1121112

%e 1221111

%e 1311111

%e 2111211

%e 2112111

%e 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).

%t runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;

%t degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],runsres[#]+1==degdep[#]&]],{n,0,10}]

%Y The version for binary indices is A329866.

%Y Compositions counted by runs-resistance are A329744.

%Y Compositions counted by cuts-resistance are A329861.

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

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Nov 23 2019