YLL討論網

圓上有P1,P2,....,P20,利用這20個點畫10條弦,任兩條弦都不相教交,而且每個點都用到,
如果說這樣的畫法是此圓的"拼圖",問共有幾種"拼圖"?

10種?
我猜想畫法只有一種樣式,就是十條平行線(平行線這個說法不符合數學上的定義,不過這樣說比較方便啦! ),每一點有十種畫法,所以猜是十種

安靜be-quiet 寫到:10種?
我猜想畫法只有一種樣式,就是十條平行線(平行線這個說法不符合數學上的定義,不過這樣說比較方便啦! ),每一點有十種畫法,所以猜是十種

不一定要平行,像P1P2,P3P4,P5P6,....,P19P20,這10條弦畫出也是一種拼圖

先定義一些狀況，若某兩點相連後其左右兩塊圓皆還有點存在，則稱為貫穿。
則可輕易看出一個符合題意的貫穿，左右兩邊剩餘點數必同為偶數，而不相鄰的貫穿，其間必為四的倍數。
再假設Ｐ１至Ｐ２０依序於一圓上，
（ａ，ｂ）表左右兩邊的剩餘點個數，
（Ｐａ，Ｐｂ）表此兩點連為一線

分以下幾種情況：
１．無貫穿→兩種。
２．一條貫穿：則左右兩邊可為（２，１６）（４，１４）（６，１２）（８，１０）四種，
　　　　每一種皆有二十種變化，以（２，１６）為例
　　　　即（Ｐ１，Ｐ１８）、（Ｐ２，Ｐ１９）、．．．
　　　　　（Ｐ１９，Ｐ１６）、（Ｐ２０，Ｐ１７）
　　　　故為８０種。
３．二條貫穿(相鄰)：則左右兩邊可為（２，１４）（４，１２）（６，１０）（８，８）四種，
　　　　除了（８，８）為對稱只有十種變化外，餘皆二十種
　　　　故為７０種。
４．三條貫穿至八條貫穿(皆相鄰)：很明顯地，依序為６０至１０種。
　　　　（以下皆只敘明有幾種，討論方法皆相同）
５．兩組貫穿，中間有四點，其組數可為
　　　　（１，１）→５０種
　　　　（１，２）→４０種
　　　　（１，３）→３０種
　　　　（１，４）→２０種
　　　　（１，５）→１０種
　　　　（２，２）→３０種
　　　　（２，３）→２０種
　　　　（２，４）→１０種
　　　　（３，３）→１０種
６．兩組貫穿，中間有八點，其組數可為
　　　　（１，１）→３０種
　　　　（１，２）→２０種
　　　　（１，３）→１０種
　　　　（２，２）→１０種
７．兩組貫穿，中間有十二點，其組數可為
　　　　（１，１）→１０種
８．三組貫穿，中間有四點、四點，其組數可為
　　　　（１，１，１）→２０種
　　　　（１，１，２）→１０種
　　　　（１，２，１）→１０種

共７０２種

piny 寫到:先定義一些狀況，若某兩點相連後其左右兩塊圓皆還有點存在，則稱為貫穿。
則可輕易看出一個符合題意的貫穿，左右兩邊剩餘點數必同為偶數，而不相鄰的貫穿，其間必為四的倍數。
再假設Ｐ１至Ｐ２０依序於一圓上，
（ａ，ｂ）表左右兩邊的剩餘點個數，
（Ｐａ，Ｐｂ）表此兩點連為一線

分以下幾種情況：
１．無貫穿→兩種。
２．一條貫穿：則左右兩邊可為（２，１６）（４，１４）（６，１２）（８，１０）四種，
　　　　每一種皆有二十種變化，以（２，１６）為例
　　　　即（Ｐ１，Ｐ１８）、（Ｐ２，Ｐ１９）、．．．
　　　　　（Ｐ１９，Ｐ１６）、（Ｐ２０，Ｐ１７）
　　　　故為８０種。
３．二條貫穿：則左右兩邊可為（２，１４）（４，１２）（６，１０）（８，８）四種，
　　　　除了（８，８）為對稱只有十種變化外，餘皆二十種
　　　　故為７０種。
４．三條貫穿至八條貫穿：很明顯地，依序為６０至１０種。
　　　　（以下皆只敘明有幾種，討論方法皆相同）
５．兩組貫穿，中間有四點，其組數可為
　　　　（１，１）→５０種
　　　　（１，２）→４０種
　　　　（１，３）→３０種
　　　　（１，４）→２０種
　　　　（１，５）→１０種
　　　　（２，２）→３０種
　　　　（２，３）→２０種
　　　　（２，４）→１０種
　　　　（３，３）→１０種
６．兩組貫穿，中間有八點，其組數可為
　　　　（１，１）→３０種
　　　　（１，２）→２０種
　　　　（１，３）→１０種
　　　　（２，２）→１０種
７．兩組貫穿，中間有十二點，其組數可為
　　　　（１，１）→１０種
８．三組貫穿，中間有四點、四點，其組數可為
　　　　（１，１，１）→２０種
　　　　（１，１，２）→１０種
　　　　（１，２，１）→１０種

