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

Author

Gus Wiseman, Mar 27 2022

Keywords

• nonn

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.

Examples

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

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.

Programs

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

Formula

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