다섯 섬을 다리로 모두 연결하는 방법의 수

ⅰ) 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$ 중 섬 $\mathrm{A}$ 또는 $\mathrm{B}$에 연결된 섬이 $1$개인 경우

그림과 같이 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$를 잇는 다리가 $2$개 놓여야 하고, 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$ 중 어느 하나와 섬 $\mathrm{A}$, $\mathrm{B}$중 어느 하나를 잇는 다리가 $1$개 놓여야 한다. 따라서 이때의 방법의 수는 $\mathrm{_{3}} \mathrm{C} _{2} \times _{3} \mathrm{C} _{1} \times _{2} \mathrm{C} _{1} = 18$이다. ⅱ) 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$ 중 섬 $\mathrm{A}$ 또는 $\mathrm{B}$에 연결된 섬이 $2$개인 경우

그림과 같이 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$ 중 어느 두 섬이 섬 $\mathrm{A}$, $\mathrm{B}$중 어느 하나와 다리로 연결되고 (그림에서 $\mathrm{C}$, $\mathrm{D}$) 다리로 연결되지 않은 한 섬(그림에서 $\mathrm{E}$)은 다리로 연결된 어느 한 섬(그림에서 $\mathrm{C}$, $\mathrm{D}$)과 다리로 연결되면 된다. 따라서 이때의 방법의 수는 $\mathrm{_{3}} \mathrm{C} _{2} \times ( _{2} \mathrm{C} _{1} ) ^{2} \times _{2} \mathrm{C} _{1} = 24$이다. ⅲ) 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$ 중 섬 $\mathrm{A}$ 또는 $\mathrm{B}$에 연결된 섬이 $3$개인 경우

그림과 같이 섬 $\mathrm{C}$, $\mathrm{D}$, $\mathrm{E}$가 각각 섬 $\mathrm{A}$, $\mathrm{B}$중 어느 하나와 다리로 연결되면 되므로 이때의 방법의 수는 $( _{2} \mathrm{C} _{1} ) ^{3} = 8$ ⅰ), ⅱ), ⅲ)에서 구하는 방법의 수는 $18 + 24 + 8 = 50$ [다른 풀이] 섬 $\mathrm{A}$, $\mathrm{B}$를 연결하는 다리를 포함시켰을 때, 건설 가능한 다리의 총 개수는 ${}_{5} \mathrm{C} _{2} = 10$개다. 섬 $\mathrm{A}$, $\mathrm{B}$를 연결하는 다리가 존재하므로 건설 할 $3$개의 다리를 임의로 선택하는 방법의 수는 ${}_{9} {\mathrm{C}} _{3} = 84$이다. 이 중 $5$개의 섬이 모두 다리로 연결되지 않는 경우는 그림과 같이 다리로 다른 섬과 연결되지 않는 섬이 있는 경우 또는 두 섬과 세 섬으로 분리된 형태의 경우이다.

ⅰ) 다리로 다른 섬과 연결되지 않은 섬은 섬 $\mathrm{A}$, $\mathrm{B}$, $\mathrm{C}$ 중 많아야 한 개다. 이 섬을 선택하는 방법의 수는 ${}_{3} \mathrm{C} _{1}$$= 3$이다. 남은 네 섬을 다리로 연결하는 방법의 수는 ${}_{5} \mathrm{C} _{3} = 10$이다. 따라서 이때의 방법의 수는 $3 \times 10 = 30$이다. ⅱ) 두 섬과 세 섬으로 분리된 형태의 경우는 떨어진 두 섬이 $\mathrm{AB}$, $\mathrm{CD}$, $\mathrm{DE}$, $\mathrm{EC}$인 경우이다. 따라서 이때의 방법의 수는 $4$이다. ⅰ), ⅱ)에서 구하는 방법의 수는 $84 - ( 30 + 4 ) = 50$이다.