ちょっかいスズメ　　　　　　　　　　　　　 　　　　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２７年５月２４日付け）

　スズメの雄は隣に他の番の雌のスズメがやってくると、見境もなく、ちょっかいを出すとい
う習慣があった。スズメの世界ではいつもこれが原因で諍いが絶えなかった。そこで、スズ
メの王様がお触れを出して、平和な日々が送れるように次の決まりを立てた。

（１）雌は他の雌の隣には並んでよい。
（２）自分の番の雄の隣なら並んでよい。

従って、二組の番（A,a,B,b)<大文字：雄、小文字：雌＞が電線に止まる時は、

　　A,a,b,B　、A,B,b,a　、B,A,a,b　、B,b,a,A　、a,A,B,b　、a,b,B,A　、b,a,A,B　、b,B,A,a

の８通りは許されるが、他の並びは禁止となった。

　さて今、三組、四組、五組のスズメの番が電線に一列に止まるとき、決まり通りに並ぶ方
法はそれぞれ何通りずつあるか？


























（答）　らすかるさんが考察されました。（平成２７年５月２４日付け）

　全部で、n組のとき、n組中m組（1≦m≦n）の番が隣に並ぶとすると、

　先頭が雄か雌かで2通り

　n組からm組を選んで並べるのが、_nＰ_m通り

　残りのn-m匹の雄とn-m匹の雌の入れ方は、

　　mが偶数ならば、　_m/2H_n-m・_m/2+1H_n-m・((n-m)!)²通り

　　mが奇数ならば、　{_(m+1)/2H_n-m・(n-m)!}²通り

　よって、まとめると、

2・_nＰ₁・{₁H_n-1・(n-1)!}² +2・_nＰ₂・{₁H_n-2・₂H_n-2・((n-2)!)²} +2・_nＰ₃・{₂H_n-3・(n-3)!}² +
2・_nＰ₄・{₂H_n-4・₃H_n-4・((n-4)!)²} +2・_nＰ₅・{₃H_n-5・(n-5)!}² +2・_nＰ₆・{₃H_n-6・₄H_n-6・((n-6)!)²}+・・・
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(nPnの項まで)

となるので、n=2ならば、2・₂P₁・(₁H₁・1!)² + 2・₂P₂・(₁H₀・₂H₀・0!²) = 8通り

n=3ならば、2・₃P₁・(₁H₂・2!)² + 2・₃P₂・(₁H₁・₂H₁・1!²) + 2・₃P₃・(₂H₀・0!)² = 60通り

n=4ならば、

2・₄P₁・(₁H₃・3!)² + 2・₄P₂・(₁H₂・₂H₂・2!²)
　　　　　　　　　　　　　　　　　　　　 + 2・₄P₃・(₂H₁・1!)² + 2・₄P₄・(₂H₀・₃H₀・0!)² = 816通り

n=5ならば、

2・₅P₁・(₁H₄・4!)² + 2・₅P₂・(₁H₃・₂H₃・3!²) + 2・₅P₃・(₂H₂・2!)²
　　　　　　　　　　　　　　　　　　　+ 2・₅P₄・(₂H₁・₃H₁・1!²) + 2・₅P₅・(₃H₀・0!)² = 17520通り

n=6ならば、

2・₆P₁・(₁H₅・5!)² + 2・₆P₂・(₁H₄・₂H₄・4!²) + 2・₆P₃・(₂H₃・3!)²
　　　　+ 2・₆P₄・(₂H₂・₃H₂・2!²) + 2・₆P₅・(₃H₁・1!)² + 2・₆P₆・(₃H₀・₄H₀・0!²) = 550080通り

＃この数列は、「A096121」にありました。


　ＧＡＩ さんからのコメントです。（平成２７年５月２５日付け）

　よくこんな一般式を作れますね。私は、２組は手作業で、３組は、6!=720の全パターンをコ
ンピュータで作らせ、これから条件に外れるものを徐々に除いていき（プログラムの力不足
のため）、やっと60に絞り込みました。４組は、この結果を観察して、雄、雌の配列パターン
を考えていったら、11パターンに絞られたので、まず雌を並ばせておき、これに対して、雄が
決まる部分を確定し、残りの雄の自由度を個別のパターンで出して合計すると、

　　60（=4!(2*3!+2*2!*1*2!+2*2!+2*1+2*1+1*2!+2*1+1*1+1*1))

がとれました。５組目は、４組の方法を踏襲して、雄、雌の配列パターンが21となり、個別の
雄の自由度から、

　　2*5!(4!+3!+3!+3!+2!+2!+2!+3!+2!+2!+2!+2!+1+1+2!+1+2!+1+1+1+1)=17520

　ここでふと整数列大辞典が思い付き、ここまでの数字をタイプしたら、「A096121」がヒット
するではないか！そこには、15組までの数値が載せられている。そして、漸化式

　ａ_n+1＝n(n+1)(ａ_n＋ａ_n-1)

が書いてあり、実際に確認していくとピタリと一致する。また、説明には、”２×ｎボードをルー
ク（飛車）の動きで動く方法”とある。確かに、上段にはオス、下段には番のメスを配置してお
くと、この問題は、

　任意のスズメから出発して、ルーク（飛車）の動きで全ての場所を巡る方法

に一致する。これが数学の醍醐味だ。一見無関係に見える現象も、本質が同じである、異
なる現れに過ぎないことを知らせてくれる。

　らすかるさんの解法をみるにつけ、PやHや!の本質を十分に掴んである姿が羨ましいです。
苦労した後にこんな見事な解決策を見るのはとても参考になります。