FC2ブログ

Welcome to my blog

[答132] 黒星先行のない6勝6敗

ヤドカリ

ヤドカリ



[答132] 黒星先行のない6勝6敗


 12戦して6勝6敗になる星取りのうち、○●○●○○○●●○●● のように、

 いつの時点においても黒星が先行していないものは何通り?


[解答1]

 ○を→、●を↑ に対応させると、図のような道を、対角線(点線)の左上を通らずに、

 左下から右上に行く最短経路の問題になります。

 各交差点において、左の交差点に達する道順と、下の交差点に達する道順の和を書き込むと、

 道順は、132 通りです。


[解答2]

 6勝6敗の星取りは全部で、12!/(6!・6!)=924 通りです。

 そのうち、黒星先行があるものは、最初に黒星先行になった次から○●をすべて逆に書き換えると、 

   ○●○●○●●●○○○● ⇔ ○●○●○●●○●●●○

   ●○●○●○●●●○○○ ⇔ ●●○●○●○○○●●●

 のように、5勝7敗の星取りになります。

 逆に、5勝7敗の星取りは、必ず黒星先行があり、

 同じ書き換えをすると、黒星先行がある6勝6敗の星取りになります。

 1対1の対応がつきますので、黒星先行がある6勝6敗の星取りは、12!/(5!・7!)=792 通りです。

 従って、924-792=132 通りです。


[参考] カタラン数

 黒星先行のないn勝n敗なら、

 (2n)!/{n!・n!}-(2n)!/{(n-1)!・(n+1)!}

  =(2n)!・(n+1)/{n!・(n+1)!}-(2n)!・n/{n!・(n+1)!}

  =(2n)!/{n!・(n+1)!}=2nn /(n+1)

 となります。この形で表される数をカタラン数といいます。

.

スポンサーサイト



Comments 4

There are no comments yet.
uch*n*an  
No title

[解答2]は,一般化につながる考え方ですが,知らないとなかなか気付かないと思います。
カタラン数は,特殊な設定のようにも思いますが,意外なところに顔を出したりするので,
今回の問題は,私にはよい復習になりました。

いっちゃん  
No title

こんにちは。これも見事ですね^^
アジサイをヨーロッパに紹介した人がシーボルトなんですよ。妻の名前が「たき」だから「おたくさ」っていうのです。。♪ポチ

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
[解答2]の一般化の考え方は、ほとんど記憶のかなたにあった考え方を、
工夫して呼び起こしたものです。私にとっても復習になりました。

ヤドカリ  
No title

いっちゃん、コメントとポチを有難う御座います。
「おたくさ」って「おたきさん」ですか、勉強になります。
北鎌倉の名月院にも梅雨時期にもう1度いきたいなぁ。