有六个城市，任两个城市间可铺路也可不铺路，要使得六城市两两联通，有几种铺路法？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

王守恩

2个城市铺路的方法是1种；
3个城市铺路的方法是4种；
4个城市铺路的方法是38种；
5个城市铺路的方法是738种；
6个城市铺路的方法是26999种；
7个城市铺路的方法是1874488种；
8个城市铺路的方法是251816342种；
9个城市铺路的方法是66307967418种；
............
蔡老弟！还能找出规律来吗？

luyuanhong

谢谢楼上 王守恩 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。

王守恩

王守恩 发表于 2017-5-13 13:48
2个城市铺路的方法是1种；
3个城市铺路的方法是4种；
4个城市铺路的方法是38种；

1=2^1 - (1) - 2×[2^0 - (1)]
4=2^3 - (1+3) - 3×[2^1 - (1+1)]
38=2^6 - (1+6+15) - 4×[2^3 - (1+3+3)]
738=2^10 - (1+10+45+120) - 5×[2^6 - (1+6+15+20)
26999=2^15 - (1+15+105+455+1365) - 6×[2^10 - (1+10+45+120+210)]
1874488=2^21 - (1+21+210+1330+5985+20349) - 7×[2^15 - (1+15+105+455+1365+3003)]
251816342=2^28 - (1+28+378+3276+20475+98280+376740) - 8×[2^21 - (1+21+210+1330+5985+20349+54264)]
66307967418=2^36 - (1+36+630+7140+58905+376992+1947792+8347680) - 9×[2^28 - (1+28+378+3276+20475+98280+376740+1184040)]
...............


陆老师！可以化简吗？

luyuanhong

谢谢楼上 王守恩 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。

王守恩

说得不好，请大家补充。
1，6个城市至少要有5条路。
2，6个城市最多有15条路。
3，把5——15条路的各种可能都罗列出来。
4，共铺15条路，则每个城市都有5条路，共铺15条路的各种可能都是答案。
5，共铺14条路，则某个城市只有4条路，共铺14条路的各种可能都是答案。
6，共铺13条路，则某个城市可能只有3条路，共铺13条路的各种可能都是答案。
7，共铺12条路，则某个城市可能只有2条路，共铺12条路的各种可能都是答案。
8，共铺11条路，则某个城市可能只有1条路，共铺11条路的各种可能都是答案。
9，共铺10条路，某个城市可能没有路可走，共铺10条路的各种可能，要减去这些可能。
10，共铺9条路，会出现没有路可走的可能，共铺9条路的各种可能中，要减去这些可能。
11，共铺8条路，会出现没有路可走的可能，共铺8条路的各种可能中，要减去这些可能。
12，共铺7条路，会出现没有路可走的可能，共铺7条路的各种可能中，有减去这些可能。
13，共铺6条路，会出现没有路可走的可能，共铺6条路的各种可能中，要减去这些可能。
14，共铺5条路，会出现没有路可走的可能，共铺5条路的各种可能中，要减去这些可能。

luyuanhong

王守恩

luyuanhong 发表于 2017-9-22 23:56

大家看看，哪里错了？
5个城市间铺1条路，可两两联通的铺路法有0种。
5个城市间铺2条路，可两两联通的铺路法有0种。
5个城市间铺3条路，可两两联通的铺路法有0种。
5个城市间铺4条路，可两两联通的铺路法有125种。
5个城市间铺5条路，可两两联通的铺路法有222种。
5个城市间铺6条路，可两两联通的铺路法有205种。
5个城市间铺7条路，可两两联通的铺路法有120种。
5个城市间铺8条路，可两两联通的铺路法有45种。
5个城市间铺9条路，可两两联通的铺路法有10种。
5个城市间铺10条路，可两两联通的铺路法有1种。
                      合计728种。

王守恩

      1=2^0
      1=2^1 - 1×1×1
      4=2^3 - 1×1×2 - 2× 1 × 1
    38=2^6 - 1×4×3 - 2× 1 × 3 -  8× 1×1
  728=2^10-1×38×4 -2× 4 × 6 -  8× 1×4-64×1×1
a(6)=2^15-1×728×5-2×38×10 - 8× 4×10-64×1×5-1024×1×1
a(7)=2^21-1×a(6)×6-2×728×15-8×38×20-64×4×15-1024×1×6-2^15×1×1
a(8)=2^28-1×a(7)×7-2×a(6)×21-8×728×35-64×38×35-1024×4×21-2^15×1×7-2^21×1×1
a(9)=2^36-1×a(8)×8-2×a(7)×28-8×a(6)×56-64×728×70-1024×38×56-2^15×4×28-2^21×1×8-2^28×1×1

luyuanhong

谢谢楼上 王守恩 的解答。我已将帖子转贴到“陆老师的《数学中国》园地”。