次の問題を教えてください。
よろしくお願いします。
n色のボールがそれぞれ2個ずつあり、この2n個のボールを一列に並べる。同じ色のボールが隣り合わないような並べ方は何通りあるか。ただし、同じ色のボールは区別しないものとする.
|
No.86948 - 2023/12/16(Sat) 09:25:26
| ☆ Re: 場合の数の問題 / ast | | | さすがOEIS, なんでもあるなぁ……
> 式は Σ[k=0〜n](-1)^(n-k)*nCk*(n+k)!/2^k と表されるようです。
については, すでに挙げられた
> Σ(-1)^k × nCk × (2n-k)!/2^(n-k) でしょうか。
で n-k を改めて k と置いた (逆向きに足した) ものに一致しますので齟齬はないですね.
# i.e. j=n-k とおくと k=n-j, nCk=nCj, 2n-k=n+j, k=0,…,n ↔ j=n,…,0 で
# Σ_[k=0,…,n] (-1)^k nCk (2n-k)!/2^(n-k) = Σ_[j=n,…,0] (-1)^(n-j) nCj (n+j)!/2^j.
|
No.86965 - 2023/12/17(Sun) 17:40:25 |
| ☆ Re: 場合の数の問題 / ast | | | まだ不完全 (ほとんど n=3 のときしか検討してない, 少なくとも n=4 くらいはちゃんとやらないといけないだろうが未検討) ですが.
# きちんと検討してから書けと言われそうではあるが, どう検討していいものやらよくわからないので……^^A;
漸化式は:
a[n]/n! = (2n-1)a[n-1]/(n-1)! + a[n-2]/(n-2)!
と見ると, n! は塗る色の順番の数, a[n]/n! はどのボール対から順番に塗るかのパターン数と思えるから, a[n] は
[i] n-2 色のパターンのあとに, n-1,n 番目の 2 色を交互に: 1 通り.
[ii] n-1 色のパターンに対して 2(n-1)+1 個の「間」の k+1 番目と (k+n-1 mod 2n-1)+1 番目 (k=0,1,…,2n-2) に n 色目: 2n-1 通り.
というように解釈するのではないかと推測します.
ただし, [ii] はこれでいいのか, なぜ [i] と [ii](誤っていればその修正バージョン) でパターンを尽くせるのか etc., 全然見当つかないレベルで検討できていません.
# もしや [ii] は一方が 2n-1 箇所を一周するあいだに他方が n-1 周する位置とする必要があるか?
|
No.86967 - 2023/12/18(Mon) 12:43:13 |
|
