場合の数の有名な問題
今回は高校入試の範囲で有名な問題を解説していこうと思います。更新するかもしれません」。
問題 場所$1$から場所$n$に異なる$n$このものが並んでいる.これらを並べかえてどれもが元の位置にならないようにする方法の総数を$D(n)$とする. ($D(n)\geq 2$)
(1)$n=4$のときの並べ方を全てかき出して$D(4)$を求めよ.
(2)$n\geq 4$に対して$D(n)=(n-1)\{D(n-2)+D(n-1)\}$を証明せよ.
(1)左の成分から順に場所$1$から場所$n$として
$(2,1,3,4),(2,3,4,1),(2,4,1,3),$
$(3,1,4,2),(3,4,1,2),(3,4,2,1),$
$(4,1,2,3),(4,3,2,1),(4,3,2,1)$
(2)まず一番左の場所におく数字を$2$とする. $2$番目に$1$をおくとき$(2,1,\triangle,…,\square)$の形であり,残りの$3$から$n$の場所に$3$から$n$のものをおくからこの場合は$D(n-2)$通り.
$2$番目に$1$でないものをおくとき, ものの$1$をものの$2$とみなすと$2$から$n$の場所に$2$から$n$のものをおくからこの場合は$D(n-1)$通り.
一番左には$2$の代わりに$3$から$n$もおけるから全部で$D(n)=(n-1)\{D(n-2)+D(n-1)\}$通り.
このように番号が重ならないように並べる場合の数を完全順列と言います.一つ目の場合分けでは$3$から$n$の場所に$3$から$n$のものをおくことになり綺麗に$D(n-2)$が出てきますが,後半では例えば$2$の場所に$3$をおくと残りはものが$1$と$4$から$n$があり場所は$3$から$n$が空いているというチグハグな残り方をします.そこで$2$の場所に$1$をおかない場合をまとめて扱うと$D(n−1)$になるというのがポイントだと思います.
問題 下の図のように碁盤の目状の道路がある.地点Aから地点Bに行く最短経路のうち直線$l$を通らないものは幾つあるか.一般に$n$マスの場合はどうか.
画像の名前
$n$マスの場合を考える.図$2$のように直線$l$に関して点$B$と対称な点を$B^\prime$とし点$B^\prime$までの道も碁盤の目状に加える.直線$l$を通って点$B$まで行く最短経路と$B^\prime$まで行く最短経路は直線$l$に関して折り返すことで一対一に対応する.よって求める最短経路の数は$B$までの最短経路の数から$B^\prime$までの最短経路の数を引いて$_{2n}C_n-_{2n}C_{n-1}=\frac{_{2n}C_n}{n+1}$通り.
画像の名前
このような場合の数をカタラン数といいたまに入試問題として出題されるようです.こちらのサイトでは類題も扱われています.
カタラン数【最短経路の応用問題】【2008年度 九州大学】 /
https://mathclinic314.com/2008%e5%b9%b4%e5%ba%a6%e3%80%80%e4%b9%9d%e5%b7%9e%e5%a4%a7%e5%ad%a6%e3%80%80%e3%82%ab%e3%82%bf%e3%83%a9%e3%83%b3%e6%95%b0%e3%80%90%e6%9c%80%e7%9f%ad%e7%b5%8c%e8%b7%af%e3%81%ae%e5%bf%9c%e7%94%a8/
このサイトの解答戦略2のように具体的な数が与えられた場合はパスカルの三角形のように数える方法もあります.
このような進み方は常に横に進む回数が縦に進んだ回数以上になっている必要があり,他にも複数の()の意味のある付け方や多角形を三角形に分割する場合の数などにも現れます.
この記事を高評価した人
この記事に送られたバッジ
投稿者
