A370253 Number of deranged matchings of 2n people with partners (of either sex) such that at least one person is matched with their spouse.

0, 1, 1, 7, 45, 401, 4355, 56127, 836353, 14144545, 267629139, 5601014255, 128455425593, 3203605245777, 86317343312395, 2498680706048191, 77336483434140705, 2548534969132415297, 89087730603300393443, 3292572900736818264015, 128281460895447809211529

Offset: 0

Author

Sam Coutteau, Feb 13 2024

Keywords

• nonn

Examples

			For n=0, there is no matching which has at least one person matched with their original partner.
For n=1, there are only 2 people, so there is only one way to match them and it is with their original partner.
For n=2, we have two couples, A0 with A1, and B0 with B1. Of the three ways to match them [(A0,A1),(B0,B1)], [(A0,B0),(A1,B1)] and [(A0,B1),(A1,B0)], only the first matching has a person matched up with their original partner.
		

Links

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

Crossrefs

Cf. A001147 (total number of matchings for 2n people).

Cf. A053871 (number of deranged matchings of 2n people with partners (of either sex) other than their spouse).

Cf. A055140, A057427.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, signum(n),
      (4*n-7)*a(n-1)-2*(2*n^2-10*n+11)*a(n-2)-2*(n-2)*(2*n-5)*a(n-3))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 14 2024

Mathematica

a[n_] := Sum[(-1)^(n-i+1)*Binomial[n, i]*(2i-1)!!, {i, 0, n-1}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 29 2024 *)

Python

import math
A001147 = lambda i: math.factorial(2*i) // ( 2 ** i * math.factorial(i) )
A370253 = lambda n: int( sum( (-1)**(i+1) * math.comb(n,n-i) * A001147(n-i) for i in range(1,n+1) ) )
print( ", ".join( str(A370253(i)) for i in range(0,21) ) )

Formula

a(n) = A001147(n) - A053871(n).

a(n) = Sum_{i=0..n-1} (-1)^(n - i + 1) * binomial(n,i)*A001147(i).

a(n) mod 2 = A057427(n).

a(n) = Sum_{k=1..n} A055140(n,k). - Alois P. Heinz, Feb 14 2024