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