『拡張金太郎飴整列』解答


◆東京都 由釜与祢弥 さんからの解答。

【練習問題1】

6006[通り]

【練習問題2】

6006[通り]

【本命問題】

m-1
Π
k=0
k!・ n-1
Π
k=0
k!

m+n-1
Π
k=0
k!
(mn)! [通り]

(1),(2)についてはプログラムを書いて確かめました。
(3)については、これがカタラン数であることが予想されることからの予想です。
したがってこれを証明しなければならないのですが、至らず...。


◆出題者のコメント。

解答ありがとうございます。
4ヶ月近くも未解答だったので、とても嬉しいです。

正解だと思います。
でも、証明がないのと未証明の「考えていた一般解」と異なるため、言い切ることができず困っています。
でも、プログラムで確かめたということですから、おそらく「考えていた一般解」は間違っていたのでしょう。^^;
(事務系のソフトが一切ないため、m,nが大きくなると私には確かめることができません。)

ですから、誰かが証明してくれるのを期待したいところです。

m種類n個ずつを(m,n)で表すと、「考えていた一般解」でも

(1,n)=1
(2,n)=2nn
n+1
(m,1)=1
(m,2)=2mm
m+1
(3,3)=42

となり、由釜与祢弥 さんの一般解の結果と同じです。

ところが、それ以外だと「考えていた一般解」の方が小さい数になります。

それにしても、この複雑な一般解をよく導き出したものだと感服しました。

「考えていた一般解」は、全ての場合がカタラン数になることを前提に無理やり導いたため、当然どんな場合もカタラン数になります。
6006もそうであるように、全ての場合がカタラン数になるわけではなかったんですね。
(下のカタラン数三角形参照)


 『拡張金太郎飴整列』へ

 数学の部屋へもどる