場合の数の問題

質問

原点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.13

kony0 · ベストアンサー

n≧3のとき、a[n]=a[n-1]+n
n＝2のとき、a[2]=2

という漸化式を解けばよいことになります。
※N(n,2)をa[n]と表記しなおしただけです。

a[n]-a[n-1]=（nの式）となっていることに注目してください。これが「数列a[n]の階差数列が式で与えられている」ことを示しています。
その解き方は、階差数列でおなじみの方法ですが、「階差のスタートの項に、階差を足しこんでいく」ことで導出できます。

いまは、階差のスタートがa[2]ですから、
a[n]=a[2]+(a[3]-a[2])+(a[4]-a[3])+…+(a[n]-a[n-1])
=a[2]+Σ(k=3～n)(a[k]-a[k-1])
=a[2]+Σ(k=3～n)k
となります。

お礼

う～ん、けっこうむずかしいですね。
でもなんとなくわかりました。
ありがとうございました。

回答No.2

0shiete

（１）について、

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

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

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

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

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

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

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

お礼

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

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

回答No.1

fushigichan

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

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