第４０８問の解答

問題［場合の数］

ある湖の上に、５つの島があります。
この５つの島の間を４つの橋で結んで、各島の間を行き来できるようにしようという計画が持ち上がりました。
では、橋を使ってどの島にも行き来できるようにするような橋のかけ方（注）は、何通り考えられるでしょうか。

（注）常識的でない橋のかけ方（１つの島を飛び越して別の島に橋をかける、等）をしても構わないものとします。
橋を渡る、以外の手段は使わないものとします。もちろん、橋を複数回利用しないと行けない島があっても構いません。

解答例１

あ～く＠ぴかぴかの（略さん、CRYING DOLPHINさん、Taroさん、まるケンさん、tomhさん、BossFさん、小西孝一さん、他

島を頂点、橋を辺で表すことにします。全ての頂点どうしを辺で結んだ場合から不適なものを除いて数えることにしましょう。

辺の数は全部で５つの頂点から２個選ぶ、₅Ｃ₂＝１０通りあります。
従って、１０個の辺から４本選ぶのは、全部で₁₀Ｃ₄＝２１０通りあります。

さて、これらから題意に不適なものは２つのタイプがあります。

（タイプ１）４頂点しか結んでいない場合

最初に５個の頂点から４個選ぶのが、₅Ｃ₄＝５通りあります。
選んだ４個の頂点の辺の数は全部で₄Ｃ₂＝６通り、これらから４本選ぶのは₆Ｃ₄＝１５通り、
従って、タイプ１は全部で₅Ｃ₄×₆Ｃ₄＝５×１５＝７５通りとなります。

（タイプ２）三角形と１本の辺になる場合

５個の頂点から３個選ぶ₅Ｃ₃＝１０通りあります。

よって、求める場合の数は、
　２１０－（７５＋１０）＝１２５通り
となります。

答：　１２５通り

以上

解答例２

まるケンさん、圭太さん、なかさん、tomhさん、DrKさん、トトロ＠Ｎさん、ちこりんさん、おかひで博士さん、kasamaさん、他

１つの頂点から結ばれた辺の個数の最大値が何本かで場合分けしてみます。

（タイプ１）最大が２本のとき

５つの頂点が１列に並んだ形状となります。
従って、５つの頂点を５個並べる順列の数＝₅Ｐ₅＝５！＝５×４×３×２×１＝１２０通り、
ただし左右ひっくり返したものは同じものになるので、この半分の６０通りになります。

（タイプ２）最大が３本のとき

３本の辺が集まる１つの頂点と、これから２つ続く頂点が決まれば、あとの２頂点は自動的に決まるので、₅Ｐ₃＝５×４×３＝６０通りとなります。

（タイプ３）最大が４本のとき

４本の辺が集まる１つの頂点が決まれば、あとの４頂点は自動的に決まるので、₅Ｃ₁＝５通りとなります。

従って、求める個数は、
　６０＋６０＋５＝１２５通り
になります。

解答例３

姉小路さん、他

頂点の数がｎ個のときをｔ_nで表して、漸化式を求めて数えることににします。
ただし、形状に注目すると一般化できないので、１つの頂点を固定したツリー状で数えることにします。

n≦3までの個数は、上記のようにｔ₁＝１、ｔ₂＝１、ｔ₃＝３と簡単に求まります。
n≧3のときの漸化式を下図で考えてみましょう。

各頂点には１からｎまでの番号を振っておき、頂点１を固定しておきます。
さて頂点２にぶら下がっている頂点の個数をｒ個とすると、０≦r≦（n-2）となります。

まず頂点１と頂点２を除く（n-2）個の頂点からｒ個選ぶのが、_n-2C_r通り。

頂点２からｒ個の頂点がぶら下がるツリーは、ｔ_r+1通り、
また頂点１から残り（n-r-２）個の頂点がぶら下がるツリーはｔ_n-r-1通り。

そして、頂点２が頂点１からのツリーのどの頂点にぶら下がるかは、（n-r-1）通り、
従って、漸化式は下記のようになります。

