場合の数の問題

質問

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

kony0

#10の補足を見ました。

＞７．のところがよくわからないので、もうちょっと詳しく教えて頂けたらうれしいです。

階差数列型！という言葉の意味がわからないのか、
階差数列という言葉は知っているが、6.の式が、階差数列の考え方で解けることがわからないか

どちらでしょうか？

お礼

わかりにくい補足をしてすみません！

＞階差数列という言葉は知っているが、6.の式が、階差数列の考え方で解けることがわからないか

のほうです。数列は習ったので、階差数列は一応わかってるつもりです。
よろしくお願いしますm(__)m

回答No.11

laputart

>(3)なので、ちょっとお聞きしたいのですが、
>>N(N,2)=(2+3+....N)
>>　　　=N(N+1)/2 - 1
>>
> よってN(n,2)=n(n+1)/2 + 1
>となります。

>のNというのは、何のことなのでしょうか？
---------に対しての回答----------------
大文字と小文字の混在でちょっとわかりにくいですね。
正しくは
N(n,2)=(2+3+....n)
　　　=n(n+1)/2 - 1

よってN(n,2)=n(n+1)/2 + 1
となります。

お礼

補足してくださってどうもありがとうございます。
n(n+1)/2 - 1 から
n(n+1)/2 + 1
となるのがよくわからないのですが、ここのところを教えていただけるでしょうか？

回答No.10

kony0

結局、こんな感じの考え方になります。
1. n≧1に対して、N(n,0)=1
2. N(1,1)=1
3. n≧2に対して、N(n,1)=N(n,0)+N(n-1,1)=1+N(n-1,1)
4. 2.3.よりN(n,1)=n
5. N(2,2)=N(2,1)=2
6. n≧3に対して、N(n,2)=N(n,1)+N(n-1,2)=n+N(n-1,2)
7. 6.の漸化式は階差数列型！
n≧3に対してN(n,2)=N(2,2)+Σ(k=3～n)k
途中計算略で、N(n,2)=(2+n)(n-1)/2

お礼

ご回答ありがとうございます。
７．のところがよくわからないので、もうちょっと詳しく教えて頂けたらうれしいです。

補足

すみません。お礼の補足です。

N(n,2)=N(2,2)+Σ(k=3～n)k

がよくわからないので、この式がでてくるところまでを教えて頂けたらうれしいです。

回答No.9

fushigichan

stripeさん、＃１＃３です。補足いただいたんですが

＞出だしの(1)なのですが、
ｘ≧ｙという条件があるので、
右右上上
右上右上
の二通りなのではないでしょうか？

そうでした。領域{(x,y)|x≧y}
の中を通る道筋だけ、ということですよね？

それなら、stripeさんのご回答の通りですね！間違えてすみません。

N(2,2)は、
x≧yとなるには
点(0,1)(0,2)(1,2)は通れませんから、それらを通らない経路で考えないといけなかったですね。

(0,0)(1,0)(1,1)(2,1)(2,2)
(0,0)(1,0)(2,0)(2,1)(2,2)
の２通りしかないですね！

N(3,1)
x≧yを通るには、
点(0,1)は通れません。
＃１で考えた４とおりのうち、(0,1)を通るのは１通りなので
4C1-1=3
となって３とおり。

N(3,2)
(0,1)(0,2)(1,2)は通れません。
(0,1)を通るものは、４とおり。
(1,2)を通るものは、１とおり。
(0,2)を通るものは、(0,1)を通るものに含まれています。
＃１の１０通りから上の５通り引いて
１０－５＝５通り。
となって全部stripeさんの解答どおりです。

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

＃１で回答した
N(n,1)には、点(0,1)を通る１とおりが余分に含まれてしまっているので
(n+1)C1-1=n
となって、N(n,1)=n
が正解です。

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

これは難しそうですね。
N(n,2)=N(n,1)+N(n-1,2)
という考え方は、＃３のとおりでいいと思います。

N(n,2)=N(n,1)+N(n-1,2)ですが、N(n,1)=nを代入すると

