%I #27 Mar 04 2024 10:33:34
%S 1,1,0,1,3,13,64,406,2737,23044,200509,2078460,22323513,275402437,
%T 3501602483,50310672046,739235942264,12084285146335,202054808987101,
%U 3703410393626031,69269248667062892,1409725495837854024,29169764518508360709,651568557906956269430
%N Number of permutations of [n] whose fixed points sum to n.
%H Alois P. Heinz, <a href="/A369796/b369796.txt">Table of n, a(n) for n = 0..450</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%F a(n) = Sum_{k>=0} A000166(n-k)*A008289(n,k).
%F a(n) = A369596(n,n).
%e a(0) = 1: the empty permutation.
%e a(1) = 1: 1.
%e a(3) = 1: 213.
%e a(4) = 3: 1432, 2314, 3124.
%e a(5) = 13: 13542, 15243, 21435, 23415, 24135, 31425, 34125, 34215, 41235, 42351, 43125, 43215, 52314.
%e a(6) = 64: 123564, 123645, 132654, 134652, 136254, ..., 542136, 542316, 621435, 625413, 625431.
%p g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
%p b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
%p `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
%p end:
%p a:= n-> b(n$3):
%p seq(a(n), n=0..23);
%Y Main diagonal of A369596.
%Y Cf. A000142, A000166, A008289, A331518.
%K nonn
%O 0,5
%A _Alois P. Heinz_, Mar 02 2024
|