D - D-infinite Editorial
by
semiexp
厳密性のかけらもない近似による解法
厳密性がないところに(?)と書いておきます
\(a\) 回の a の現れについて、その次に現れる文字は b か c ですが、i 回目に出てくる a の次に b か c のどちらが現れるか、という列を固定します。b や c についても同様の列を固定しておきます。
これを固定すると、最初の文字を決めたときに文字列全体が決まります。ただし、実際には「もうすでに使い切ってしまった文字に到達してしまう」場合が考えられますが、そのような場合は比較的少ないと考えられるので(←?)無視します。また、文字列の最後の次の文字というのは存在しませんが、これも無視します(?)。
a の次に b が現れる事象が \(x\) 回のとき、各隣接ペアの個数は次のようになります:
a->b: \(x\)a->c: \(a-x\)b->a: \(a+b-c-x\)b->c: \(x+c-a\)c->a: \(x+c-b\)c->b: \(b-x\)
なので、最初に固定した 3 つの列の組の個数は
\[n(x) = \binom{a}{x} \binom{b}{x+c-a} \binom{c}{b-x} \]
となります。本来は、有効な \(x\) 全体にわたって \(n(x)\) の和をとる必要があるのですが、\(n(x)\) が最大値をとる \(x\) の寄与が十分支配的であると近似します(本来の和は、最大値の高々 \(a+b+c\) 倍であることから、log をとる今回の設定ではこの違いは無視できます)。
ここで、\(n(x)\) が最大値をとる \(x\) を求めるために、\(\frac{n(x+1)}{n(x)}\) を考えると、およそ(±1 の差は無視して)
\[ \frac{n(x+1)}{n(x)} = \frac{a-x}{x} \cdot \frac{b-c+a-x}{x+c-a} \cdot \frac{b-x}{c-b+x} \]
になります。最大値を求めるためには \(\frac{n(x+1)}{n(x)} = 1\) となる \(x\) を探せばよいのですが、\(x=\frac{a+b-c}{2}\) のときにこれが成り立つことが確かめられます。
このときの \(n(x)\) の値を評価すると、
\[ \binom{a}{\frac{a+b-c}{2}} \cdot \binom{b}{\frac{b+c-a}{2}} \cdot \binom{c}{\frac{c+a-b}{2}} \]
となります。Stirling 近似により、
\[ \log \binom{a}{\frac{a+b-c}{2}} \simeq a \log a - \frac{a+b-c}{2} \log \frac{a+b-c}{2} - \frac{a+c-b}{2} \log \frac{a+c-b}{2} \]
です。\(b, c\) についても同様にすると、
\[\log n(x) \sim a \log a + b \log b + c \log c - (a + b - c) \log \frac{a+b-c}{2} - (b + c - a) \log \frac{b+c-a}{2} - (c + a - b) \log \frac{c+a-b}{2} \]
を得ます。よって、
\[ p/q = \frac{a^a \cdot b^b \cdot c^c \cdot 2^{a+b+c}}{(a+b-c)^{a+b-c} \cdot (b+c-a)^{b+c-a} \cdot (c+a-b)^{c+a-b}} \]
を得ます。
posted:
last update: