A352513 Number of nonfixed points in the n-th composition in standard order.

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

Offset

0,6

Comments

The k-th composition in standard order (graded reverse-lexicographic, 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. See also A000120, A059893, A070939, A114994, A225620.

A nonfixed point in a composition c is an index i such that c_i != i.

Links

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

Formula

A000120(n) = A352512(n) + A352513(n).

Example

The 169th composition in standard order is (2,2,3,1), with nonfixed points {1,4}, so a(169) = 2.

Mathematica

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

Crossrefs

The version counting permutations is A098825, fixed A008290.

Fixed points are counted by A352512, triangle A238349, first A238351.

The triangular version is A352523, first nontrivial column A352520.

A011782 counts compositions.

A352486 gives the nonfixed points of A122111, counted by A330644.

A352521 counts comps by strong nonexcedances, first A219282, stat A352514.

A352522 counts comps by weak nonexcedances, first col A238874, stat A352515.

A352524 counts comps by strong excedances, first col A008930, stat A352516.

A352525 counts comps by weak excedances, first col A177510, stat A352517.

Cf. A000700, A088218, A088902, A114088, A115994, A238352, A350841.

Sequence in context: A331981 A099302 A219198 * A025814 A029354 A035434

Adjacent sequences: A352510 A352511 A352512 * A352514 A352515 A352516

Keyword

nonn

Author

Gus Wiseman, Mar 27 2022

Status

approved