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,4

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.

Links

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

Wikipedia, Longest increasing subsequence

Formula

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

Example

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

Mathematica

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

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.

Sequence in context: A285706 A357181 A357137 * A124094 A101950 A104562

Adjacent sequences: A333378 A333379 A333380 * A333382 A333383 A333384

Keyword

nonn

Author

Gus Wiseman, Mar 24 2020

Status

approved