場合の数の問題

原点Oから出発して、座標平面上をｘ軸の正の方向、またはｙ軸の正の方向に1だけ進む事を次々に行なって得られる経路を道という。原点Oと点(i、j)を結ぶ領域((ｘ、ｙ)｜ｘ≧ｙ)内の道の総数をN(i,j)とする。
(1)N(2,2)、N(3,1)、N(3,2)を求めよ。
(2)ｎ≧1のとき、N(n、１)を求めよ。
(3)ｎ≧３のとき、N(ｎ、２)をN(ｎ、１)とN(ｎ-1、2)で表し、N(ｎ、2)を求めよ。

(1)は図を書いて数えました。
答えは2,3,5だと思います。

(2)、(3)はちょっと解きかたがわかりません。
よろしくお願い致します。

No.3 回答者： fushigichan 回答日時： 2003/11/29 14:32

＃１続きです。

＞(3)ｎ≧３のとき、N(ｎ、２)をN(ｎ、１)とN(ｎ-1、2)で表し、N(ｎ、2)を求めよ。

これは、図を描いて考えてみましょう。

N(n,2)というのは、横にｎ回、縦に２回進むということですが、
よく見てみましょう。

点(n,2)というのは、点(n,1)から縦にさらに１つ進んだものであって、
点(n-1,2)からは、横にさらに１つだけ進んだ点である、ということが分かります。
また、点(n,2)に至るには、点(n,1)もしくは(n-1,2)のどちらかを必ず経由しなければなりませんね。

原点から点(n,1)に至ってから、さらに(n,2)に至る方法は１とおりです（縦に１つ進むだけ）
原点から点(n-1,2)に至ってから、さらに(n,2)に至る方法も１とおりです（横に１進むだけ）

ということは、
N(n,2)=N(n,1)+N(n-1,2)
である、といえます。ここまでいいでしょうか。

N(n,1)=n+1
である、と(2)で求めました。

N(n-1,2)={(n-1)+1}C2=(n+1)!/2!(n-1)!
=(n+1)n/2

ゆえに
N(n,2)=N(n,1)+N(n-1,2)=(n+1)+(n+1)n/2
=(n+1){1+n/2}
=(n+1)(n+2)/2

さて、実際
N(n,2)=(n+2)C2=(n+2)!/2!n!=(n+2)(n+1)/2
ですから、考え方は合っていますね。
ご参考になればうれしいです。落ち着いて考えてみてくださいね。

この回答へのお礼

ｘ≧ｙという条件がなかったら、そんな解き方になるんですね。
今よく見ると、ごっちゃになりそうなので、後でよくみさせていただきますm(__)m

お礼日時：2003/12/03 17:33

No.2 回答者： 0shiete 回答日時： 2003/11/29 14:27

（１）について、

コンビネーションnCmは
nCm=n!/(m!(n-m)!)
で計算されます。

N(2,2)の場合、距離4だけ進まないといけないわけですが、

右右上上
右上右上
右上上右
....

などの行き方があるわけですよね。

つまり、４つの箱に「右」「上」を２つづつ入れる
問題と同じです。
これは4C2で計算できますね。

N(3,1),N(3,2)についても同様です。

わからなければ、また補足をお願いします。

この回答へのお礼

ご回答ありがとうございます。

(3)の問題がよくわからないので、よかったら教えて下さいｍ(＿＿\)ｍ

お礼日時：2003/12/03 17:34

No.1 回答者： fushigichan 回答日時： 2003/11/29 14:25

stripeさん、こんにちは。

＞原点Oから出発して、座標平面上をｘ軸の正の方向、またはｙ軸の正の方向に1だけ進む事を次々に行なって得られる経路を道という。原点Oと点(i、j)を結ぶ領域((ｘ、ｙ)｜ｘ≧ｙ)内の道の総数をN(i,j)とする。
(1)N(2,2)、N(3,1)、N(3,2)を求めよ。

N(i,j)というのは、原点Ｏから、点(i,j)に至る道順の数ですね（経路の数）
点(i,j)というのは、原点から、x軸方向にi,y軸方向にjだけ進んだ点のことです。

そこに至るまでの道順の総数は、
(i+j)Ci　コンビネーション(i+j)のi
になります。
何故かというと、原点Ｏから点(i,j)に行くまでには
横にi回、縦にj回進まないといけません。
合計(i+j)回進めばいいのですが、そのうち何回横に進めばいいのか？と考えたらいいです。

さて、具体的には
N(2,2)とは、原点(0,0)から点(2,2)に至る経路ですが
横に２、縦に２だけ進まないと(2,2)にはいけませんね。
そのうち、どこで横に進むかで
(2+2)C2=4*3/2=6
の６とおりがあります。
実際図を描いてみましょう。

(0,0)→(0,1)→(0,2)→(1,2)→(2,2)
(0,0)→(0,1)→(1,1)→(1,2)→(2,1)
(0,0)→(0,1)→(1,1)→(2,1)→(2,2)
(0,0)→(1,0)→(1,1)→(1,2)→(2,2)
(0,0)→(1,0)→(1,1)→(2,1)→(2,2)
(0,0)→(1,0)→(2,0)→(2,1)→(2,2)

の６とおりの行き方があることが分かると思います。

N(3,1)も同様に
横に３回、縦に１回進むので、全部で４個進むうちに
どこで上に行くかで

(3+1)C1=4C1=4
となって４とおりです。

N(3,2)も同様に

(3+2)C2=5*4/2*1=10
となって１０とおりです。ここまでいいでしょうか。

＞(2)ｎ≧1のとき、N(n、１)を求めよ。

これも、全く同様に考えたらいいですね。
N(n,1)というのは、横にn回、縦に１回だけ進むということなので

N(n,1)=(n+1)C1=(n+1)!/1!n!=n+1

ちょっと長くなりそうなので、一旦ここで送りますね。