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,7

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.

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 fixed points {2,3}, so a(169) = 2.

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

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.

Sequence in context: A031267 A247763 A065360 * A364032 A333397 A101676

Adjacent sequences: A352509 A352510 A352511 * A352513 A352514 A352515

Keyword

nonn

Author

Gus Wiseman, Mar 26 2022

Status

approved