N(n,2)=n +N(n-1,2)　　←これを漸化式と考える。
　　　　　　　　　　　　nを１つずつ減らしていきましょう。

N(n-1,2)=(n-1)+N(n-2,2)
N(n-2,2)=(n-2)+N(n-3,2)
・・・・・
N(3,2)=3+N(2,2)
N(2,2)=2+N(1,2)
--------------------------------へんぺん足す

N(n,2)={2+3+4+・・+(n-1)+n}+N(1,2)

2+3+4+・・+n=Σk[k=2 to n]=n(n+1)/2-1
=(n^2+n-2)/2

ゆえに
N(n,2)=(n^2+n-2)/2+0=(n^2+n-2)/2

でした。(3)については＃７の方がいい説明されていると思います。
(1)のN(2,2)=2だと思います。
ご参考になればうれしいです。訂正させていただきます。

お礼

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

(2)ばんまではよくわかりました～(＾＾)

＞N(n,2)={2+3+4+・・+(n-1)+n}+N(1,2)
この式の前まではわかったのですが、
N(n,2)とN(1,2)はどうやってでてきたのでしょうか？
{2+3+4+・・+(n-1)+n}という項はだいじょぶです。
よかったら教えて下さいｍ(＿＿)ｍ

回答No.8

cubics

失礼、失礼、問題よく読んでないのは、一番いけない。
そうです、（１）の解答は２、３、５でいいです。
でもって、（２）はｎになるでしょ。
（３）の考え方は同じです。

だから、結果は、
Ｎ（ｎ、２）＝（ｉ＝２からｎ）シグマ（ｉ）
ｎ＞＝３の場合
ですね。
これを展開すると、
Ｎ（ｎ、２）＝ｎ（ｎ＋１）／２－１
となって、前の方といっしょです。

お礼

ご回答ありがとうございます。
今みるとごっちゃになりそうなので、前に答えていただいたのはあとでみさせていただきます。
参考にさせていただきます。

回答No.7

laputart

(1) N(2,2)はN(2,1)とN(1,2)の和で６ではないでしょうか。と思ったら　ｘ≧ｙの条件があるので５でした。

(2)
N(n,0)は１通り　全て１となります。
よってN(n,1)はN(n,0)とN(n-1,1)の和となります。
N(1,1)はN(1,0)+N(0,1)ですがｘ≧ｙなのでN(0,1)は
通過できません。つまりN(0,1)=0
よってN(1,1)=N(1,0)=1 となります。

N(2,1)=N(2,0)+N(1,1) = 1 +1 =2
N(3,1)=N(3,0)+N(2,1) = 1 +2 =3
となりますから　N(n,1)=n となります。

(3) N(n,2)について
N(n,2) = N(n,1)+(n-1,2)の和です。
N(n,1)=n　は（１）で求めたとおりです。
N(0,2),N(1,2)はｘ≧ｙなので0です。
N(2,2)=N(2,1)+N(1,2)で2+0=2となります。
----------
N(3,2)=N(3,1)=N(2,2)なので3+2=5
N(4,2)=N(4,1)=N(3,2)なので4+5=9
N(5,2)=N(5,1)=N(4,2)なので5+9=14
.......

よってN(n,2)=n(n+1)/2 + 1
となります。

※この求め方
N(2,2) = 2
N(3,2) = N(2,2) +3
N(4,2) = N(3,2) +4
N(5,2) = N(4,2) +5
...
...
...

N(N,2)=N(N-1,2) + N
両辺の和を求めると
左辺
N(2,2)+N(3,2)+.... +N(N,2)

右辺
= N(2,2)+N(3,2)+....+N(N-1) + (2+3+4+5+.....N)

右辺の前半を左辺に移項すると
N(N,2)=(2+3+....N)
　　　=N(N+1)/2 - 1
となります。

お礼

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

＞N(2,1)=N(2,0)+N(1,1) = 1 +1 =2
N(3,1)=N(3,0)+N(2,1) = 1 +2 =3
となりますから　N(n,1)=n となります。

