cp's OEIS Frontend

The case n=2 is a degenerate polygon (two sides connecting two vertices). The two possibilities are when the edges cross and do not cross. Polygons start at n=3 with a triangle.

Number of deranged matchings of 2n people with partners (of either sex) other than their spouse. 2n objects are initially paired in some way and then are re-paired so that no object is with its original partner (the dancing problem in the article).

Of interest in the "collision problem", where, given a 2-to-1 function f, we are asked for x, y such that f(x)=f(y).

2^n*n!*a(n) = (2n)! b(n) where b(n) are the probabilities that appear in Margolis (2001). One interpretation is in terms of matchings or 1-factors of the complete graph on 2n vertices. The number of these is (2n)!/2^{n}n!. The number of 1-factors being disjoint from (that is, having no edges in common with) a given 1-factor is then a(n); and then b(n) is the probability of picking such a disjoint one factor at random.

Also n!*a(n) = 2^n * c(n) where c(n) = A001499(n). If we define d(n,k) = k(n-1)(d(n-1,k) + d(n-2,k)), with d(0,k) = 1 and d(1,k) = 0, so d(n,1) are the derangement numbers A000166, then a(n) = d(n,2) (cf. A033030, A088991). On the other hand, taking d*(n,k) = d(n,k)/k^{n}, we have d*(n,k) = (n-1)(d*(n-1,k) + d*(n-2,k)/k), with d*(0,k) = 1 and d*(1,k) = 0 and it is easy to see from Bricard's recurrence for c(n) that c(n)/n! satisfies this for k = 2.

A proof that the description in the first comment as "number of deranged matchings" implies the defining recursion relation: let (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) be the given pairs. In a deranged matching x_1 will be paired with any of the 2(n-1) objects x_2, y_2, x_3, y_3, ..., x_n, y_n. It is sufficient to count only those deranged matchings in which x_1, is matched with x_2. They are of two kinds: (i) y_1 is not matched with y_2; their number is a(n-1); (ii) y_1 is matched with y_2; their number is a(n-2). - Emeric Deutsch, Jan 23 2009

Inverse binomial transform of the odd double factorials (A001147). - David Callan, Aug 25 2009

From Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009: (Start)

The formula is given directly by the Principle of Inclusion and Exclusion.

The first term includes all pairings, the second term excludes all pairings containing each pair, the third term includes all pairings containing each pair of pairs, and so on.

Based on n-a -> n for large n, the ratio a(n)/(2n-1)!! -> exp(-1/2) ~= 0.60653.

We find a(n)/(2n-1)!! for n= 100, 200, 300, 400 ~= 0.6050124904, 0.6057720290, 0.6060250088, 0.6061514604. (End)

This is a subset of the set of pairings of the first 2n integers (A001147) in another way: forbidding pairs of the form (2k,2k+1) for all k as well as the pair (1,2n) (seeing the constraint as circular by opposition to the linear A165968). - Olivier Gérard, Feb 08 2011

a(n) is the n-th central moment of a central chi-squared distribution (with 1 degree of freedom), i.e., a(n) = E[ (Y- E[Y] )^n ] = E[ (X^2 - 1 )^n ] where Y is chi-squared, X is std normal, X~N(0,1), and the expectation operator is E[]. - David Fioramonti, May 11 2016

Exponential self-convolution of a(n)/2^n gives subfactorials (A000166). - Vladimir Reshetnikov, Oct 09 2016

For n > 1, also the number of maximum matchings in the n-cocktail party graph. - Eric W. Weisstein, Jun 15 2017

Number of polygonal tiles with n sides with two exits per side and n edges connecting pairs of exits, with no edges between exits on the same side (cf. A289191, A289269 for nonisomorphic tiles under rotational and rotational and reflectional symmetries). - Marko Riedel, Jun 28 2017

Number of ways n people can hold hands (every hand is holding another hand) where no one is holding their own hand. - Harry Richman, Aug 29 2023

The case n=2 is a degenerate polygon (two sides connecting two vertices). The two possibilities are when the edges cross and do not cross. Polygons start at n=3 with a triangle.