★ 場合の数の問題 No.86948 について, 漸化式の話です. # もう一つのスレッドがあったので話が混線しなくて都合がいいやと思ってたら, # 書いてる間に消えてた (まあそりゃ管理の都合上は消すのが正当よね) ので, # 新規にスレッドを建てます (内容コピーしてて助かった^^;).
## 内容は完全ではありません (途中まではともかく後半は話が完結してない). 以下, x個のボールの「間」と言ったら便宜上ボールの並びの両端を含む x+1 箇所を指すこととします. 求める場合の数を a[n], 0≤m≤n に対し「ちょうど m 色のボールが隣り合う」場合の数を a^(m)[n] と書く (ただし, a^(0)[n]=a[n], また誤解の虞が無いならば a^(1)[n], a^(2)[n], … の代わりに a'[n], a''[n], … のように ' の個数で区別する記法でも構わない※もちろん微分ではない) ことにすれば, [*] Σ_[m=0,1,…n] a^(m)[n] = (2n)!/(2!)^n. (2n 個すべての並べ方) [0] a[n-1] 通りの各場合に 2(n-1)+1 個の「間」から n 色目を入れる2箇所を選ぶ: (2n-1)C2 * a[n-1] 通り, [1] a'[n-1] 通りの各場合に同色隣り合うところの間に n 色目を一つ入れて, 2(n-1)+1 個の並びにした後, もう一つはさっきの一個目の両隣を除く ((2(n-1)+1)+1)-2 個の「間」から1箇所選ぶ: (2n-2) a'[n-1] 通り, [2] a''[n-1] 通りの各場合について, n 色目はそれぞれ同色隣り合う2色のそれぞれの間に入れる一通り: a''[n-1] 通り. が a[n] に寄与し, 3 色以上が同色隣り合っていたら a[n] へは寄与しないので, a[n]=(2n-1)(2n-2)a[n-1]/2+(2n-2) a'[n-1]+a''[n-1], a[n-1]+a'[n-1]+a''[n-1]+…+a^(n-1)[n-1]=(2(n-1))!/(2!)^(n-1). となるはずです. # 便宜的に a[0]=1, a[1]=0, a'[1]=1 および m>n のとき a^(m)[n]=0 とすると, # この漸化式は n=1,2,3 までは解けて, a[2]=2, a[3]=30 となります. # 実際に書きならべるとこれは正しいように思います.
n≥4 のときは条件が足りずに解けませんが, 例えば a'[n] も同様に, n 色並べたとき 1 色のみが隣り合う場合ということは [i] a[n-1] 通りの各場合に n 色目を同じ個所の「間」に2つ並べて入れる [ii] a'[n-1] 通りの各場合に, その同色隣り合う箇所を保ったまま n 色目を残りの「間」から2箇所それぞれ入れる [iii] a''[n-1] 通りの各場合に, 同色隣り合ううちの1色は潰すようにあいだに n 色目をひとつ入れて, 残りは同色隣り合うのを保つように「間」に入れる [iv] a'''[n-1] 通りの各場合は, n 色目は同色隣り合う3色のうち2色を潰すように入れる [v] n-1 色並べて4色以上が同色隣り合う場合は a'[n] に寄与しない といったように, ほかの a^(m)[n-1] たちの情報も使えばわかるはずで, 二項間の連立漸化式が a^(0)[n]=(2n-1)(2n-2)a[n-1]/2+(2n-2) a'[n-1]+a''[n-1], a^(1)[n]= f[1,0](n)a[n-1]+f[1,1](n)a'[n-1]+f[1,2](n)a''[n-1]+f[1,3](n)a'''[n-1], … a^(m)[n]=f[m,m-1](n)a^(m-1)[n-1]+f[m,m](n)a^(m)[n-1]+f[m,m+1](n)a^(m+1)[n-1]+f[m,m+2](n)a^(m+2)[n-1], … a^(n-2)[n]=f[n-2,n-3](n)a^(n-3)[n-1]+f[n-2,n-2](n)a^(n-2)[n-1]+f[n-2,n-1](n)a^(n-1)[n-1], a^(n-1)[n]=f[n-1,n-2](n)a^(n-2)[n-1]+f[n-1,n-1](n)a^(n-1)[n-1]. 初期条件: a[n-1]+a'[n-1]+a''[n-1]+…+a^(n-1)[n-1]=(2n-2)!/(2!)^(n-1). のような形で得られるはずです (係数となる n の式 f[i,j](n) は真面目に見れば具体的に組合せの数などを用いて書けると思いますが, 私はそこまで気力が無い). # 上の [i]-[v] が正しい (かつ, それを a^(m)[n] についての記述に正しく読み替えた) ならば # おそらく 0 になるであろう箇所は省きましたが, 上に出てこない f[i,j](n) が実際はあったならすみません. これは小さい n に対して順番にということなら高校までの知識の範囲である程度までは計算できるでしょうし, 一般に解くには大学初年度級の「行列」の知識が要るものの理屈の上では解けるはずです (が, 私がそれを計算できるとかするとかという意味ではない).
{a'[n]},{a''[n]},… などを用いない {a[n]} 単独の高階漸化式がどうなるかは見ていませんが, a[n]を表すのに (a[0],a[1],) a[2],…,a[n-1] 全部必要な気がします.
|
No.86960 - 2023/12/17(Sun) 15:13:51
|