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

Author

Gus Wiseman, Mar 24 2020

Keywords

• nonn

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.

Examples

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

Links

• Wikipedia, Longest increasing subsequence

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.

Programs

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}]

Formula

For n > 0, a(n) = A124767(n) - 1.