最初からｎで考えないで、小さい数でやってみるとわかりやすいですね。
よくわかりました。

(3)なので、ちょっとお聞きしたいのですが、
＞N(N,2)=(2+3+....N)
　　　=N(N+1)/2 - 1

＞よってN(n,2)=n(n+1)/2 + 1
となります。

のNというのは、何のことなのでしょうか？
n(n+1)/2 + 1
の+1は-1のことでしょうか？

とんちんかんなこと聴いてたらすみません(＾＾；
まだ理解不足なので・・・。

回答No.6

cubics

またまた補足
数列を習得済みであれば、（３）は、
Ｎ（ｎ、２）＝Ｎ（ｎ、１）＋Ｎ（ｎ－１、２）
＝（ｎ＋１）＋Ｎ（ｎ－１、２）
つまり
Ｎ（ｎ、２）－Ｎ（ｎ－１、２）＝ｎ＋１
数列で置き換えて
Ｘ（ｎ）－Ｘ（ｎ－１）＝ｎ＋１
Ｘ（２）＝６またはＸ（３）＝１０
ここでシグマを用いてから、計算すれば、
Ｘ（ｎ）＝（ｉ＝１からｎ＋１）シグマ（ｉ）
になりますね。
これ以上はお勉強ください。^^;;)

補足

皆さまどうもありがとうございます。

出だしの(1)なのですが、
ｘ≧ｙという条件があるので、
右右上上
右上右上
の二通りなのではないでしょうか？

回答No.5

cubics

間違えてましたので、補足。
ｎ＞＝３ですから、
Ｎ（ｎ、２）＝シグマ（ｉ）（ｉ＝１からｎ＋１）
シグマ記号使えないんで（行もずれるし）、
適当に解釈してくださいね。
つまり、ｎ＝３のときは
Ｎ（３、２）＝１＋２＋３＋４＝１０

ここまでくると、実はｎ＝２でも、
Ｎ（２、２）＝１＋２＋３＝６
ｎ＝１でも、
Ｎ（１、２）＝１＋２＝３
となって、ｎ＞＝３じゃなくてもよくなるんですね。

回答No.4

cubics

まず、（１）が間違ってます。^^;;)
答は、６，４，１０ですね。
続けて同じ方向に進んでもいいはずです。
そうでないと問題の意図が違ってくるから。

（２）は、単純にＮ（ｎ、１）＝ｎ＋１
これは、図に書いてもわかりますね？

（３）は、図に書いて考えてくださいね。
そうしたら、すぐにＮ（ｎ、２）に行く方法が
Ｎ（ｎ、１）からは１本だけ、
Ｎ（ｎ－１、２）からも１本だけとわかります。
つまり、こうなります。
Ｎ（ｎ、２）＝Ｎ（ｎ、１）＋Ｎ（ｎ－１、２）
（１）に戻ってください。計算して、
１０＝４＋６　でしょ？

そうしたら、
Ｎ（ｎ、２）＝Ｎ（ｎ、１）＋Ｎ（ｎ－１、２）を
どんどん使って、Ｎ（２、２）まで帰納すれば
いいことがわかりますね。
Ｎ（ｎ、２）＝Ｎ（ｎ、１）＋Ｎ（ｎ－１、２）
＝Ｎ（ｎ、１）＋Ｎ（ｎ－１、２）
＝Ｎ（ｎ、１）＋Ｎ（ｎ－１、１）＋Ｎ（ｎ－２、２）
・・・
＝Ｎ（ｎ、１）＋・・・＋Ｎ（２、２）
＝（ｎ＋１）＋ｎ＋（ｎ－１）＋・・・＋６
（最後が＋６なのは、ｎがだいぶ大きいときですね）

ｎ＞＝３ですから、
Ｎ（ｎ、２）＝シグマ（ｉ＋２）（ｉ＝１からｎ）
になりますので、ご自分で帰納的にやってみてください。

回答No.3

fushigichan

＃１続きです。

＞(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