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

Comments

In other words, a(n) is the number of involutions in S_n that are not derangements.

Links

Table of n, a(n) for n=0..27.

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) - A123023(n).

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)

Example

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

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}]

Prog

(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)])
(PARI) my(x='x+O('x^30)); Vec(serlaplace(exp(x+x^2/2)-exp(x^2/2))) \\ Joerg Arndt, Nov 27 2024

Crossrefs

Cf. A000085 (involutions), A000166 (derangements), A002467 (permutations with a fixed point), A099174, A123023 (involutions that are derangements).

Sequence in context: A110413 A075686 A077441 * A269744 A303844 A197789

Adjacent sequences: A378097 A378098 A378099 * A378101 A378102 A378103

Keyword

nonn,easy

Author

Maniru Ibrahim, Nov 16 2024

Status

approved