■記事リスト / ▲上のスレッド
□投稿者/ 冨士 一般人(1回)-(2021/02/12(Fri) 15:32:13)
 | nを自然数とします。
xy平面上で点Pが(0,0)を出発してx軸正の方へ1移動するかy軸正の方へ1移動するかを繰り返して(n,n)まで移動します。
このような移動の方法は全部で2nCn通りあり、y≦xの部分だけを通っていく方法は2nCn/(n+1)通りあります。
質問ですが、y≦xの部分だけを通っていく方法2nCn/(n+1)通りのうち点Pがy=x (0<x<n)に触れる回数が全部で何回なのか知りたいです。
数学的にどう書くのがよいのかよく分からないのですが、y≦xの部分だけを通っていく2nCn/(n+1)通りのうち
y=x (0<x<n)に触れる回数がk (k=0,1,2,...,n-1)回のものをa[k]通りとすると(Σ[k=0,n-1]a[k]=2nCn/(n+1) )、
s[k]=Σ[k=0,n-1] k*a[k]
の値、その求め方などが知りたいです。
s[3]=4、s[4]=14などです。
よろしくお願いします。
|
|
|
▽[全レス4件(ResNo.1-4 表示)]
| ■50620 / ResNo.1) |
Re[1]: カタラン数
|
□投稿者/ らすかる 一般人(5回)-(2021/02/12(Fri) 17:04:48)
| 「s[k]=Σ[k=0,n-1] k*a[k]」は
「s[n]=Σ[k=0,n-1] k*a[k]」の間違いですよね。
f(n)=2nCn/(n+1)とすると
例えばs[4]のとき
(1,1)に触れる回数はf(1)×f(3)
(2,2)に触れる回数はf(2)×f(2)
(3,3)に触れる回数はf(3)×f(1)
なので
f(1)×f(3)+f(2)×f(2)+f(1)×f(3)=5×1+2×2+1×5=14
のようになりますね。
よって一般には
s[n]=Σ[k=1～n-1]f(k)f(n-k)=2・(2n)C(n-2)/n
と表されます。
|
|
|
| ■50621 / ResNo.2) |
Re[2]: カタラン数
|
□投稿者/ 富士 一般人(1回)-(2021/02/12(Fri) 18:36:03)
| s[k]とs[n]間違えていました。失礼しました。
たしかにこの方法で数えられそうです！全然気付きませんでした。
シグマ計算についてはまだ確認できていませんが、ありがとうございます。
もうひとつよろしいでしょうか。
S[n]=Σ[k=0,n-1] 2^k * a[k]
の求め方も教えてほしいです。
自分で色々計算すると(2n-1)C(n-1)になりそうな気がするのですが、どう求めるのかは分かりません。
|
|
|
| ■50622 / ResNo.3) |
Re[3]: カタラン数
|
□投稿者/ らすかる 一般人(6回)-(2021/02/12(Fri) 22:13:04)
| 経路の交差点に順に数字を書き込んでいって何通りか調べる方法で考えて、
その方法でy=xに当たった時に2倍すればΣ[k=0～n-1]2^k*a[k]が求まります。
y=0の行はすべて1
y=1の行は(1,1)が2、(2,1)が3、(3,1)が4、…のようになるのでx+1
y=2の行は(2,1)の3の2倍に4,5,6,…を加えていけばよいので
3×2+Σ[k=3～x](k+1)=(x+1)(x+2)/2
同様にy=3の行は(3+1)(3+2)/2×2+Σ[k=4～x]{(k+1)(k+2)/2}=(x+1)(x+2)(x+3)/6
y=4の行は(4+1)(4+2)(4+3)/6×2+Σ[k=5～x]{(k+1)(k+2)(k+3)/6}=(x+1)(x+2)(x+3)(x+4)/24
一般にy=kの行が(x+k)Ckとなりそうなので
これを仮定してy=k+1の行を求めると
((k+1)+k)Ck×2+Σ[m=k+2～x](m+k)Ck=(x+k+1)C(k+1)
なのでy=nのとき(x+n)Cn
S[n]はy=n-1のときのx=nの値なので
S[n]=(2n-1)C(n-1)
|
|
|
| ■50623 / ResNo.4) |
Re[4]: カタラン数
|
□投稿者/ 富士 一般人(2回)-(2021/02/13(Sat) 09:57:19)
| ありがとうございました。
とても説明が分かりやすかったです。
|
解決済み! |
|
■記事リスト /
レス記事表示 →
[親記事-4]
|
で表示されます。
で表示されます。
場合の数(2)