数列
以前こんな問題について書いた。 c-and-a.hatenablog.com 問題設定 人でじゃんけんを行い、あいこであればもう一度、勝ちが出れば、勝った人たちでまたじゃんけんを行う。これを最後に一人出るまで繰り返す。優勝者がでるまでに行ったじゃんけんの回数の期待…
前回もとめた母関数をマクローリン展開して、係数を求め、の一般項を求めることが出来た。 正直マクローリン展開云々のところは計算が大変だったので、ここに転記しない(気が向いたらそのうち書く)。さて、こうなった。なおとし、のとき、2項目はとする。…
前回の結論 じゃんけんの勝ち残り戦の優勝が決まるまでの回数の期待値を係数とする母関数はを満たすことが分かった。以下でこの関数方程式を解いていく。色々やってみたって感じがにじみ出ている式変形でスマートでなく、結果上手くいったものであるんので多…
普通大人数でじゃんけんをするときはなかなか勝ちが決まらないため、何グループかに分割して行う。 では、分割しないで、勝ち残りで優勝を決めるまで行うとどれほどかかるのだろうか? 問題設定 人でじゃんけんを行い、あいこであればもう一度、勝ちが出れば…
n次元ランダムウォークの再帰確率の続き c-and-a.hatenablog.comつづいて、条件を満たす数列を求めるためにを決定するのだがほぼ1次元ランダムウォークの再帰確率(2)で行った通りなので、結果だけ示すとする。 c-and-a.hatenablog.com結果求める数列はとな…
1次元ランダムウォーク同様、時刻に位置に動点がある確率をで表す。また、第軸正方向に動かすベクトルをとおけば、漸化式はとなる。 また条件はかつは実数とする。まず、条件を無視して漸化式の一般解を求めよう。(1次元ランダムウォークの方法をなぞる)と…
1次元ランダムウォークの再帰確率(2)の続き c-and-a.hatenablog.com再帰確率とは、ランダムウォークを無限(つまりかなり長い間)に続けたとき、動点が原点に少なくとも一回戻っている確率である。まず、時刻に初めて原点に戻った確率を、時刻に(初めてでな…
1次元ランダムウォークの再帰確率(1)の続き c-and-a.hatenablog.com一般解は求まったので、次はの条件を付けよう。 この条件はクロネッカーのデルタを用いればとかける。前のページで求めた、一般解に代入すればとなり、またとおけばここでであるので、と…
これまで書いてきた、漸化式のお話はこの記事のアバンにするつもりだったのだが、つい、項間での一般解が求まってしまい、厖大な量になってしまった。 1次元ランダムウォークとは 「時刻で原点にある点が時刻が増える度に、右(の正方向)または左(の負方向)の…
隣接項間漸化式の線形的アプローチ(6)の続き c-and-a.hatenablog.com具体例 例えば、漸化式がであったときの一般解を求めてみよう。この漸化式の特性方程式はと、上で因数分解できる(当然こうなるよう係数を決定した)。の解の一方をとすると、他方はである。…
隣接n項間漸化式の線形的アプローチ(5)の続き c-and-a.hatenablog.comさて、隣接項間漸化式の一般解を求めよう。 この漸化式の特性方程式は1次または2次の実係数多項式の積に因数分解できる。また、の個の基底は、とかける。 の個の基底は、の2解を用いて、…
隣接項間漸化式の線形的アプローチ(4)の続き c-and-a.hatenablog.com実は、上の既約多項式の次数は高々2であることに気づいた。 c-and-a.hatenablog.comもう少し早く気づいていれば、これまでの議論をより簡単にできたのに…(その場の思い付きで書くからこう…
隣接n項間漸化式の線形的アプローチ(3)の続き c-and-a.hatenablog.com であるとして、という数列を考える。であることは既に示した。つぎに、のときを示す。 に対応する漸化式の左辺にを代入するととなる。ここで、は、を含む多項式と含まない多項式に分解で…
隣接項間漸化式(2)の続き c-and-a.hatenablog.com良いアルファベットがなくなりそうなので、一度添え字をリセットするとともに、これまでの振り返りをする。次のような隣接項間漸化式を考えているのだった。なお、は実数列、は実数でである。 また、この特性…
隣接n項間漸化式の線形的アプローチの続き c-and-a.hatenablog.com 特性方程式がになる漸化式の解の集合をと表す。 をが満たすとする。剰余の定理からとするとを満たす次多項式と高々次多項式の存在が保証される。ここで、 と表すととなり、漸化式はと変形で…
実数列の隣接項間漸化式の一般解を考える。なお、かつとする。 c-and-a.hatenablog.com 隣接三項間漸化式の線形的アプローチで示したように、隣接3項間漸化式の解の集合は2次元ベクトル空間である。同様な議論で、(1)の解の集合は、次元ベクトル空間である…
隣接三項間漸化式の線形的アプローチの続き。 c-and-a.hatenablog.com (i) のとき 、つまりとなりである。また、とすると、はより、写像により、同様にとなる。ここで、(2)よりとなるは存在しない。つまりとは一次独立であり、とも一次独立であるといえる。 …
の漸化式を満たす実数列を考察する。 まず、数列とが(1)を満たすとする。このとき、任意のに対して を満たす。本来はまだ確かめる条件はあるが、殆ど自明であることばかりなのでそれらは割愛する。これら2式から、(1)の解の集合は上のベクトル空間であること…