在 6 座岛屿之间建造 5 座桥，使它们能够联通，请问有几种建桥方案？

王守恩

dlpg070 发表于 2019-12-2 09:06
回复王守恩 27#
您发了2#，5#，7#，26#，27#大量数据，不怀疑其正确性，但多数不能完全理解
直到看见27 ...

例如：6×1296+15×432+20×108+15×24+6×5+1×1=16807
出现 “1” 有6种可能，其中：
出现1个 “1”：6×1296=12，13，14，15，16，17 各出现1296次。
出现2个 “1”：15×432=12,13，12,14，12,15，12,16，12,17，13,14，13,15，...，15,16，15,17，16,17 各出现432次，
出现3个 “1”：20×108=12,13,14，12,13,15，12,13,16，12,13,17，12,14,15，...，14,15,17，14,16,17，15,16,17各出现108次，
出现4个 “1”：15×24=12,13,14,15，12,13,14,16，12,13,14,17，12,13,15,16，...，13,14,16,17，13,15,16,17，14,15,16,17各出现24次，
出现5个 “1”：6×5=12,13,14,15,16，12,13,14,15,17，12,13,14,16,17，12,13,15,16,17，12,14,15,16,17，13,14,15,16,17 各出现5次，
出现6个 “1”：1×1=12,13,14,15,16,17出现1次。





补充内容 (2019-12-3 07:26):
1296=1×6^4，432=2×6^3，108=3×6^2，24=4×6^1，5=5×6^0，1=6×6^(-1)

dlpg070

王守恩 发表于 2019-12-2 12:45
例如：6×1296+15×432+20×108+15×24+6×5+1×1=16807
出现 “1” 有6种可能，其中：
出现1个 “1 ...

根据王守恩27#数据，归纳出如下2个公式
1 通项公式
2 递推公式
给出代码和模拟27#结果

-------------

1. Clear["Global`*"];
   
2. time1 = AbsoluteTime[];
   
3. t[n_, k_] := (n - k)*n^(k - 1);
   
4. (*
   
5. A058127=Table[t[n,k],{n,1,10},{k,0,n-1}]//Flatten; (*Jean-Fran?ois \
   
6. Alcover,Dec 03 2013*)
   
7. A058127a=Table[{"n=",n," k=",k," ",t[n,k],"\n"},{n,1,10},{k,0,n-1}]
   
8. Print["A058127 ",A058127]
   
9. *)
   
10. sol = Table[t[n, n - 1], {n, 2, 12}];
    
11. time2 = AbsoluteTime[];
    
12. Print["通项耗时 ", time2 - time1, " 秒"]
    
13. 
    
14. Print["通项 输出 ", sol]
    
15. time1 = AbsoluteTime[];
    
16. a[2] = 1;
    
17. a[n_] := a[n] =
    
18.    Module[{sum = 0},  
    
19.     sum = (n - 1)*a[n - 1] +
    
20.       Sum[Binomial[n - 1, i]*t[n - 1, n - i - 1], {i, 2, n - 1}];
    
21.     sum];
    
22. sol1 = Table[a[n], {n, 2, 12}];
    
23. time2 = AbsoluteTime[];
    
24. Print["递推耗时 ", time2 - time1, " 秒"]
    
25. Print["递推 输出 ", sol]
    
26. 
    
27. Print["模拟王守恩27#: "]
    
28. time1 = AbsoluteTime[];
    
29. Do[(* n *)
    
30. str = ToString[Binomial[n - 1, 1]] <> "x" <>
    
31.    ToString[t[n - 1, n - 1 - 1]];
    
32. Do[(*i *)
    
33.   str = str <> "+" <> ToString[Binomial[n - 1, i]] <> "x" <>
    
34.     ToString[t[n - 1, n - i - 1]], {i, 2, n - 1}];
    
35. str = str <> "=" <> ToString[a[n]];
    
36. Print[str];
    
37. Print["  " <> ToString[n] <> " 岛 " <> ToString[n - 1] <> " 桥有" <>
    
38.    ToString[a[n]] <> "种建桥方案"];
    
39. 
    
40. Print[" "],
    
41. {n, 2, 12}]
    
42. time2 = AbsoluteTime[];
    
43. Print["模拟耗时 ", time2 - time1, " 秒"]
    
44. Print["--- end ---"]

复制代码

计算结果：

通项耗时 0.0010001 秒
通项 输出 {1,3,16,125,1296,16807,262144,4782969,100000000,2357947691,61917364224}
递推耗时 0.0030002 秒
递推 输出 {1,3,16,125,1296,16807,262144,4782969,100000000,2357947691,61917364224}
模拟王守恩27#:
1x1=1
  2 岛 1 桥有1种建桥方案

2x1+1x1=3
  3 岛 2 桥有3种建桥方案

3x3+3x2+1x1=16
  4 岛 3 桥有16种建桥方案

4x16+6x8+4x3+1x1=125
  5 岛 4 桥有125种建桥方案

5x125+10x50+10x15+5x4+1x1=1296
  6 岛 5 桥有1296种建桥方案

6x1296+15x432+20x108+15x24+6x5+1x1=16807
  7 岛 6 桥有16807种建桥方案

7x16807+21x4802+35x1029+35x196+21x35+7x6+1x1=262144
  8 岛 7 桥有262144种建桥方案

8x262144+28x65536+56x12288+70x2048+56x320+28x48+8x7+1x1=4782969
  9 岛 8 桥有4782969种建桥方案

9x4782969+36x1062882+84x177147+126x26244+126x3645+84x486+36x63+9x8+1x1=100000000
  10 岛 9 桥有100000000种建桥方案

10x100000000+45x20000000+120x3000000+210x400000+252x50000+210x6000+120x700+45x80+10x9+1x1=2357947691
  11 岛 10 桥有2357947691种建桥方案

11x2357947691+55x428717762+165x58461513+330x7086244+462x805255+462x87846+330x9317+165x968+55x99+11x10+1x1=61917364224
  12 岛 11 桥有61917364224种建桥方案

模拟耗时 0.0030002 秒
--- end ---

markfang2050

dlpg070 发表于 2019-12-2 21:07
根据王守恩27#数据，归纳出如下2个公式
1 通项公式
2 递推公式

不要干这个事，首先得证明这个通项的正确性，不要把结果凑成公式。

kastin

Cayley公式：`n`个节点的带标号的无根树有`n^(n-2)`个，所以结果就是 `6^4=1296`.
相关资料：https://www.cnblogs.com/Jackpei/p/10827653.html