A124762 Number of levels for compositions in standard order.

0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, 1, 1, 1, 2, 4, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 2, 2, 0, 0, 1, 3, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 2, 2, 2, 3, 5, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 1, 2, 1, 3, 0, 0, 1, 1, 1, 1, 2, 4, 0, 0, 0, 1, 1, 0, 0, 2, 0

Offset: 0

Author

Franklin T. Adams-Watters, Nov 06 2006

Keywords

• easy
• nonn
• tabf

Comments

The standard order of compositions is given by A066099.

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. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence gives the number of adjacent equal terms in the n-th composition in standard order. Alternatively, a(n) is one fewer than the number of maximal anti-runs in the same composition, where anti-runs are sequences without any adjacent equal terms. For example, the 1234567th composition in standard order is (3,2,1,2,2,1,2,5,1,1,1) with anti-runs ((3,2,1,2),(2,1,2,5,1),(1),(1)), so a(1234567) = 4 - 1 = 3. - Gus Wiseman, Apr 08 2020

Examples

			Composition number 11 is 2,1,1; 2>1=1, so a(11) = 1.
The table starts:
  0
  0
  0 1
  0 0 0 2
  0 0 1 1 0 0 1 3
  0 0 0 1 0 1 0 2 0 0 1 1 1 1 2 4
  0 0 0 1 1 0 0 2 0 0 2 2 0 0 1 3 0 0 0 1 0 1 0 2 1 1 2 2 2 2 3 5
		

Crossrefs

Cf. A066099, A124760, A124761, A124763, A124764, A011782 (row lengths), A059570 (row sums).

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):

- 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 A233564.

- Constant compositions are A272919.

- Normal compositions are A333217.

- Adjacent unequal pairs are counted by A333382.

- Anti-runs are 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[Select[Partition[stc[n],2,1],SameQ@@#&]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

Formula

For a composition b(1),...,b(k), a(n) = Sum_{1<=i=1

For n > 0, a(n) = A333381(n) - 1. - Gus Wiseman, Apr 08 2020

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.