login
Number of compositions of n with the same runs-resistance as cuts-resistance.
7

%I #8 Nov 24 2019 10:00:09

%S 1,0,0,0,0,2,5,10,17,27,68,107,217,420,884,1761,3679,7469,15437,31396,

%T 64369

%N Number of compositions of n with the same runs-resistance as cuts-resistance.

%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(5) = 2 through a(8) = 17 compositions:

%e (1112) (1113) (1114) (1115)

%e (2111) (1122) (1222) (1133)

%e (2211) (2221) (3311)

%e (3111) (4111) (5111)

%e (11211) (11122) (11222)

%e (11311) (11411)

%e (21112) (12221)

%e (22111) (21113)

%e (111121) (22211)

%e (121111) (31112)

%e (111131)

%e (111221)

%e (112112)

%e (112211)

%e (122111)

%e (131111)

%e (211211)

%e For example, the runs-resistance of (111221) is 3 because we have: (111221) -> (321) -> (111) -> (3), while the cuts-resistance is also 3 because we have: (111221) -> (112) -> (1) -> (), so (111221) is counted under a(8).

%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[#]==degdep[#]&]],{n,0,10}]

%Y The version for binary expansion is A329865.

%Y Compositions counted by runs-resistance are A329744.

%Y Compositions counted by cuts-resistance are A329861.

%Y Compositions with runs-resistance = cuts-resistance minus 1 are A329869.

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

%K nonn,more

%O 0,6

%A _Gus Wiseman_, Nov 23 2019