4組8人の夫婦が一列に並ぶとき夫婦同士が隣り合わない並び方を求めるのに、樹形図を書いて
ABABCDCD
ABACBDCD
ABACDBCD
ABACDBDC
ABACDCBD
ABACDCDB
ABCAD**D (** はBC順不同)
ABCAD*D* (** はBC順不同)
ABCAD**D (** はBC順不同)
ABCBD*D* (** はAC順不同)
ABCBD**D (** はAC順不同)
ABCB*D*D (** はAC順不同)
ABCDA*** (*** はBCD順不同)
ABCDB*** (*** はACD順不同)
ABCDC*** (*** はABD順不同)

A〜Dに実際の夫婦名を割り当てさらに男女の区別をして
36 * 4! * 2^4 = 13824通りとしましたが
漸化式とかでうまく解く方法はありませでしょうか？