cp's OEIS Frontend

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

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