OFFSET
1,2
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).
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.
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]
EXAMPLE
a(3)=6 because ABCcba, ACBbca, ABbacC, ACcabB, AabcCB, AacbBC are possible.
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Akemi Nakamura, Michihiro Takahashi, Shogaku Meitantei (naka(AT)sansu.org), Dec 03 2003
STATUS
approved