A369796 Number of permutations of [n] whose fixed points sum to n.

1, 1, 0, 1, 3, 13, 64, 406, 2737, 23044, 200509, 2078460, 22323513, 275402437, 3501602483, 50310672046, 739235942264, 12084285146335, 202054808987101, 3703410393626031, 69269248667062892, 1409725495837854024, 29169764518508360709, 651568557906956269430

Offset: 0

Author

Alois P. Heinz, Mar 02 2024

Keywords

• nonn

Examples

			a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(3) = 1: 213.
a(4) = 3: 1432, 2314, 3124.
a(5) = 13: 13542, 15243, 21435, 23415, 24135, 31425, 34125, 34215, 41235, 42351, 43125, 43215, 52314.
a(6) = 64: 123564, 123645, 132654, 134652, 136254, ..., 542136, 542316, 621435, 625413, 625431.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• Wikipedia, Permutation

Crossrefs

Main diagonal of A369596.

Cf. A000142, A000166, A008289, A331518.

Programs

Maple

g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..23);

Formula

a(n) = Sum_{k>=0} A000166(n-k)*A008289(n,k).

a(n) = A369596(n,n).