login
A370253
Number of deranged matchings of 2n people with partners (of either sex) such that at least one person is matched with their spouse.
2
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
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).
Sequence in context: A018927 A001266 A071971 * A337553 A006680 A197796
KEYWORD
nonn
AUTHOR
Sam Coutteau, Feb 13 2024
STATUS
approved