106興大附中記憶版

15.
設ABCDEF為相異的六個新城市，現要開闢新的道路連接這六個城市，規定任兩城市間均可選擇恰鋪一條路或者不鋪路。若兩城市之間可以經由所鋪設之道路，從其中一城市到達另一城市，我們就稱兩城市連通。要使得這六個城市兩兩之間均連通，求鋪路的方法數為　　　。
[解答]
找不到遞迴，只好慢慢算
把所有的方法-不連通的情形
n=1   (1)
n=2   (1,1)
n=3   (1,1,1)(2,1)
n=4   (1,1,1,1)(2,1,1)(3,1)(2,2)
n=5   (1,1,1,1,1)(2,1,1,1)(3,1,1)(4,1)(3,2)(2,2,1)
n=6   (1,1,1,1,1,1)(2,1,1,1,1)(3,1,1,1)(4,1,1)(5,1)(4,2)(3,3)(3,2,1)(2,2,2)(2,2,1,1)
每個數字代表互相連通城市的數量
則