设为首页收藏本站

数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 528|回复: 17

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

[复制链接]
发表于 2017-5-9 07:44 | 显示全部楼层 |阅读模式
这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子,

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


20175811135575214.jpg
发表于 2017-5-10 09:54 | 显示全部楼层
2个城市铺路的方法是1种;
3个城市铺路的方法是4种;
4个城市铺路的方法是38种;
5个城市铺路的方法是738种;
6个城市铺路的方法是26999种;
7个城市铺路的方法是1874488种;
8个城市铺路的方法是251816342种;
9个城市铺路的方法是66307967418种;
............
蔡老弟!还能找出规律来吗?
 楼主| 发表于 2017-5-13 11:13 | 显示全部楼层
谢谢楼上 王守恩 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。
发表于 2017-5-16 11:23 | 显示全部楼层
王守恩 发表于 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)]
...............


陆老师!可以化简吗?
 楼主| 发表于 2017-5-16 11:48 | 显示全部楼层
谢谢楼上 王守恩 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。
发表于 2017-5-16 11:54 | 显示全部楼层
本帖最后由 蔡家雄 于 2017-5-16 16:35 编辑
王守恩 发表于 2017-5-16 11:23
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 ...


你也不信,我今天才第一次看此题!

你的每个答案都是一连串的三角形数 k(k+1)/2,
即有   通解公式,   
应该可以简化吧!不过我没空闲来简化了。


而有的数是组合数(即:二项式系数)


王师兄果然是组合数高手!

点评

检查一下,有错!至少9个城市要对上号。  发表于 2017-5-16 19:05
发表于 2017-5-16 17:01 | 显示全部楼层
王守恩 发表于 2017-5-16 11:23
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 ...

100个城市呢?用软件吧。
注意:
当n=2k+1为奇数时,组合数公式
[2^(2k+1)-[C(2k+1,k)]*2]/2与2^(2k)
当n=2k为偶数时,组合数公式
[2^(2k)-C(2k,k)]/2与[2^(2k)-C(2k,k)]/2+C(2k,k)


Binomial[        ]
发表于 2017-5-23 18:49 | 显示全部楼层
说得不好,请大家补充。
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条路的各种可能中,要减去这些可能。
 楼主| 发表于 2017-9-22 23:56 | 显示全部楼层
本帖最后由 luyuanhong 于 2017-10-11 15:05 编辑

有六个城市,任两个城市间可铺路也可不铺路,要使得六城市两两联通,有几种铺路法?.GIF

有六个城市,任两个城市间可铺路也可不铺路,要使得六城市两两联通,有几种铺路法?.rar (19.24 KB, 下载次数: 4)

点评

谢谢陆老师!我把我错的地方找出来!进步会很大的!  发表于 2017-9-23 05:17
发表于 2017-9-24 20:43 | 显示全部楼层
本帖最后由 王守恩 于 2017-9-27 20:26 编辑


大家看看,哪里错了?
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种。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|Archiver|数学中国 ( 京ICP备05040119号 )  

GMT+8, 2017-12-13 15:03 , Processed in 0.442606 second(s), 26 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表