|
uchinyan |
|
こんにちは。
今回(408回)の問題の一般解 n^(n-2) の証明ができたようなので、ご参考までに紹介しておきます。 また、長くなります。ご容赦を。 証明だけを読むと、何でこんなことを考えるのかちょっと分かりにくい箇所もあると思います。 そこで、具体的な証明を始める前に、まず、証明に至った考えの流れを示します。 * 考え方の経緯 ちこりんさんが#23221にご指摘のように、結果が予想できているので、数学的帰納法を使うのが自然です。 しかし、前回の私の方法(#23215)では、具体的なグラフの形状に注目しているので、n を増やすと新たなf(n;...)が 増えていってしまい漸化式がうまく作れません。そこで、他の方法を模索しました。 グラフを特徴付けるものとして、ある点に集まった線の本数があります。 そこで、グラフの一点Aを固定し、そこから出ている線の本数を考えます。n=5 では、1本、2本、3本、4本の場合があります。 これは、点Aを掴んでグラフを持ち上げたときにできる形状に注目していることに対応します。 今回の問題(点の個数 = 線の本数 + 1)では、ループはありえないので、結局、木構造のグラフを対象にしていることになります。 (このことは、本当は証明が必要でしょうが、ループは、点の個数 = 線の本数 であることから明らかなので省略します。) したがって、一点Aを固定するというのは、木構造グラフの根(ルート)を固定していることに対応します。 すぐに分かりますが、この方法ならば、各線の先につなげるグラフの個数は残りの点の個数の関数で書けます。 ただ、線が2本以上は、残りの点をどの線とつなげるかで、場合分けが発生します。これは必ずしも簡単ではないのですが、 地道に考えれば計算できて、n点のグラフの総数をf(n)とすると、結局、次のような式が導けます。 f(n) = ��(m=1,n-1) { (n-1)C(m) ��(p1+p2+...+pm=n-m-1) {(n-m-1)!/p1!p2!...pm! * f(p1 + 1)f(p2 + 1)...f(pm + 1)} } ここで、��(p1+p2+...+pm=n-m-1) は、和が n-m-1 になるような0以上のm個の整数に関して和をとることを意味します。 また、f(1)=1 とします。 この式の右辺のf(..)の引数はnより小さいので、右辺に帰納法の仮定を適用して計算すれば、原理的には、証明が可能です。 しかし、この式はそれなりに美しいのですが、複雑であるので、(多分できると思いますが、)うまい計算が思いつきませんでした．．． そこで、さらに方向転換をします。 計算が難しいのは、点Aから出ている線の先の状況をまじめに計算したからで、これすらも漸化式にできないか、 と考えました。すなわち、上のf(n)の2番目の�瑤慮紊�g(m,n-m-1)(= g(m,n-1-m))とおいてしまって、つまり、 f(n) = ��(m=1,n-1) { (n-1)C(m) * g(m,n-m-1) } として、g(p,q)の漸化式を新たに考えます。 このとき、g(p,q)は、他のどの点ともつながれていない孤立点を含むグラフも許している点に注意する必要があります。 最初、これは問題ではないかと思ったのですが、この式の意味を考えると納得できます。 すなわち、この式は、点Aからm本出ている線をそれらの線を切るように分割し、点Aを含まない側のグラフの個数を g(m,n-m-1)とすることを意味します。こうした分割からは、孤立点が出現してもおかしくありません。 後で示す証明は、この方針で行いました。後の証明で見るように、この孤立点の存在が、問題を簡単にします。 これと並行して、グラフの個数の母関数とでもいうべきものも、考えていました。 今、点Aにk本線が集まるグラフの個数をx^kの係数とするようなxの関数をf(n,x)とします。つまり、 f(n,x) = ��(k=1,n-1) (点Aにk本の線が集まるグラフの個数) * x^k 何でこんなものを考えていたかというと、二項係数の計算で (1+x)^n を使用することがよくありますが、 それを真似しようとしたわけです。明らかに、 f(n) = f(n,1) です。n=2,3,4,5ぐらいの具体的な値で計算してみると、 f(n,x) = x * (x + (n-1))^(n-2) になりそうな予想がつきます。 残念ながらこれを直接に証明する方法は思いついていないのですが、この予想は、後の証明で一部参考にします。 * 一般解が n^(n-2) となる証明 n点を与えた場合の題意を満たすグラフの総数をf(n)とします。 グラフの一点Aを固定し、その点に集まる線の本数に注目します。 本数がm本の場合、それらの線を切って、点Aを含まない側のグラフの個数を考えます。これは、 g(p,q)を、p個の点で外とつながり、q個の点は外とつながっていないグラフの個数とすると、g(m,n-1-m)と書けます。 一方、m本の線のAとは異なる側のm個の点を選ぶのに (n-1)C(m) 必要なので、 f(n) = ��(m=1,n-1) (n-1)C(m) * g(m,n-1-m) このとき、g(m,n-1-m)には、他の点とはつながれていない孤立点を含むグラフも許されことに注意します。 次に、g(p,q)について考えます。このグラフ自体、p個の点が、q個の点からなる部分グラフとr個の点でつながっているので、 r個の点を選ぶのに (q)C(r) 通り、r個の点をp個の点と孤立点を許してつなぐのに p^r 通り、部分グラフの個数がg(r,q-r)個、 だから、 g(p,q) = ��(r=1,q) (q)C(r) * p^r * g(r,q-r) (p個の点に孤立点を許したことで、p個の点をr個の点とつなぐつなぎ方が非常に簡単になっていることに注意。) ただし、明らかに、g(p,0) = 1 です。(この場合、p個の孤立点があるだけになります。) f(n)の式と比べると、次が分かります。 f(n) = g(1,n-1) 後は、gについての漸化式を解けばよいのですが、直接に解くのは簡単ではなさそうです。 しかし、二項係数の出現などに注意して、次を利用することを考えます。 (ここで、母関数 f(n,x) も頭におきながら次式を導いています。) (p+q)^(q-1) = ��(r=0,q-1) (q-1)C(r) * p^r * q^(q-1-r) p * (p+q)^(q-1) = ��(r=0,q-1) (q-1)C(r) * p^(r+1) * q^(q-1-r) = ... = ��(r=1,q) (q)C(r) * p^r * r * q^(q-r-1) (r -> r-1 とし、(q-1)C(r-1) = r/q * (q)C(r) を使っています。) なので、 g(p,q) = p * (p+q)^(q-1) が解となり、g(p,0) = 1 も満たすという条件から、これに一意に決定します。 これより、 f(n) = g(1,n-1) = n^(n-2) となります。 これで、一応、証明はできました。 また、式の意味より、 f(n,x) = g(x,n-1) = x * (x + (n-1))^(n-2) もいえます。 |
|
7月4日（日） 15:46:54
23222 |