第 章 確率分野 カタラン数 入試問題 （ 原点 九州大学） から出発して座標平面上を 軸の正の方向，または 軸の正の方向に だけ進むことを次々行っ を結ぶ，領域 て得られる経路を道という。原点と点 内の道の総数を とする。 次の問に答えよ。 を求めよ。 （ のとき， を求めよ。 のとき， を と で表し を求めよ。 京都府医大） は正の整数 上段には で， とする。図のように， 個の枠があり，下段には 個の同じ大きさの空白の枠がある。 個の枠がある。上段と下段の左端はそろっており，各段の枠は隣 との間にすき間はない。 図では， である。 から までの 個の自然数を各段の枠のなかに一つずつ次の二つの 条件を満たすように並べる。 各段においては，枠の中の数は右に行くに従って大きくなる。 左から 個の各列においては，下段の数は上段の数より大きい。 この二つの条件を満たすように から を並べる並べ方の数を とする。このとき のとき，次が成り立つことを示せ。 のとき，次が成り立つことを示せ。 次が成り立つことを示。 （ 大阪市大） 袋の中に赤玉 個と白玉 個が入っている。袋に戻さずに玉を 個ずつ取り出す試行を考える。取り出 された玉のうちで，白玉の個数が赤玉の個数より多いときは試行を中止し，そうでないときは袋の中に 玉があるかぎり試行を続けるものとする。次の問に答えよ。 玉を 個取り出した時点で試行が終わる確率を求めよ。 玉を 個取り出した時点で試行が終わる確率を求めよ。 玉を 個すべて取り出すまで試行が続く確率を求めよ。 対角線を横切らない経路の数 にちなんでカタラ 次の式で定義される自然数を、ベルギーの数学者 カタラン（ ン数（ ）と呼ぶ。 （定義）カタラン数 の値による の値は次のようになる。 このカタラン数はどんな意味を持っているかを考えよう。 例題 縦，横それぞれ長さ 路を作るとき，三角形 の正方形 を区切って右図のように経 において から までの最短経路の数 を求めよ。 対角線 を横切らない経路の数は、全体の数から横切る数を引けばよ い。いま、直線 に平行で上に だけ平行移動した直線を とする。直 線 の線上または上方の格子点を通る最短経路の場合の数を 正方形 の から までの最短経路 から とすると、 を引いたものが 求めるものとなる。 の直線 に関する対称な点を とする最短経路の とする。正方形 の つが最初に直線 上の格子点を通るとき、それ以降の 経路を直線 に関して対称な最短経路に移していくことで、 の最短経路は を出発点 から までの最短経路に 対 から まで 対応する。よって ∴ ■ カタラン数は対角線を横切らない最短経路の数を求めること同じであることがわかった。 【問題 】あるクラスの生徒は教材費として、 生徒と、 円札しか持っていない 円支払う必要がある。 人の生徒と合計 円玉しか持っていない 人の 人の生徒がいたが、担任の先生は釣銭を用意し ていなかった。このとき、釣銭が不足しないように生徒からもらうことができる確率はいくらか。 パスカルの三角形との関係 次にカタラン数とパスカルの三角形の関係を考えてみよう。パスカルの三角形というのは、 変数多項式 を展開した時の係数を並べたものである。 このパスカルの三角形のちょうど真ん中の数字の列を きる。真ん中の列は偶数になるので とおくと、 で割っていけばカタラン数を生成で 行目の真ん中の数は、 で与えられることから、カタラン数があらわれることがわかる。さらに、真ん中の数字からその左隣の数を を引くことによっても生成できる。これは であることから説明できる。 別な角度から考えてみよう。パスカルの三角形を応用して、最短経路の数を求めることができる。次の図 のように点 から横の交点と縦の交点に数字の“ ”をつけていき、各道筋の交点にはすぐ下の数字と左 側の数字の和を書いていく。こうして出てきた点 この方法で対角線の左半分をすべて の値が求める道順の数になる。 にすることでカタラン数の値を求めることができる。つまり対角 線を横切らない最短経路になるわけである。 カッコのつけ方の総数 個の文字 において、積の順序を考慮した計算の方法を考えてみよう。つまり、 などのようにカッコのつけ方で積の順序が変わってくる。そういう方法が何通りあるかということである。 ここにもカタラン数が関わってくる。 （定理） 文字（ 例． ）に対する積の順序を考慮した計算の方法の個数 のとき のとき 通り 通り のとき のとき、文字を は、次で与えられる。 で、始まりのカッコを 通り で表してみる。（終わりのカッコは省略できることに 注意。） ここで最後の を省略しても個数は変わらない。また、経路図と関連付けるために右方向を 、上方向を で表してみる。 このことから の値と対応していることがわかる。 三角形の分割数 （定理） 与えられた凸 角形（ ）に対して、それを三角形に分割する方法の総数 は次の式で 与えられる。 例． のとき のとき のとき 三角形の分割とカタラン数との関係をみるためには、 をベクトル でみた 数の積を「 数の和」とし、スカラー に置き換え、それぞれのベクトルを次の図のようにおく。 つのベクト ルの和の優先順位を変えると、 つのベクトルの和を表わす対角線により、五角形は三角形に分割され、カ タラン数 に対応する。 つまり凸 角形を三角形に分割する方法の総数 オイラー（ は で与えられる与えられることがわかる。これは ）が考えたものといわれている。 分木の総数 分木とはデータ構造の一つで、あるノード（節点）が持つ子の数が高々 であるものをいう。子ノード が つ以上とれる構造は多分木（ 分木）と呼ばれる。 分木では右の子と左の子を区別する。 （定理） 個（ ）の分木を持つ 分木の総数は で与えられる。 例． のとき のとき のとき 分木をカタラン数と関連付けるために、節に文字をあてはめ、最後の葉の部分をカッコでくくること にする。 つまり 個の分木を持つ 分木は で与えられる。 カタラン数の生成関数 は、次の図のように縦，横それぞれ長さ カタラン数 対角線 の正方形の から までの最短経路のうち、 を横切らない数の総数であった。そして、次の式で与えられた。 さてこのカタラン数を生成関数という観点から考えてみよう。 数列 ，，， があり、各項 を係数とする無限級数 を考え、これを数列の生成関数（母関数）と呼ぶ。カタラン数の生成関数はどうなるであろうか。 次の図で対角線 上の格子点で 以外の点を に近い方から順に とする。ただし、 である。 点 から までの際異端経路で初めて 上の点を通るときの格子点が とすると、 ここで であるから、次の式が成り立つ。 カタラン数の生成関数を とおく。このとき、 であるから、 ∴ ∴ ∴ において、 のとき、 より、 のとき となることより、 のマクローリン展開を考える。 であるものの場合の数を ∴ （ より、 最初に求めていた の一般項を確認することができました。 の項の係数を比較すると、 マルコフ過程 入試問題 （ 九州大） いくつかの玉が入った箱 試行 箱 から と箱 があるとき，次の試行 個の玉を取り出して箱 を考える。 に入れ，その後，箱 から 個の玉を取り出して箱 に入れる。 最初に箱 に黒玉が 試行 を 個，箱 に白玉が 個入っているとき，以下の問いに答えよ。 回行ったときに，箱 に黒玉が 個入っている確率 を求めて既約分数 回行ったときに，箱 に黒玉が 個入っている確率 を求めて既約分数 回行ったときに，箱 の中がすべて黒玉になっている確率を求めて既約分数で表せ。 で表せ。 試行 を で表せ。 試行 （ を 東大前期） さいころを振り 出た目の数で を割った余りを らにさいころを振り，出た目の数で いころを振り，出た目の数で このようにして， とする．ただし， で割った余りは を割った余りを を割った余りを とする．以下同様にして， である． さ が決まればさ とする． を定める． となる確率を求めよ． 各 に対し， となる確率を求めよ． 各 に対し， となる確率を求めよ．注意：さいころは から までの目が等確率で出るもの とする． （ 白黒 東大理） 種類のカードがたくさんある．そのうち 枚のカードを手もとにもっているとき，次の操作 を考える． 手持ちの 以下の問 最初に白 ， 枚の中から 枚を，等確率 で選び出し，それを違う色のカードにとりかえる． に答えよ． 枚，黒 枚，合計 枚のカードをもっているとき，操作 を 回繰り返した後に初め を 回繰り返した後に初め て， 枚とも同じ色のカードになる確率を求めよ． 最初に白 枚，黒 枚，合計 枚のカードをもっているとき，操作 て， 枚とも同じ色のカードになる確率を求めよ． 名大前期理系 袋の中に赤と黄と青の玉が 個ずつ入っている． 「この袋から玉を 個取り出して戻し，出た玉と同じ色の 玉を袋の中に 個追加する」という操作を 回繰り返した後，赤の玉が袋の中に とする． 連比 一般の を求めよ． に対し を求めよ． 個ある確率を 慶応医 を自然数とする． 上に球を 平面上で 個置き，次の操作 を 座標も 座標も整数である点全体の集合を 回繰り返し行うことにより球を で表す．今点 上で動かす． 操作 ： 球が置かれている点を とするとき， 球を のどれかの点上に確率 操作 ， ， ， ずつで動かす． を 回行った時点で球が置かれている点の座標を で表す． 同様に，操作 繰り返し行った時点で 球が置かれている点の座標を ， で表す． を 回 の部分集合 ， ， を考える． 平面上で連立不等式 の表す領域を とする． となる確率を とする． を求めよ． 平面上で不等式 または 集合 の要素の個数が の表す領域を とする． となる確率を とする． となる確率 となる確率 を求めよ． を求めよ． を求めよ． 東大文理科 各世代ごとに，各個体が，他の個体とは独立に， 確率 で 個，確率 で 個の新しい個体を次の世代に残し， それ自身は消滅する細胞がある．ただし とする． いま，第 世代に 個であった細胞が，第 を自然数とするとき， 個 と書くことにしよう． となる確率を， 世代に ， ， を求めよ． 名大理系前期 整数に値をとる変数 の値が，以下の規則で変化する． ある時刻で のとき， 秒後に ある時刻で のとき， 秒後に ． である確率は から始めて， 秒後 に を求めよ． すべての自然数 「どんな整数 に対し次が成り立つことを示せ． についても を求めよ． は にはよらない」 である確率はともに である． である確率は である である確率を とする． マルコフ連鎖 マルコフ連鎖とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可 算）なもの（離散状態マルコフ過程）をいう。また特に、時間が離散的なもの（時刻は添え字で表される） を指すことが多い。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である （マルコフ性）。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が 過去の状態によらず、現在の状態のみによる系列である。特に重要な確率過程として、自然科学、社会科学 など様々な分野において、種々の現象の数理モデルを表現する有用な道具として活用されている。 （定義）確率過程 試行が次々と行われる行為 時点と共に変化する確率変数 を確率過程という。 例． サイコロを投げ， 回目に偶数の目が出たら することを考える 各 ，奇数の目が出たら を割り当てて記録 は互いに独立 。サイコロを投げ続けた時の記録の一例 コインを投げて表が出たら に得られる得点を確率変数 で表される．ただし， 点，裏が出たら 点を獲得できるとする。 回めのコインを投げた時 で表すと， 回めのコインを投げた時までの総得点 は とする。 （定義）単純マルコフ過程 ある時点 における事象の生起する確率が直前の事象のみに依存するとき，単純マルコフ過程という。 回目の確率変数の値から 回目の確率変数の値を定める確率を推移の確率という。推移の確率 が によらないとき、このマルコフ過程は定常状態にあるという。 定常状態にあるマルコフ過程では はとりうる範囲にわたる と定数となる推移の確率を用いて漸化式に表すことができる。 例．一つ前の試行の結果に応じて，記号の生起する確率が変わるサイコロ投げを考える 各 は独立でな い 番目の記号 が のとき， 回目のサイコロの目が であれば ，それ以外の目であれば が のとき， 回目のサイコロの目が であれば ，それ以外の目であれば とする。 番目の記号 とする。 サイコロを投げ続けた時の記録の一例 このマルコフ過程の例を条件付き確率で表すと で目が で目が 以外 で目が 以外 で目が となる．通信関係の分野では，このような確率は遷移確率と呼ばれ，それを図に表したものをシャノン線 図，または状態遷移図と呼ぶ。 例題 か 後に があり頂点 は時計回りに並んでいる。点 ははじめ点 にある。サイコロを投げ が出れば時計回りに隣の頂点に移り、 ～ が出れば反時計回りに隣の頂点に移る。 回の試行の が点 にいる確率を求めよ。 （解答） 回の試行の後に が点 ， ， にいる確率をそれぞれ とする。 式加えて、 を消去する。 を代入して整理すると、 ここで なので，辺々引いて ここで ここで とおくと、 次方程式 を解いて とおく．漸化式が と解ける。 となる。なお となる。 ， を代入して整理すると、 なので つまり、最初どこにいても何度も試行を重ねれば、 である。これから、 は いずれも に収束する。■ 完全順列 入試問題 （ 場所 東工大後期） から場所 に異なる 個のものが並んでいる。これらを並び替えてどれもが元の位置にならな とする。ただし、 いようにする方法の総数を とする。 の場合の並べ替え方をすべて書き出して、 を求めよ。 に対して を証明せよ。 （ 東京農大） の順列 のうちで、 を全部満たすも のは何通りあるか。 また、 （ を全部満たす物は何通りあるか。 早稲田大学・教育） ある囲碁大会で、 つの地区から男女が 人ずつ選抜されて、男性 人と女性 人のそれぞれが異性を 相手とする対戦を行う。その対戦組み合わせを無作為な方法で決めるとき、同じ地区同士の対戦が含ま れない組み合わせが起こる確率は （ 東北大学理系）袋 袋 である。 のそれぞれに から の自然数がひとつずつ書かれた 枚のカー ドが入っている。これらのカードをよくかきまぜて取り出していく。以下の問いに答えよ。 とする。袋 のそれぞれから同時に 枚ずつカードを取り出し 数字が同じかどうかを確 認する操作を繰り返す。ただし 取り出したカードは元には戻さないものとする。 回のカードの取り 出し操作が終わった後 数字が一致していた回数を 確率をそれぞれ求めよ。また とし とする。 となる の期待値を求めよ。 は自然数とする。袋 のそれぞれから同時に 枚ずつカードを取り出し カード の数字が一致していたら そのカードを取り除き 一致していなかったら 元の袋に戻すという操作を 繰り返す。カードが初めて取り除かれるのが カードが取り除かれる確率を とする。 回目で起こる確率を と を求めよ。 とし 回目の操作ですべての 完全順列 定義（完全順列） 集合 上の順列 で を満たすものを完全順列といい、その 個数をモンモール数という。 についての完全順列とモンモール数は次の通りである。 集合 上の完全順列 モンモール数 なし 定理（モンモール数の漸化式） 集合 上のモンモール数を （証明）集合 とすると、次の漸化式が成り立つ。 上の順列 の 番目に数 を追加する。数 目の数と変換すると、 個全ての数がその数の順番と一致しなくなる。よって、 ら 個の完全順列が作れる。 番目へはそれぞれ また、 個のうち 番目が揃っているものからも 番目の数と 番目の数を入れ替えれば完全順列 ■ 定理（モンモール数） 集合 上のモンモール数は、次で与えられる。 （証明） 両辺から を引くと、 とおくと、 両辺を で割ると、 とおくと、 のときも成立 ■ 番 個ある完全順列か が得られる。よって、 明らかに を 系（完全順列の確率） 個のものを並べ替える順列をランダムに作ったとき、完全順列となる確率は、次で与えられる。 さらに 後半は とすると、 のマクローリン展開が となる。 であることから明らかである。
© Copyright 2024 ExpyDoc
