Question

五個(gè)島嶼修四座橋（要任意兩島都能溝通），求修橋的總方法數(shù)．

Answer 1

考點(diǎn)：排列、組合及簡(jiǎn)單計(jì)數(shù)問(wèn)題

專(zhuān)題：排列組合

分析：如果五個(gè)島嶼任意兩個(gè)都有橋相連，則共需要

C

2 5

=10座橋，從中選出四座，共有：

C

4 10

=210種不同的選法，（1）如果這四座橋只連通四個(gè)島嶼，剩下一個(gè)島嶼與其它島嶼不連，則共有：

C

4 5

•

C

4 6

5種情況，（2）如果這四座橋連通五個(gè)島嶼，但三個(gè)相連，另外兩個(gè)相連，則共有：

C

3 5

•

C

2 2

種情況；除去（1）（2）其它情況均能保證任意兩島都能溝通，相減可得答案．

解答： 解：如果五個(gè)島嶼任意兩個(gè)都有橋相連，則共需要

C

2 5

=10座橋，
從中選出四座，共有：

C

4 10

=210種不同的選法，
（1）如果這四座橋只連通四個(gè)島嶼，剩下一個(gè)島嶼與其它島嶼不連，
則共有：

C

4 5

•

C

4 6

=75種情況，
（2）如果這四座橋連通五個(gè)島嶼，但三個(gè)相連，另外兩個(gè)相連，
則共有：

C

3 5

•

C

2 2

=10種情況；
除去（1）（2）其它情況均能保證任意兩島都能溝通，
故修橋的總方法數(shù)有：210-（75+10）=125種．

點(diǎn)評(píng)：本題考查的知識(shí)點(diǎn)排列組合，本題從下面解答難度較大，故應(yīng)該先排除不滿足條件的情況，進(jìn)而由總數(shù)相減得到答案．