Question

一道数学题的解答

Answer 1

我们考虑两种情况：
一、1对1或者2，就是一个村庄最多连接其他2个村庄
A-B-C-D，A-D-C-B，这样的，显然
A-B-C-D与D-C-B-A是同一种情况
这时就相当于A、B、C、D、的全排，但因为ABCD与DCBA是同一种情况，考虑倒序的情况，所以只是一半。
即，这时的方案有
A(4,4)/2=12种
二、1对3，就是由其中的一个村庄向其他的3个村庄修路，而其他的3个之间不直接连接
A-(B、C、D)
4个村庄都可以成为连接的中心，共C(4,1)=4种方案
所以，共有
12+4=16
种修筑方案。