A333382 Number of adjacent unequal parts in the n-th composition in standard-order.

0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 0, 0, 1, 1, 1, 0, 2, 2, 1, 1, 2, 0, 1, 2, 3, 2, 1, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 1, 1, 2, 2, 2, 1, 1, 2

Offset

0,14

Comments

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, a(n) is one fewer than the number of maximal runs of 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) = A124767(n) - 1.

Example

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

Mathematica

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

Crossrefs

Indices of first appearances (not counting 0) are A113835.

Partitions whose 0-appended first differences are a run are A007862.

Partitions whose first differences are a run are A049988.

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

A triangle counting maximal runs of compositions is A238279.

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.

- Anti-runs are ranked by A333489.

- Anti-runs are counted by A333381.

Cf. A000005, A000120, A003242, A029931, A048793, A059893, A070939, A114994, A225620, A228351, A238424.

Sequence in context: A115953 A225245 A204770 * A143379 A254605 A335664

Adjacent sequences: A333379 A333380 A333381 * A333383 A333384 A333385

Keyword

nonn

Author

Gus Wiseman, Mar 24 2020

Status

approved