数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

■50619 / 親記事) 　カタラン数
  ▼■
□投稿者/ 冨士 一般人(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などです。
    よろしくお願いします。
引用返信/返信 [メール受信/OFF] 削除キー/
■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
    と表されます。

引用返信/返信 [メール受信/OFF] 削除キー/
■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)になりそうな気がするのですが、どう求めるのかは分かりません。
引用返信/返信 [メール受信/OFF] 削除キー/
■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)

引用返信/返信 [メール受信/OFF] 削除キー/
■50623 / ResNo.4) 　Re[4]: カタラン数
□投稿者/ 富士 一般人(2回)-(2021/02/13(Sat) 09:57:19)
    ありがとうございました。
    とても説明が分かりやすかったです。
解決済み!
引用返信/返信 [メール受信/OFF] 削除キー/


スレッド内ページ移動 / << 0 >>

このスレッドに書きこむ
Mode/　 Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター