=======================华丽的分割线============================
8座岛屿之间建造7座桥，使它们能够联通，共有262144种建桥方案。
--------------------------------------------------------------------------------
python3.6程序运行 21.166463375091553 秒。
--------------------------------------------------------------------------------
>>>
northwolves 发表于 2019-11-18 23:54
$a_n=n^(n-2)$?怎么证明？
Cayley凯莱定理
markfang2050 发表于 2019-11-28 22:57
Cayley凯莱定理
受markfang2050鼓舞，
剔除的方法，在岛数较少时，还是可以接受的,
庆幸今天偶然机会，对特别丑的代码做了些整容,丑得有些可爱
例如:
6岛5桥全联通建桥方案数= 1296
耗时 0.4520259 不显示方案 / 0.4830276 显示方案
速度尚可
isok函数还需要优化，7岛6桥 8岛7桥时特别慢!!!
贴出代码，请指正
Clear["Global`*"];
(*判断 line 是否全联通，ok 待优化 ，改进 True/False
各岛建桥情况： arr[] 1:联通 2:未联通，有另外1组 0:无桥 *)
isok:=isok=Module[{ret=True,x=0,y=0,
arr=Array+1}]},
x=line[];
y=line[];
arr[]=1;
arr[]=1;
Table[
Table[
x=line[];
y=line[];
If[(arr[]==1) || (arr[]==1),arr[]=1;
arr[]=1](*;
Print["i=",i," j=",j," arr=",arr]*),
{j,1,Length}],
{i,1,Length}];
x=Sum],{i,1,Length+1}];
If[ x !=(Length+1),ret=False];
ret(*{x,arr}*)];(* end *)
time1=AbsoluteTime[];(*计算时间开始*)
nn=6;
resline={};
tup2=With[{n=nn,m=2},Subsets,{m}]];
Print["tup2 长度= ",Length," ",tup2]
tup2line=With[{n=Length,m=nn-1},Subsets];
Print["tup2line 长度= ",Length]
Do[(*i *)line=tup2line[];
If==True,AppendTo]
,{i,1,Length}]
resline;(*如果去掉分号则显示各个建桥方案*)
Print["=== ==="]
time2=AbsoluteTime[];
Print<>"岛"<>ToString<>"桥全联通建桥方案数=
"<>ToString]]
Print["耗时 ",time2-time1]
输出:
tup2 长度= 15 {{1,2},{1,3},{1,4},{1,5},{1,6},{2,3},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6},{4,5},{4,6},{5,6}}
tup2line 长度= 3003
=== ===
6岛5桥全联通建桥方案数= 1296
耗时 0.4470256
dlpg070 发表于 2019-11-29 20:30
受markfang2050鼓舞，
剔除的方法，在岛数较少时，还是可以接受的,
庆幸今天偶然机会，对特别丑的代码 ...
如何用简单的语言，把题目与乘法原理扯上号？
又：这答案可以用多项式系数来解读吗？
本帖最后由 dlpg070 于 2019-11-30 08:45 编辑
dlpg070 发表于 2019-11-29 20:30
受markfang2050鼓舞，
剔除的方法，在岛数较少时，还是可以接受的,
庆幸今天偶然机会，对特别丑的代码 ...
画图部分只是一个自制简易视觉调试工具，
解题完毕，则其任务就结束了
应要求把画图部分附上，没什么特色，倒挺好玩的(集中在代码尾部，测试通过)
Clear["Global`*"];
(*判断 line 是否全联通，ok 待优化 ，改进 True/False 各岛建桥情况： arr[] 1:联通 2:未联通，有另外1组 0:无桥 *)
isok:=isok=Module[{ret=True,x=0,y=0, arr=Array+1}]},
x=line[];
y=line[];
arr[]=1;
arr[]=1;
Table[
Table[
x=line[];
y=line[];
If[(arr[]==1) || (arr[]==1),arr[]=1;
arr[]=1](*;
Print["i=",i," j=",j," arr=",arr]*),
{j,1,Length}],
{i,1,Length}];
x=Sum],{i,1,Length+1}];
If[ x !=(Length+1),ret=False];
ret(*{x,arr}*)];(* end *)
time1=AbsoluteTime[];(*#计算时间开始*)
nn=6;(* 岛数 *)
resline={};
tup2=With[{n=nn,m=2},Subsets,{m}]];
Print["tup2 长度= ",Length," ",tup2]
tup2line=With[{n=Length,m=nn-1},Subsets];
Print["tup2line 长度= ",Length]
Do[(*i *)line=tup2line[];
If==True,AppendTo]
,{i,1,Length}]
Grid]},{j,1,Length}]];
(*如果去掉分号则格式化显示各个建桥方案*)
Print["=== ==="]
time2=AbsoluteTime[];
Print<>"岛"<>ToString<>"桥全联通建桥方案数= "<>ToString]]
(* 绘图用 简单的视觉调试工具*)
pts=Table[{Sin,Cos},{i,0,nn-1}];
(*点序号变坐标 岛桥专用,已修改 *)
fm:=Module[{i=n,lst={},x=0,y=0},
x=line[];
y=line[];
AppendTo],pts[]}];
lst
];
(*画一张图*)
gra:=Graphics[{Opacity,Green,Circle[{0,0},1.0],Table[{Red,Disk],0.1],
Opacity,Black,Text,Bold,FontSize->10],pts[]]},{i,1,nn}],
Black,Arrow[#]&/@lines,Disk[{0,0},0.05]},Axes->False,PlotRange->{-1.1,1.1},
PlotLabel->Style<>""],10,Blue,Background->Yellow],ImageSize->100]
listgra={};(*图形列表*)
lines={};(*连线坐标*)
For,i++,
lines={};
m=resline[];
Do],{j,1,Length}];
AppendTo]
];
out=Table[
listgra[],
{i,1,Min]}](* ;-不显示图形 ，50是任意选择值 *)
(*为了在图形太多时，选取显示少量 （50）样本*)
Export<>"岛"<>ToString<>"桥.png",out];
Print["测试 Import:"]
Import<>"岛"<>ToString<>"桥.png"]
Print["耗时 ",time2-time1]
Print["--- rnd ---"]
王守恩 发表于 2019-11-24 21:46
在六座岛屿之间建造五座桥，使它们能够联通，请问有几种建桥方案？
1，给 6 个岛编上号：1，2，3，4 ...
接 7 楼。
1×1=1
1×2(个岛)÷2(个数字1座桥)=1，可以有 1 种建桥方案。
2×1+1×2×1=4
4×3(个岛)÷4(个数字2座桥)=3，可以有 3 种建桥方案。
3×1+2×3×2+1×3×3=24
24×4(个岛)÷6(个数字3座桥)=16，可以有 16 种建桥方案。
4×1+3×4×3+2×6×8+1×4×16=200
200×5(个岛)÷8(个数字4座桥)=125，可以有 125 种建桥方案。
5×1+4×5×4+3×10×15+2×10×50+1×5×125=2160
2160×6(个岛)÷10(个数字5座桥)=1296，可以有 1296 种建桥方案。
6×1+5×6×5+4×15×24+3×20×108+2×15×432+1×6×1296=28812
28812×7(个岛)÷12(个数字6座桥)=16807，可以有 16807 种建桥方案。
7×1+6×7×6+5×21×35+4×35×196+3×35×1029+2×21×4802+1×7×16807=458752
458752×8(个岛)÷14(个数字7座桥)=262144，可以有 262144 种建桥方案。
8×1+7×8×7+6×28×48+5×56×320+4×70×2048+3×56×12288+2×28×65536+1×8×262144=8503056
8503050×9(个岛)÷16(个数字8座桥)=4782969，可以有 4782969 种建桥方案。
9×1+8×9×8+7×36×63+6×84×486+5×126×3645+4×126×26244+3×84×177147+2×36×1062882+1×9×4782969=180000000
180000000×10(个岛)÷18(个数字9座桥)=100000000，可以有 100000000 种建桥方案。
................
看着这些美妙的数字，您不想试一试？！
本帖最后由 王守恩 于 2019-11-30 17:48 编辑
王守恩 发表于 2019-11-30 15:15
接 14 楼。
1×1=1
接 26 楼。
1×1=1
2 岛 1 桥有 1 种建桥方案。
2×1+1×1=3
3 岛 2 桥有 3 种建桥方案。
3×3+3×2+1×1=16
4 岛 3 桥有 16 种建桥方案。
4×16+6×8+4×3+1×1=125
5 岛 4 桥有 125 种建桥方案。
5×125+10×50+10×15+5×4+1×1=1296
6 岛 5 桥有 1296 种建桥方案。
6×1296+15×432+20×108+15×24+6×5+1×1=16807
7 岛 6 桥有 16807 种建桥方案。
7×16807+21×4802+35×1029+35×196+21×35+7×6+1×1=262144
8 岛 7 桥有 262144 种建桥方案。
8×262144+28×65536+56×12288+70×2048+56×320+28×48+8×7+1×1=4782969
9 岛 8 桥有 4782969 种建桥方案。
9×4782969+36×1062882+84×177147+126×26244+126×3645+84×486+36×63+9×8+1×1=100000000
10 岛 9 桥有 100000000 种建桥方案。
...........
9×4782969+36×1062882+84×177147+126×26244+126×3645+84×486+36×63+9×8+1×1=100000000
表示 ：1个“1” + 2个“1” + 3个“1” + 4个“1” + 5个“1” + 6个“1” + 7个“1” + 8个“1” + 9个“1” =100000000
王守恩 发表于 2019-11-30 17:28
接 26 楼。
1×1=1
求证：
\(\frac{8!*9^8}{0!*8!}+\frac{8!*9^7}{1!*7!}+\frac{8!*9^6}{2!*6!}+\frac{8!*9^5}{3!*5!}+\frac{8!*9^4}{4!*4!}+\frac{8!*9^3}{5!*3!}+\frac{8!*9^2}{6!*2!}+\frac{8!*9^1}{7!*1!}+\frac{8!*9^0}{8!*0!}=10^8\)
王守恩 发表于 2019-11-30 19:55
求证：
\(\frac{8!*9^8}{0!*8!}+\frac{8!*9^7}{1!*7!}+\frac{8!*9^6}{2!*6!}+\frac{8!*9^5}{3!*5!}+\f ...
谢谢lsr314！
在 6 座岛屿之间建造 5 座桥，使它们能够联通，请问有几种建桥方案？
答案可以用展开多项式系数思想来解读。
给 6 个岛编上号：1，2，3，4，5，6；
给15座桥编上号：12,13,14,15,16,23,24,25,26,34,35,36,45,46,56。
每种建桥方案就是在这15座桥中选择合适的5座桥(10个数字)，
在5座桥(10个数字)里，肯定会出现数字 “1”，
我们只要统计 “1” 出现的次数就可以了，
展开多项式 (5+x)^4
(5+x)^4=625 + 500 x + 150 x^2 + 20 x^3 + x^4
系数合计：625 + 500 + 150 + 20 + 1 =1296，可以有 1296 种建桥方案。
出现 “1” 有5种可能，其中：
出现1个 “1”：625次，
出现2个 “1”：500次，
出现3个 “1”：150次，
出现4个 “1”：20次，
出现5个 “1”：1次。
王守恩 发表于 2019-11-30 17:28
接 26 楼。
1×1=1
回复王守恩 27#
您发了2#，5#，7#，26#，27#大量数据，不怀疑其正确性，但多数不能完全理解
直到看见27# "这些美妙的数字",感到太奇妙了
这里隐含着独一无二的 通项的递推公式
希望能说明其中部分乘数的算法
例如:
6×1296+15×432+20×108+15×24+6×5+1×1=16807
--- --- -- -- --
7 岛 6 桥有 16807 种建桥方案。
即 432，108，24，5，1的计算方法
显然不是统计“1“吧
有了这些算法，递推公式就归纳出来了，
虽然特繁杂，但独特,好玩儿