login
Number of maximal anti-runs of the n-th composition in standard order.
112

%I #9 Mar 24 2020 22:30:02

%S 0,1,1,2,1,1,1,3,1,1,2,2,1,1,2,4,1,1,1,2,1,2,1,3,1,1,2,2,2,2,3,5,1,1,

%T 1,2,2,1,1,3,1,1,3,3,1,1,2,4,1,1,1,2,1,2,1,3,2,2,3,3,3,3,4,6,1,1,1,2,

%U 1,1,1,3,1,2,2,2,1,1,2,4,1,1,1,2,2,3,2

%N Number of maximal anti-runs of the n-th composition in standard order.

%C Anti-runs are sequences without any adjacent equal terms.

%C A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of 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.

%C For n > 0, also one plus the number of adjacent equal pairs in the n-th composition in standard order.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>

%F For n > 0, a(n) = A124762(n) + 1.

%e The 46th composition in standard order is (2,1,1,2), with maximal anti-runs ((2,1),(1,2)), so a(46) = 2.

%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t Table[Length[Split[stc[n],UnsameQ]],{n,0,100}]

%Y Anti-runs summing to n are counted by A003242(n).

%Y A triangle counting maximal anti-runs of compositions is A106356.

%Y A triangle counting maximal runs of compositions is A238279.

%Y Partitions whose first differences are an anti-run are A238424.

%Y All of the following pertain to compositions in standard order (A066099):

%Y - Adjacent equal pairs are counted by A124762.

%Y - Weakly decreasing runs are counted by A124765.

%Y - Weakly increasing runs are counted by A124766.

%Y - Equal runs are counted by A124767.

%Y - Strictly increasing runs are counted by A124768.

%Y - Strictly decreasing runs are counted by A124769.

%Y - Strict compositions are ranked by A233564.

%Y - Constant compositions are ranked by A272919.

%Y - Normal compositions are ranked by A333217.

%Y - Adjacent unequal pairs are counted by A333382.

%Y - Anti-runs are ranked by A333489.

%Y Cf. A000120, A029931, A048793, A059893, A070939, A114994, A225620, A228351.

%K nonn

%O 0,4

%A _Gus Wiseman_, Mar 24 2020