ｔ_n＝Σ_(r=0..n-2){_n-2C_r×ｔ_r+1×(n-r-1)×ｔ_n-r-1｝　・・・　（１）

すると、
　ｔ₃＝₁C₀×ｔ₁×２×ｔ₂＋₁C₁×ｔ₂×１×ｔ₁＝１×１×２×１＋１×１×１×１
　　＝２＋１＝３

　ｔ₄＝₂C₀×ｔ₁×３×ｔ₃＋₂C₁×ｔ₂×２×ｔ₂＋₂C₂×ｔ₃×１×ｔ₁＝１×１×３×３＋２×１×２×１＋１×３×１×１
　　＝９＋４＋３＝１６

　ｔ₅＝₃C₀×ｔ₁×４×ｔ₄＋₃C₁×ｔ₂×３×ｔ₃＋₃C₂×ｔ₃×２×ｔ₂＋₃C₃×ｔ₄×１×ｔ₁＝１×１×４×１６＋３×１×３×３＋３×３×２×１＋１×１６×１×１
　　＝６４＋２７＋１８＋１６＝１２５

と順次求まります。

解答例４

まるケンさん、uchinyanさん、他

ｔ_n＝ｎ^n-2と予想されますが、（１）の漸化式ではこのことを証明するのが難しいので、
複数のツリーが集まったものに拡張して考えることにしましょう。
ｐ本のツリーが集まった場合で、これらにぶら下がった頂点の個数が全部でｑ個のときの場合の数を、
ｇ（p、ｑ）で表すことにします。

容易に、ｇ（p、0）＝１、ｇ（p、１）＝ｐ、ｇ（p、２）＝ｐ（ｐ＋２）と求まります。
どうも
　ｇ（p、ｑ）＝ｐ（ｐ＋ｑ）^q-1　・・・　（２）
が成り立ちそうです。これをｑに関する漸化式を求めて証明することにしましょう。

ｐ本のツリーで固定された各頂点（根と呼びます）に直接ぶら下がる頂点の個数をｒとします。
１≦r≦ｑで、これらを選ぶのが_qC_r通り。

このｒ個の頂点を根として考えると、ｒ本のツリーに（q-r）個の頂点がぶら下がっているので、
全部でｇ（ｒ、ｑ－ｒ）通りあります。

そして、ｒ個の根が元のｐ個の根のどれにぶら下がるかは、それぞれｐ通りあるので、
全部でｐ^r通り。

従って漸化式は、下記のようになります。

ｇ（p、ｑ）＝Σ_(r=1..q){_qC_r×p^r×ｇ（r、ｑ-r）｝　・・・　（３）

あるｑの値未満について（２）が成り立つと仮定しましょう。
すると（３）より、
　ｇ（p、ｑ）＝Σ_(r=1..q){_qC_r×p^r×r×ｑ^q-r-1｝
　　　　　　＝Σ_(r=1..q){（_q-1C_r-1×q/r）×p^r×r×ｑ^q-r-1｝
　　　　　　＝Σ_(r=0..q-1){_q-1C_r×p^r+1×ｑ^q-r｝
　　　　　　＝ｐ(ｐ＋ｑ)^q-1となり、ｑについても（２）が成り立ちます。

従って、数学的帰納法より（２）が成り立つことが分かります。

とくにツリーが１本のとき、（２）より、
t_n＝g(1、n-1)＝１×（1+n-1）^n-1-1＝ｎ^n-2
が得られます。

（参考）１≦ｐ、ｑ≦５のときのｇ（p、ｑ）

解答例５

Prüfer符号（下図参照）との対応によって（２）を直接証明してみます。

頂点がｎ個のときのツリー全体をT、１～nまでの数をn-2個並べてできる集合をSとし、ｔ∈Tについて、ｓ（Prüfer符号）を次のように定めます。

（１）：端点（つながっている辺が１本しかない頂点）のうち最小番号のものをa₁とし、a₁につながっている頂点をb₁とします。

（２）：ｔからa₁を除いたツリーについて、同様にして最小番号の端点a₂と、a₂につながる頂点b₂を求めます。

以下、(n-2）回の操作を行って得たb_k(k=0..n-2)を並べて、ｓ＝｛b₁b₂・・・b_n-2｝とします。
このとき、１≦b_k≦ｎより、ｓ∈Sとなります。

逆に、ｓ∈Sに対し、ｔを次のように定めます。

まず、N＝｛1、２、・・・、ｎ｝、ｓ＝｛b₁b₂・・・b_n-2｝（１≦b_k≦ｎ）とします。

（１）：Nに属する整数でｓに含まれないものの最小値をa₁とし、a₁とb₁を結びます。

（２）：Nからa₁を、ｓからb₁をそれぞれ除き、同様に求めたa₂とb₂を結びます。

以下、(n-2）回の操作を行うと、ｓはなくなり、Nには２個の整数が残ります。
残ったNの２整数に対する２頂点を結んで操作を終えます。

できあがった図形をｔとすると、ｔにはn個の頂点と（n-1）本の辺が含まれます。

もしｔがｐ本の（つながっていない）ツリーに分かれていたとすると、m個の頂点からなるツリーには（m-1）本の辺からできているので、ｔの辺は（n-p）本となり矛盾します。
従って、ｔは１本のツリーとなり、ｔ∈Tになります。

以上から、Tの個数＝Sの個数＝ｎ^n-2となることが分かります。


	１つの頂点から結ばれた辺の個数の最大値が何本かで場合分けしてみます。（タイプ１）最大が２本のとき５つの頂点が１列に並んだ形状となります。従って、５つの頂点を５個並べる順列の数＝₅Ｐ₅＝５！＝５×４×３×２×１＝１２０通り、ただし左右ひっくり返したものは同じものになるので、この半分の６０通りになります。（タイプ２）最大が３本のとき３本の辺が集まる１つの頂点と、これから２つ続く頂点が決まれば、あとの２頂点は自動的に決まるので、₅Ｐ₃＝５×４×３＝６０通りとなります。（タイプ３）最大が４本のとき４本の辺が集まる１つの頂点が決まれば、あとの４頂点は自動的に決まるので、₅Ｃ₁＝５通りとなります。従って、求める個数は、　６０＋６０＋５＝１２５通りになります。


	頂点の数がｎ個のときをｔ_nで表して、漸化式を求めて数えることににします。ただし、形状に注目すると一般化できないので、１つの頂点を固定したツリー状で数えることにします。 n≦3までの個数は、上記のようにｔ₁＝１、ｔ₂＝１、ｔ₃＝３と簡単に求まります。 n≧3のときの漸化式を下図で考えてみましょう。各頂点には１からｎまでの番号を振っておき、頂点１を固定しておきます。さて頂点２にぶら下がっている頂点の個数をｒ個とすると、０≦r≦（n-2）となります。まず頂点１と頂点２を除く（n-2）個の頂点からｒ個選ぶのが、_n-2C_r通り。頂点２からｒ個の頂点がぶら下がるツリーは、ｔ_r+1通り、また頂点１から残り（n-r-２）個の頂点がぶら下がるツリーはｔ_n-r-1通り。そして、頂点２が頂点１からのツリーのどの頂点にぶら下がるかは、（n-r-1）通り、従って、漸化式は下記のようになります。ｔ_n＝Σ_(r=0..n-2){_n-2C_r×ｔ_r+1×(n-r-1)×ｔ_n-r-1｝　・・・　（１）すると、　ｔ₃＝₁C₀×ｔ₁×２×ｔ₂＋₁C₁×ｔ₂×１×ｔ₁＝１×１×２×１＋１×１×１×１　　＝２＋１＝３　ｔ₄＝₂C₀×ｔ₁×３×ｔ₃＋₂C₁×ｔ₂×２×ｔ₂＋₂C₂×ｔ₃×１×ｔ₁＝１×１×３×３＋２×１×２×１＋１×３×１×１　　＝９＋４＋３＝１６　ｔ₅＝₃C₀×ｔ₁×４×ｔ₄＋₃C₁×ｔ₂×３×ｔ₃＋₃C₂×ｔ₃×２×ｔ₂＋₃C₃×ｔ₄×１×ｔ₁＝１×１×４×１６＋３×１×３×３＋３×３×２×１＋１×１６×１×１　　＝６４＋２７＋１８＋１６＝１２５と順次求まります。


	ｔ_n＝ｎ^n-2と予想されますが、（１）の漸化式ではこのことを証明するのが難しいので、複数のツリーが集まったものに拡張して考えることにしましょう。ｐ本のツリーが集まった場合で、これらにぶら下がった頂点の個数が全部でｑ個のときの場合の数を、ｇ（p、ｑ）で表すことにします。容易に、ｇ（p、0）＝１、ｇ（p、１）＝ｐ、ｇ（p、２）＝ｐ（ｐ＋２）と求まります。どうも　ｇ（p、ｑ）＝ｐ（ｐ＋ｑ）^q-1　・・・　（２）が成り立ちそうです。これをｑに関する漸化式を求めて証明することにしましょう。ｐ本のツリーで固定された各頂点（根と呼びます）に直接ぶら下がる頂点の個数をｒとします。１≦r≦ｑで、これらを選ぶのが_qC_r通り。このｒ個の頂点を根として考えると、ｒ本のツリーに（q-r）個の頂点がぶら下がっているので、全部でｇ（ｒ、ｑ－ｒ）通りあります。そして、ｒ個の根が元のｐ個の根のどれにぶら下がるかは、それぞれｐ通りあるので、全部でｐ^r通り。従って漸化式は、下記のようになります。ｇ（p、ｑ）＝Σ_(r=1..q){_qC_r×p^r×ｇ（r、ｑ-r）｝　・・・　（３）あるｑの値未満について（２）が成り立つと仮定しましょう。すると（３）より、　ｇ（p、ｑ）＝Σ_(r=1..q){_qC_r×p^r×r×ｑ^q-r-1｝　　　　　　＝Σ_(r=1..q){（_q-1C_r-1×q/r）×p^r×r×ｑ^q-r-1｝　　　　　　＝Σ_(r=0..q-1){_q-1C_r×p^r+1×ｑ^q-r｝　　　　　　＝ｐ(ｐ＋ｑ)^q-1となり、ｑについても（２）が成り立ちます。従って、数学的帰納法より（２）が成り立つことが分かります。とくにツリーが１本のとき、（２）より、 t_n＝g(1、n-1)＝１×（1+n-1）^n-1-1＝ｎ^n-2 が得られます。（参考）１≦ｐ、ｑ≦５のときのｇ（p、ｑ）


	Prüfer符号（下図参照）との対応によって（２）を直接証明してみます。頂点がｎ個のときのツリー全体をT、１～nまでの数をn-2個並べてできる集合をSとし、ｔ∈Tについて、ｓ（Prüfer符号）を次のように定めます。（１）：端点（つながっている辺が１本しかない頂点）のうち最小番号のものをa₁とし、a₁につながっている頂点をb₁とします。（２）：ｔからa₁を除いたツリーについて、同様にして最小番号の端点a₂と、a₂につながる頂点b₂を求めます。以下、(n-2）回の操作を行って得たb_k(k=0..n-2)を並べて、ｓ＝｛b₁b₂・・・b_n-2｝とします。このとき、１≦b_k≦ｎより、ｓ∈Sとなります。逆に、ｓ∈Sに対し、ｔを次のように定めます。まず、N＝｛1、２、・・・、ｎ｝、ｓ＝｛b₁b₂・・・b_n-2｝（１≦b_k≦ｎ）とします。（１）：Nに属する整数でｓに含まれないものの最小値をa₁とし、a₁とb₁を結びます。（２）：Nからa₁を、ｓからb₁をそれぞれ除き、同様に求めたa₂とb₂を結びます。以下、(n-2）回の操作を行うと、ｓはなくなり、Nには２個の整数が残ります。残ったNの２整数に対する２頂点を結んで操作を終えます。できあがった図形をｔとすると、ｔにはn個の頂点と（n-1）本の辺が含まれます。もしｔがｐ本の（つながっていない）ツリーに分かれていたとすると、m個の頂点からなるツリーには（m-1）本の辺からできているので、ｔの辺は（n-p）本となり矛盾します。従って、ｔは１本のツリーとなり、ｔ∈Tになります。以上から、Tの個数＝Sの個数＝ｎ^n-2となることが分かります。