スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

お釣りが切れない確率の問題

[ 問題 ]
Charlieは1枚10ユーロのチケットを売っている。今、Charlieの手元には k 枚の10ユーロ紙幣がある。
n 人の10ユーロ紙幣を持った客と、m 人の20ユーロ紙幣を持った客がランダムな順番でチケットを買おうとしている。Charlieが全ての客をさばける(釣りが切れない)確率はいくらか?
( 前回の記事 D問題から引用 )

Tags : 数学 組合せ論

ある時点までに来た 10ユーロを持った人の数 x, 20ユーロを持った人の数 y とすると、問題の条件は、常に
x + k ≧ y
が成り立っているということと同じです。

これはつまり、xy-座標上で表現すると図のようになります。がんばって手書き
図の赤い線 y=x+k を越えないように 点(0,0) から 点(n,m) まで、最短距離で移動するときの経路が問題の条件にあった経路になります。
最短経路の図と場合の数


問題の条件にあった経路の総数を求めます。
これは、(0,0)-(n,m) をつなぐ全経路の中で、 y=x+k を越える経路を除いたものに等しくなります。
さらに言い換えれば、
(0,0)-(n,m) をつなぐ全経路の中で、 y=x+k+1 に触れる(跨ぐ場合も含む)経路を除いたもの
といってもかまいません。

ここで、 y=x+k+1 に触れる(or跨ぐ)経路(たとえば図の緑の経路)の総数が
n+mCn+k+1
であることが次のようにして分かります。

 1. 経路中で y=x+k+1 に初めて触れる点に注目し、
  経路のその点以降の部分を y=x+k+1 について反転する。(図の緑の点線)
 2. すると、経路の終端は 点(m-k-1,n+k+1) に達する。
 3. このようにして作った新しい経路は、(0,0)-(m-k-1,n+k+1) を結ぶ全経路と1対1に対応するので、
  経路の総数は (m-k-1)+(n+k+1)Cn+k+1 = n+mCn+k+1 となる。

( この辺りの話は、Brown運動の反射原理なんかも参考になるかも )

(0,0)-(n,m) を結ぶ全経路の数は明らかに n+mCn なので、問題の条件に合った経路の総数は
n+mCn-n+mCn+k+1 … (1)
となります。

(1)式を、(0,0)-(n,m) を結ぶ全経路の数 n+mCn で除してちょこちょこ計算すると、求める確率は
1-\frac{_mC_{k+1}}{_{n+k+1}C_{k+1}}
となります。



特に、k=0, m=n のときは
(1)式 = 2nCn/(n+1) となり、Catalan(カタラン)数に等しくなります。
そういった面から、この問題はCatalan数のひとつの一般化といえるのではないでしょうか?


この記事を書くにあたり、次のサイトがとても参考になりました。
○場合の数・確率を勉強しよう!(http://kakuritsu.hp.infoseek.co.jp/mokufr.html)
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。