n組並んでるところへ
n+1組めの夫婦を付け足す
と考えると、
2n人並んだスキマ2n+1箇所
(両端もアリ)から
異なる2箇所を選んで
夫と妻に割り振ればいい。
a[n+1]=a[n]・(2n+1)Ｐ2,
a[1]=2.
本当はa[1]=0なのだけれど、
n=1のときだけ夫婦が並んでよい
ように問題を改造すると、
a[1]→a[2]にも同じ漸化式が使えて
初期値の計算が簡単。
a[1]は、別扱いにしといて。