cp's OEIS Frontend

Also called the relaxed ménage problem (cf. A000179).

a(n) can be seen as a subset of the unordered pairings of the first 2n integers (A001147) with forbidden pairs (1,2n) and (i,i+1) for all i in [1,2n-1] (all adjacent integers modulo 2n). The linear version of this constraint is A000806. - Olivier Gérard, Feb 08 2011

Number of perfect matchings in the complement of C_{2n} where C_{2n} is the cycle graph on 2n vertices. - Andrew Howroyd, Mar 15 2016

Also the number of 2-uniform set partitions of {1...2n} containing no two cyclically successive vertices in the same block. - Gus Wiseman, Feb 27 2019

See the signed version of these numbers, A000806, for much more information about these numbers.

From Gus Wiseman, Feb 27 2019: (Start)

Also the number of 2-uniform set partitions of {1..2n} containing no two successive vertices in the same block. For example, the a(3) = 5 set partitions are:

{{1,3},{2,5},{4,6}}

{{1,4},{2,5},{3,6}}

{{1,4},{2,6},{3,5}}

{{1,5},{2,4},{3,6}}

{{1,6},{2,4},{3,5}}

(End)

From Gus Wiseman, Jul 05 2020: (Start)

Also the number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal and where the first i appears before the first j for i < j. For example, the a(3) = 5 permutations are the following.

(1,2,3,1,2,3)

(1,2,3,1,3,2)

(1,2,3,2,1,3)

(1,2,3,2,3,1)

(1,2,1,3,2,3)

(End)

From Gus Wiseman, Feb 27 2019: (Start)

Also the number of 2-uniform set partitions of {1..2n} such that no block has its two vertices differing by less than 3. For example, the a(4) = 10 set partitions are:

{{1,4}, {2,6}, {3,7}, {5,8}}

{{1,4}, {2,7}, {3,6}, {5,8}}

{{1,5}, {2,6}, {3,7}, {4,8}}

{{1,5}, {2,6}, {3,8}, {4,7}}

{{1,5}, {2,7}, {3,6}, {4,8}}

{{1,5}, {2,8}, {3,6}, {4,7}}

{{1,6}, {2,5}, {3,7}, {4,8}}

{{1,6}, {2,5}, {3,8}, {4,7}}

{{1,7}, {2,5}, {3,6}, {4,8}}

{{1,8}, {2,5}, {3,6}, {4,7}}

(End)

A cyclical form of A190823.

Also the number of 2-uniform set partitions of {1...2n} such that, when the vertices are arranged uniformly around a circle, no block has its two vertices separated by an arc length of less than 3.

Columns k=0 and k=1 respectively give A000012 and A000085(n)-A170941(n).

Row sums give A000085.

Diagonal T(2n,n) gives A005493(n-1) for n>0.

Reversed rows converge to A005493.

T(n,k) is defined for all n, k >= 0: T(n,k) = 1 for k >= n.

Columns k=0 and k=1 respectively give A000085 and A170941 (involutions on [n] without adjacent transpositions).

Diagonal T(2n,n) gives A000110(n).

Also the number of spanning subgraphs of the complement of an n-cycle, with no overlapping edges.

I.e., for n >= 3, also the number of matchings in the complement of the cycle graph C_n. - Eric W. Weisstein, Sep 02 2025

T(n,k) is the number of involutions on [n] containing exactly k adjacent transpositions. The Mathematica recurrence below is based on considerations and manipulations similar to those in the Stadler and Haslinger reference for the case k=0 (Theorem 5 in Section 3).

It appears that each column is a palindromic linear combination of the entries a[n] := T(n,0) in column 0:

T(n,1) = a[n] - a[n-1] + a[n-2],

T(n,2) = (a[n] - 2 a[n-1] + 2 a[n-2] - 2 a[n-3] + a[n-4])/2,

T(n,3) = (a[n] - 3 a[n-1] + 3 a[n-2] - 4 a[n-3] + 3 a[n-4] - 3 a[n-5] + a[n-6])/6,

T(n,4) = (a[n] - 4 a[n - 1] + 4 a[n - 2] - 4 a[n - 3] + 4 a[n - 4] - 4 a[n - 5] + 4 a[n - 6] - 4 a[n - 7] + a[n - 8])/24,

T(n,5) = (a[n] - 5 a[n - 1] + 5 a[n - 2] + 4 a[n - 5] + 5 a[n - 8] - 5 a[n - 9] + a[n - 10])/120.

It appears that each diagonal is a polynomial function: topmost entries are 1, second entries are k+1, third entries are (k+1)^2, fourth entries are 1/3 (1 + k) (2 + k) (3 + 2 k), fifth entries are 1/12 (1 + k) (2 + k) (30 + 23 k + 5 k^2), sixth entries are 1/60 (1 + k) (2 + k) (3 + k) (130 + 77 k + 13 k^2), seventh entries are 1/180 (1 + k) (2 + k) (3 + k) (1110 + 821 k + 210 k^2 + 19 k^3).

Conjecture: The asymptotic distribution of adjacent transpositions in involutions is Poisson with mean 1.