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

Links

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

Wikipedia, Permutation

Formula

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

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

Example

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.

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);

Crossrefs

Main diagonal of A369596.

Cf. A000142, A000166, A008289, A331518.

Sequence in context: A065065 A020086 A151987 * A356485 A126149 A060927

Adjacent sequences: A369793 A369794 A369795 * A369797 A369798 A369799

Keyword

nonn

Author

Alois P. Heinz, Mar 02 2024

Status

approved