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

Links

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

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

Example

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.

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

Prog

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

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.

Sequence in context: A018927 A001266 A071971 * A337553 A006680 A197796

Adjacent sequences: A370250 A370251 A370252 * A370254 A370255 A370256

Keyword

nonn

Author

Sam Coutteau, Feb 13 2024

Status

approved