A352512 Number of fixed points in the n-th composition in standard order.

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

Offset: 0

Author

Gus Wiseman, Mar 26 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 fixed point of composition c is an index i such that c_i = i.

Examples

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

Crossrefs

The version counting permutations is A008290, unfixed A098825.

The triangular version is A238349, first column A238351.

Unfixed points are counted by A352513, triangle A352523, first A352520.

A011782 counts compositions.

A088902 gives the fixed points of A122111, counted by A000700.

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. A088218, A114088, A115994, A238352, A330644, A350841, A352486.

Programs

Mathematica

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

Formula

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