The problem examines a given convex polygon of n sides -that is, a polygon of n sides that satisfies the property: For all point P1 P2 within the interior of the polygon, the line segment joining P1 and P1 also lies within the interior of the polygon.
Given a convex polygon of n sides, Euler wanted to count the number of ways the interior of the polygon could be triangulated(Subdivided) by drawing diagonals that do not intersect.
for a convex polygon of n >= 3 sides, let t(n) count the number of ways the interior of the polygon can be triangulated by drawing non intersecting diagonals.
a)Define t(2) = 1 and verify that t(n+1) = t(2)t(n)+t(3)t(n-1) + ....+t(n)t(2)
請問助教這一題的題意到底在問什麼??
我進不到題目裡面
謝謝助教
2 則留言:
這題是在問一個n+1個邊的多邊形可以切成多少種三角形,其中切的線段不能交叉
我的想法是這樣:
將這n+1個多邊形的頂點去編號1到n+1
以編號1為軸去切,因為要切成三角形,若第一條線連到3,分成兩個多邊形(123,345..n+1)
因為三角形123=>t(3)
另外多邊形34..n+1回到1,共n個邊=>t(n)
若連到4號則變成t(4),t(n-1)..依此類推
所以t(n+1)=t(3)t(n)+t(4)t(n-1)+..
但是跟題目求的差一點...@@
我想大概是這樣
剩下就麻煩助教 指點錯的地方...
原題在問的是欲將一個 n-gon 切成多個三角形的聯集, 總共會有幾種方式, pai回答的想法差不多了, 只是漏了一種可能: 假設先考慮一個底邊, 因為那個底邊可與它右邊和他相鄰的那個邊形成一三角形, 也可以和他左邊的邊形成一三角形, 而你的看法已經將那個底邊固定在那兩個三角形裡的其中一個了, 所以才會少考慮
這題事實上有出現在課本chap5的習題裡(5-73), 對一個 n+2 polygon 分割成三角形聯集的方法數就是 C_n
張貼留言