A352875 Number of integer compositions y of n with a fixed point y(i) = i.

0, 1, 1, 2, 5, 10, 21, 42, 86, 174, 351, 708, 1424, 2861, 5743, 11520, 23092, 46269, 92673, 185562, 371469, 743491, 1487870, 2977164, 5956616, 11916910, 23839736, 47688994, 95393322, 190811346, 381662507, 763389209, 1526881959, 3053930971, 6108131542, 12216698288

Offset

0,4

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Formula

a(n) = 2^(n-1) - A238351(n) for n >= 1. - Andrew Howroyd, Jan 02 2023

Example

The a(0) = 0 through a(5) = 10 compositions (empty column indicated by dot):
  .  (1)  (11)  (12)   (13)    (14)
                (111)  (22)    (32)
                       (112)   (113)
                       (121)   (122)
                       (1111)  (131)
                               (221)
                               (1112)
                               (1121)
                               (1211)
                               (11111)

Mathematica

pq[y_]:=Length[Select[Range[Length[y]], #==y[[#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], pq[#]>0&]], {n, 0, 15}]

Prog

(PARI)
S(v, u, c)={vector(#v, k, c + sum(i=1, k-1, v[k-i]*u[i]))}
seq(n)={my(v=vector(1+n), s=vector(#v, i, 2^(i-2))); v[1]=1; s[1]=0; for(i=1, n, v=S(v, vector(n, j, if(j==i, 'x, 1)), O(x)); s-=apply(p->polcoef(p, 0), v)); s} \\ Andrew Howroyd, Jan 02 2023

Crossrefs

The version for partitions is A001522, ranked by A352827 (unproved).

The version for permutations is A002467, complement A000166.

The complement for partitions is A064428, ranked by A352826 (unproved).

This is the sum of latter columns of A238349, nonfixed A352523.

The complement is counted by A238351.

The complement for reversed partitions is A238394, ranked by A352830.

The version for reversed partitions is A238395, ranked by A352872.

The case of just one fixed point is A240736.

A008290 counts permutations by fixed points, nonfixed A098825.

A011782 counts compositions.

A115720 and A115994 count partitions by Durfee square.

A238352 counts reversed partitions by fixed points, rank statistic A352822.

A352512 counts fixed points in standard compositions, nonfixed A352513.

A352521 = comps by subdiags, first col A219282, rank stat A352514.

A352522 = comps by weak subdiags, first col A238874, rank stat A352515.

A352524 = comps by superdiags, first col A008930, rank stat A352516.

A352525 = comps by weak superdiags, col k=1 A177510, rank stat A352517.

A352833 counts partitions by fixed points.

Cf. A006918, A008292, A088218, A114088, A123125, A188674, A257990.

Sequence in context: A280148 A215410 A279668 * A245747 A032283 A266248

Adjacent sequences: A352872 A352873 A352874 * A352876 A352877 A352878

Keyword

nonn

Author

Gus Wiseman, May 15 2022

Extensions

Terms a(21) and beyond from Andrew Howroyd, Jan 02 2023

Status

approved