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

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, 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, 1, 1, 1, 3, 1, 2, 2, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 3, 2

Offset: 0

Author

Gus Wiseman, Mar 24 2020

Keywords

• nonn

Comments

Anti-runs are sequences without any adjacent equal terms.

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.

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

Examples

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

Links

• Wikipedia, Longest increasing subsequence

Crossrefs

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

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

A triangle counting maximal runs of compositions is A238279.

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

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

- Adjacent equal pairs are counted by A124762.

- Weakly decreasing runs are counted by A124765.

- Weakly increasing runs are counted by A124766.

- Equal runs are counted by A124767.

- Strictly increasing runs are counted by A124768.

- Strictly decreasing runs are counted by A124769.

- Strict compositions are ranked by A233564.

- Constant compositions are ranked by A272919.

- Normal compositions are ranked by A333217.

- Adjacent unequal pairs are counted by A333382.

- Anti-runs are ranked by A333489.

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

Programs

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Split[stc[n],UnsameQ]],{n,0,100}]

Formula

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