第408問の解答


問題[場合の数]

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

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


解答例1

あ〜く@ぴかぴかの(略さん、CRYING DOLPHINさん、Taroさん、まるケンさんtomhさん、BossFさん、小西孝一さん、他

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

参考図1

辺の数は全部で5つ頂点から2個選ぶ、5210通りあります。
従って、10個から4本選ぶのは、全部で104210通りあります。

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

(タイプ1)4頂点しか結んでいない場合

最初に5個頂点から4個選ぶのが、545通りあります。
選んだ4個頂点辺の数は全部で426通り、これらから4本選ぶのは6415通り
従って、タイプ1は全部で54×64=5×15=75通りとなります。

(タイプ2)三角形と1本の辺になる場合

5個頂点から3個選ぶ5310通りあります。

よって、求める場合の数は、
 210−(75+10)=125通り
となります。

答:  125通り

以上


解答例2

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

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

参考図2

(タイプ1)最大が2本のとき

5つの頂点1列に並んだ形状となります。
従って、5つ頂点5個並べる順列の数=55=5!=5×4×3×2×1=120通り
ただし左右ひっくり返したものは同じものになるので、この半分の60通りになります。

(タイプ2)最大が3本のとき

3本の辺が集まる1つの頂点と、これから2つ続く頂点が決まれば、あとの2頂点は自動的に決まるので、53=5×4×3=60通りとなります。

(タイプ3)最大が4本のとき

4本の辺が集まる1つの頂点が決まれば、あとの4頂点は自動的に決まるので、
5
15通りとなります。

従って、求める個数は、
 60+60+5=125通り
になります。


解答例3

姉小路さん、他

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

参考図3−0

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

参考図3

各頂点にはからまでの番号を振っておき、頂点1を固定しておきます。
さて頂点2にぶら下がっている頂点の個数をr個とすると、0≦r≦(n-2)となります。

まず頂点1頂点2を除く(n-2)個頂点からr個選ぶのが、n-2Cr通り。

頂点2からr個頂点がぶら下がるツリーは、r+1通り
また頂点1から残り(n-r-2)個頂点がぶら下がるツリーn-r-1通り

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

nΣ(r=0..n-2){n-2Cr×r+1×(n-r-1)×n-r-1} ・・・ (1)

すると、
 31C0×1××21C1×2××1
  
=1××2×+1××1×
  
=2+1

 t42C0×1××32C1×2××22C2×3××1
  
=1××3×+2××2×+1××1×
  
=9+4+3=16

 t53C0×1××43C1×2××33C2×3××23C3×4××1
  
=1××4×16+3××3×+3××2×+1×16×1×
  
=64+27+18+16125

と順次求まります。


解答例4

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

nn-2と予想されますが、(1)の漸化式ではこのことを証明するのが難しいので、
複数のツリーが集まったものに拡張して考えることにしましょう。
p本ツリーが集まった場合で、これらにぶら下がった頂点の個数が全部でq個のときの場合の数を、
g(p、q)で表すことにします。

参考図4−0

容易に、g(p、0)g(p、1)g(p、2)p(p+2)と求まります。
どうも
 g(p、q)=p(p+q)q-1
 ・・・ (2)
が成り立ちそうです。これをに関する漸化式を求めて証明することにしましょう。

参考図4

p本ツリーで固定された各頂点と呼びます)に直接ぶら下がる頂点の個数とします。
1≦rで、これらを選ぶのがqCr通り

このr個の頂点として考えると、r本ツリー(q-r)個の頂点がぶら下がっているので、
全部でg(r、q−r)通りあります。

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

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

g(p、q)=Σ(r=1..q){qCr×pr×g(r、q-r)} ・・・ (3)

あるの値未満について(2)が成り立つと仮定しましょう。
すると(3)より、
 g(p、q)=Σ(r=1..q){qCr×pr×r×q-r-1
      =Σ(r=1..q){(q-1Cr-1×q/r)×pr×r×q-r-1
      =Σ(r=0..q-1){q-1Cr×pr+1×q-r
      =p(p+q)q-1 
となり、についても(2)が成り立ちます。

従って、数学的帰納法より(2)が成り立つことが分かります。

とくにツリー1本のとき、(2)より、
 tng(1、n-1)=1×(1+n-1)n-1-1n-2
が得られます。

(参考)1≦p、q≦5のときのg(p、q)

参考図4−1


解答例5

Prüfer符号(下図参照)との対応によって(2)を直接証明してみます

参考図5−0

頂点n個のときのツリー全体をT、1〜nまでの数をn-2個並べてできる集合をSとし、t∈Tについて、Prüfer符号)を次のように定めます。

参考図5−1

(1):端点(つながっている辺が1本しかない頂点)のうち最小番号のものをa1とし、a1につながっている頂点b1とします。

(2):tからa1を除いたツリーについて、同様にして最小番号端点a2、a2につながる頂点b2を求めます。

以下、(n-2)回の操作を行って得たbk(k=0..n-2)を並べて、={b1b2・・・bn-2}とします。
このとき、1≦bkより、s∈Sとなります。

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

参考図5−2

まず、N={1、2、・・・、}、={b1b2・・・bn-2}(1≦bk)とします。

(1):Nに属する整数に含まれないものの最小値a1とし、a1b1を結びます。

(2):Nからa1を、からb1をそれぞれ除き、同様に求めたa2b2を結びます。

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

できあがった図形とすると、にはn個頂点(n-1)本が含まれます。

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

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