圓上有P1,P2,....,P20,利用這20個點畫10條弦,任兩條弦都不相教交,而且每個點都用到,
如果說這樣的畫法是此圓的"拼圖",問共有幾種"拼圖"?
piny 寫到:先定義一些狀況,若某兩點相連後其左右兩塊圓皆還有點存在,則稱為貫穿。
則可輕易看出一個符合題意的貫穿,左右兩邊剩餘點數必同為偶數,而不相鄰的貫穿,其間必為四的倍數。
再假設P1至P20依序於一圓上,
(a,b)表左右兩邊的剩餘點個數,
(Pa,Pb)表此兩點連為一線
分以下幾種情況:
1.無貫穿→兩種。
2.一條貫穿:則左右兩邊可為(2,16)(4,14)(6,12)(8,10)四種,
每一種皆有二十種變化,以(2,16)為例
即(P1,P18)、(P2,P19)、...
(P19,P16)、(P20,P17)
故為80種。
3.二條貫穿:則左右兩邊可為(2,14)(4,12)(6,10)(8,8)四種,
除了(8,8)為對稱只有十種變化外,餘皆二十種
故為70種。
4.三條貫穿至八條貫穿:很明顯地,依序為60至10種。
(以下皆只敘明有幾種,討論方法皆相同)
5.兩組貫穿,中間有四點,其組數可為
(1,1)→50種
(1,2)→40種
(1,3)→30種
(1,4)→20種
(1,5)→10種
(2,2)→30種
(2,3)→20種
(2,4)→10種
(3,3)→10種
6.兩組貫穿,中間有八點,其組數可為
(1,1)→30種
(1,2)→20種
(1,3)→10種
(2,2)→10種
7.兩組貫穿,中間有十二點,其組數可為
(1,1)→10種
8.三組貫穿,中間有四點、四點,其組數可為
(1,1,1)→20種
(1,1,2)→10種
(1,2,1)→10種
共702種
qeypour 寫到:圓上有P1,P2,....,P20,利用這20個點畫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