今日のパズル

今日のパズルの時間(?)に出たような問題。

2n 個の数 1, 1, 2, 2, 3, 3, ..., n, n を次の条件を満たすように一列に並べよ。
[条件] k = 1, 2, ..., n に対して2つの k の間に他の数がちょうどk個ある。

n = 3 だったら 3, 1, 2, 1, 3, 2 等です。
さっきプログラム組んで、 n = 3, 4, 7, 8, 11, 12 のときの解を調べてみたら

n	解の個数
3	2
4	2
7	52
8	300
11	35584
12	216288

となりました。 解の個数には順序を逆にしたものも含みます。
さんざん悩んでやっと1つずつ見つけた n = 7, 8 の時の解がこんなにあるとは…。
それにしても必要性の証明だけして十分性の証明をしないのは生殺しですよ。 そんなもん自分で調べろって事でしょうけど。