A089039 Number of circular permutations of 2n letters that are free of jealousy.

1, 2, 6, 60, 960, 24000, 861840, 42104160, 2686763520, 217039253760, 21651071904000, 2614084251609600, 375698806311628800, 63383303286471168000, 12403896267489382656000, 2786994829444848422400000, 712575504763406361133056000

Offset: 1

Author

Akemi Nakamura, Michihiro Takahashi, Shogaku Meitantei (naka(AT)sansu.org), Dec 03 2003

Keywords

• nonn
• nice

Comments

The number of circular permutations of 2*n people consisting of n married couples, such that no one sits next to a person of the opposite sex who is not his or her spouse.

Limit_{n->oo} a(n)/(n-1)!^2 = Sum_{k>=1} 1/(k!*(k-1)!) = 1.590636854637329063382254424999666247954478159495536647132... (A096789).

Examples

			a(3)=6 because ABCcba, ACBbca, ABbacC, ACcabB, AabcCB, AacbBC are possible.
		

Links

• Eiji Kurihara, Small room of mathematics; see the answer for No. 380 of arithmetic challenges version 1.
• Mikhail Kurkov and others, On a A089039 and pair of sequences with simple recursion, Math Overflow, Apr 20 2024
• Masaru Yoshikawa, Arithmetic challenges. See problem No. 380.

Programs

Mathematica

a[1] = 1; a[n_] := n!*(n-2)!*HypergeometricPFQ[{1-n/2, 3/2-n/2}, {2, 2-n, 2-n}, 4]; Table[a[n], {n, 1, 17}] (* Jean-François Alcover, Oct 30 2013, after symbolic sum *)

PARI

a(n) = if (n==1, 1, sum (k=1, n\2, n!*(n-k-1)!^2/((k-1)!^2*(n-2*k)!*k))); \\ Michel Marcus, Sep 03 2013

Formula

a(1)=1, a(n) = Sum_{k=1..floor(n/2)} n!*(n-k-1)!^2/((k-1)!^2*(n-2*k)!*k) for n > 1.

a(n) = (n-1)!*(A001040(n-1) + A001053(n)) = 2*A276356(n), n > 1. - Conjectured by Mikhail Kurkov, Feb 10 2019 and proved by Max Alekseyev, Apr 23 2024 (see MO link)

a(n+4) = -(n+3)*(n+2)*(n*(n+1)*a(n) + 2*(n+1)^2*a(n+1) + n*(n+3)*a(n+2) - 2*a(n+3)) for all integer n>1. - conjectured by Michael Somos, Apr 21 2024. [The conjecture is equivalent to Kurkov's formula and thus is also proved. - Max Alekseyev, Apr 23 2024]