A378100 Number of involutions in the symmetric group S_n with at least one fixed point.
0, 1, 1, 4, 7, 26, 61, 232, 659, 2620, 8551, 35696, 129757, 568504, 2255345, 10349536, 44179711, 211799312, 962854399, 4809701440, 23103935021, 119952692896, 605135328337, 3257843882624, 17175956434375, 95680443760576, 525079354619951, 3020676745975552
Offset: 0
Examples
a(4) = 7: (1,2)(3)(4), (1,3)(2)(4), (1,4)(2)(3), (1)(2,3)(4), (1)(2,4)(3), (1)(2)(3,4), (1)(2)(3)(4).
Crossrefs
Programs
-
Maple
a := proc(n) local k, total, deranged; total := add(factorial(n)/(factorial(n-2*k)*2^k*factorial(k)), k=0..floor(n/2)); if mod(n, 2) = 0 then deranged := factorial(n)/(2^(n/2)*factorial(n/2)); else deranged := 0; end if; return total - deranged; end proc: seq(a(n), n=1..20); # second Maple program: a:= proc(n) option remember; `if`(n<4, [0, 1$2, 4][n+1], a(n-1)+(2*n-3)*a(n-2)-(n-2)*(a(n-3)+(n-3)*a(n-4))) end: seq(a(n), n=0..27); # Alois P. Heinz, Nov 24 2024 -
Mathematica
a[n_] := Module[{total, deranged}, total = Sum[n! / ((n - 2 k)! * 2^k * k!), {k, 0, Floor[n/2]}]; deranged = If[EvenQ[n], n! / (2^(n/2) * (n/2)!), 0]; total - deranged ]; Table[a[n], {n, 1, 20}] -
PARI
my(x='x+O('x^30)); Vec(serlaplace(exp(x+x^2/2)-exp(x^2/2))) \\ Joerg Arndt, Nov 27 2024 -
Python
from math import factorial def a(n): total = sum(factorial(n) // (factorial(n - 2 * k) * 2**k * factorial(k)) for k in range(n // 2 + 1)) deranged = factorial(n) // (2**(n // 2) * factorial(n // 2)) if n % 2 == 0 else 0 return total - deranged print([a(n) for n in range(1, 21)])
Formula
a(n) = Sum_{k=0..floor(n/2)} n! / ((n-2k)! * 2^k * k!) - (n! / (2^(n/2) * (n/2)!) * (1 - (n mod 2))).
a(n) = A000085(n) for odd n.
From Alois P. Heinz, Nov 24 2024: (Start)
E.g.f.: exp(x*(2+x)/2)-exp(x^2/2).
a(n) = Sum_{k=1..n} A099174(n,k). (End)
Comments