請各位數學高手幫忙解決一題數學排水問題~~~

Question

題目是這樣的
a-----b
l l
l l
~~~~~~~~~~~~~~~
有a、b兩個家庭要從水管排放廢水
首先~~~~~是一條河
--- 和 l 是水管
l
然後---水管只能排放一邊
而且a、b只能選其中一條排放
不能兩條都排
所以總共有三種排法
a---→b
l l
l ↓
~~~~~~~~~~~~~~~
a←---b
l l
↓ l
~~~~~~~~~~~~~~~
a-----b
l l
↓ ↓
~~~~~~~~~~~~~~~
但是不能這樣
a←---b
l l
↓ ↓
~~~~~~~~~~~~~~~
因為這樣b就變成兩條都排水
但他只能選一條
以此類推
如果是
a-----b-----c
l l l
l l l
~~~~~~~~~~~~~~~~~~~
那就有8條
你們可以先自己算算看是不是8條
如果是的話
那就代表搞懂我的題目了
最後我要問的是
S(2)=3個方法 (a、b兩家庭)
S(3)=8個方法 (a、b、c三家庭)
那以此類推
S(n)=???
答案要以n表示
如果可以的話
請盡量用高中程度的數學來寫
如果不能的話
再以大學的數學來寫
希望各位數學神人幫幫我一下
圖畫不好請見諒~~~

不是用聯立啦
不知道你為什麼會這樣想

a、b、c三個家庭都有水有排放到河裡
好吧
我補充一下
a-----b-----c
l l l
l l l
~~~~~~~~~~~~~~~~~~~

八種方法

1.
a---←b---←c
l l l
↓ l l
~~~~~~~~~~~~~~~~~~~

2.
a→---b---←c
l l l
l ↓ l
~~~~~~~~~~~~~~~~~~~

3.
a→---b---→c
l l l
l l ↓
~~~~~~~~~~~~~~~~~~~

4.
a→---b------c
l l l
l ↓ ↓
~~~~~~~~~~~~~~~~~~~

5.
a-----b→---c
l l l
↓ l ↓
~~~~~~~~~~~~~~~~~~~

6.
a---←b-----c
l l l
↓ l ↓
~~~~~~~~~~~~~~~~~~~

7.
a-----b---←c
l l l
↓ ↓ l
~~~~~~~~~~~~~~~~~~~

8.
a-----b-----c
l l l
↓ ↓ ↓
~~~~~~~~~~~~~~~~~~~

這樣總共有八種排水方法
不知道這樣夠不夠清楚了~~~

sorry
直的水管箭頭移位
你們應該看得懂~~~

n*n -1是如何得出來的
該不會只有綜合
S(2)=3
S(3)=8
來算出來吧
不過就如小路 ( 大師 4 級 )說的
S(4)就錯了~~~

就S(3)來說
他這題麻煩點在於第五和第六個方法
因為b可向左或向右
所以有兩種排法
因此也不能用排列組合
來分成1.選一條 2.選兩條 3.選三條
因為在選兩條時
b有向左向右所以算兩次~~~

Answer 1

耶?
N=5我怎麼算到53種?

2007-08-08 16:27:38 補充：
S(1)=1
S(2)=3
S(3)=8
S(4)=21
S(5)=55.........

之前數錯了, 不好意思.

S(n) = 2 * S(n-1) + S(n-2) + S(n-3)+ ...+ S(1) +1

解:

當在原本的S(n-1)排列組合中加上第 n 個新家庭 Xn時有三種排水法:

1. Xn直接排水給X(n-1)，共S(n-1)種排法.

2. Xn直接排水入河流，但並不接受X(n-1)及以左家庭排水過來，共S(n-1)種排法.

3. Xn排水入河流，並接受X(n-1)及以左家庭排水過來，這時要分開算：
　a. 只接受X(n-1)但不接受X(n-2)及以左家庭，共S(n-2)種排水法。
　b. 接受X(n-1)X(n-2)但不接受X(n-3)及以左家庭，共S(n-3)種排水法
　.......以此類推~

4. 最後的1就是全部家庭都透過Xn排水入河流

呼~

比較喜歡用 ∑ 可是還不太會用這個界面...





2007-08-08 16:34:53 補充：
我列一下S(4)=21的組合好了.
我以排入河的家庭來算:

四家庭排入河: ABCD -> 1種

三家庭排入河0: ABC, BCD -->各1種, 共2種
三家庭排入河1: ABD, ACD --> 各2種, 共4種

二家庭排入河0: AB, BC, CD -->各1種, 共3種
二家庭排入河1: AC, BD -->各2種, 共4種
二家庭排入河2: AD -->3種

一家庭排入河: A, B, C, D -->各1種, 共4種

1+2+4+3+4+3+4=21

Answer 2

我 N= 4也算 20耶

另外，N=5算46種方法~~

Answer 3

我肯定 n^2 － 1 是不對的.

因為 n ＝ 4 時, 我已經得到 20 種排水的方法了.

Answer 4

水管問題：是8種沒錯
1. a給b--> b排水 c排水
2. a給b給c -->c排水
3. b給a --> a排水 c排水
4. b給c --> a排水 c排水
5. c給b --> a排水 b排水
6. c給b給a --> a排水
7. a c皆給b --> b排水
8. abc 皆不給 --> abc排水

S(n) = n*n -1 (即 n 的平方減 1 )
可把數字帶進去驗證即可

Answer 5

我覺得需要用扣的....

2007-08-06 02:49:23 補充：
我的算法很難耶~~而且感覺沒有定律>"<
反正從第二項(三個家)推論是要用扣的~~

Answer 6

我看你用ㄅ全再做一次會比較清楚