共７０２種

可否以此方法算一下6點跟8點跟10點的拼圖各有幾個?

Anonymous 寫到:

可否以此方法算一下6點跟8點跟10點的拼圖各有幾個?

可以吧！方法相同，分別為五種、十四種、三十二種。

發現一些情況尚未考慮，就是兩組以上的貫穿有可能某一邊是相鄰的，此時間隔不一定得為四的倍數，這些情況都尚未考慮進去，所以答案將會更多！

明天有空再好好整理一次，先睡了！

piny 寫到:

Anonymous 寫到:

可否以此方法算一下6點跟8點跟10點的拼圖各有幾個?

可以吧！方法相同，分別為五種、十四種、三十二種。

我的答案五種,十四種,四十種
第三個不一樣

呵呵！大家的答案都再加碼...

我的答案再改為5種、14種、42種，

以下為10點的情況討論：

１．無貫穿：２種
２．一條貫穿：１５種
３．二條貫穿（相鄰）：１０種
４．三條貫穿（皆相鄰）：５種
５．兩組貫穿（某一頭相鄰、另一頭隔兩點）：１０種

至於原題目，發現還有好多情況得考慮，還在想有沒有較簡捷的算法．．．

忘了登入
其實原題我算15528種
只是不知對或不對?

一般解決圖形上的分割問題，我們會嘗試找出遞迴關係，再求解
假設圓內接2n邊形的拼圖數為F(n)
n=0，F(0)=1(這應該沒有意義，但為了配合公式，這是不得已的規定)
n=1，F(1)=1(理由同上)
n=2，F(2)=2
因為圓上兩點A、B能夠相連成一條弦，且滿足條件
其充要條件為此弦必須將其它點分割成左右兩側都是偶數個頂點
設AB線段左側頂點數為2s，AB線段右側頂點數為2n-2s-2=2(n-s-1)
所以原2n邊形分成一個2s邊形及一個2(n-s-1)邊形
而2s邊形的拼圖數為F(s)，2(n-s-1)邊形的拼圖數為F(n-s-1)
所以屬於此種類型的拼圖數為F(s)*F(n-s-1)
所以F(n)=F(0)*F(n-1)+F(1)*F(n-2)+....+F(n-1)F(0)
上式遞迴式的解為F(n)=[1/(n+1)]*C(2n,n)
(證明在此略)

所以，20邊形，n=10，F(10)=(1/11)*C(20,10)=16796

qeypour 寫到:圓上有P1,P2,....,P20,利用這20個點畫10條弦,任兩條弦都不相教交,而且每個點都用到,
如果說這樣的畫法是此圓的"拼圖",問共有幾種"拼圖"?

我以為是一次把10條弦畫完才算一種.....還是我誤解題目的意思啦

galaxylee 寫到:

一般解決圖形上的分割問題，我們會嘗試找出遞迴關係，再求解
假設圓內接2n邊形的拼圖數為F(n)
n=0，F(0)=1(這應該沒有意義，但為了配合公式，這是不得已的規定)
n=1，F(1)=1(理由同上)
n=2，F(2)=2
因為圓上兩點A、B能夠相連成一條弦，且滿足條件
其充要條件為此弦必須將其它點分割成左右兩側都是偶數個頂點
設AB線段左側頂點數為2s，AB線段右側頂點數為2n-2s-2=2(n-s-1)
所以原2n邊形分成一個2s邊形及一個2(n-s-1)邊形
而2s邊形的拼圖數為F(s)，2(n-s-1)邊形的拼圖數為F(n-s-1)
所以屬於此種類型的拼圖數為F(s)*F(n-s-1)
所以F(n)=F(0)*F(n-1)+F(1)*F(n-2)+....+F(n-1)F(0)上式遞迴式的解為F(n)=[1/(n+1)]*C(2n,n)
(證明在此略)
所以，20邊形，n=10，F(10)=(1/11)*C(20,10)=16796

其實我有找到紅色之遞迴式
但因沒找到棕色的一般解而造成加錯的情況
可請galxylee兄撥空post一下遞迴式得解之過程嗎?
感激不盡