作业帮关于平面凸多边形三角剖分数的问题
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/23 13:41:41
关于平面凸多边形三角剖分数的问题
由乌尔班的三角剖分数公式Dn+1/Dn=4*n-6/n推知六边形三角剖分数比五边形三角剖分数为：
D6/D5=4*5-6/5=14/5=28/10（即,28是六边形的三角剖分数,10是五边形的三角剖分数）
但是,我是用阶乘求组合的方式求六边形的三角剖分数却不是28,而是C3=6!/3!(6-3)!=4*5*6/1*2*3=20,即六边形的三角剖分数是20.
请问,用不同的方法计算,一个是28,一个是20,到底哪个对?错的那个问题出在哪里?请务必有详解过程地回答我!
由乌尔班的三角剖分数公式Dn+1/Dn=4*n-6/n推知六边形三角剖分数比五边形三角剖分数为：
D6/D5=4*5-6/5=14/5=28/10（即,28是六边形的三角剖分数,10是五边形的三角剖分数）
但是,我是用阶乘求组合的方式求六边形的三角剖分数却不是28,而是C3=6!/3!(6-3)!=4*5*6/1*2*3=20,即六边形的三角剖分数是20.
请问,用不同的方法计算,一个是28,一个是20,到底哪个对?错的那个问题出在哪里?请务必有详解过程地回答我!
以三角剖分的意义来说,两个都不对.
一般所指的三角剖分数D[n],是指将凸n边形分成n-2个三角形的方法数,
其中三角形的顶点必须是n边形的顶点.
n = 3,4,5,6时依次为1,2,5,14.
递推公式为D[n+1] = D[n]·(4n-6)/n.
也可用组合数表示为D[n] = C(2n-4,n-2)/(n-1).
凸多边形三角划分一节有n = 6的情形的图.
从你的组合解法和n = 5时得10的结果来说,
也许你想求的是以n边形的顶点为顶点的三角形的个数?
这个要简单许多,就是如你所说的C(n,3).
那么n = 5时得10,n = 6时得20都是正确的.
总之,上面是两个不同问题.
请先明确你所想求的"三角剖分数"具体是什么意义.
再问： 你的回答前后矛盾嘛~~~不赘述，哪里矛盾你自己看吧。
再答： 好吧, 我的意思是"一般意义的"三角剖分数应该是D[n]那个序列: 1, 2, 5, 14, 42, 132, 429,... 如果你想求的是"一般意义的"三角剖分数, 那么用D[n+1] = D[n]·(4n-6)/n或者D[n] = C(2n-4,n-2)/(n-1)可以得到正确的结果. 特别的D[6] = 14. 但是这个"一般意义"的三角剖分数不满足你所说的D[5] = 10, 而D[6]也不等于28或20, 所以我不知道你想求的是"何种意义的"三角剖分数? 需要麻烦你解释一下, 我再回答该种意义的三角剖分数应该怎样计算.
再问： 我所要知道的是：以平面凸多边形的顶点为三角形的三个顶点，所进行的三角剖分。其实我已经知道还是我用阶乘求组合的方式求得的结果对——当然，这么不谦虚地说话，是站在我所要的以多边形的顶点为三角形的三个顶点这一立场之上。但是，我还想知道的是：乌尔班的三角剖分公式为什么不能适用于我说的这种三角剖分？乌尔班三角剖分公式有其局限性吗？
再答： 重复一下我所说的"一般意义的"三角剖分的定义:将凸n边形分划为n-2个三角形, 其中三角形的顶点必须是n边形的顶点.
所以"以多边形的顶点为三角形的顶点"这一点并没有分歧,有分歧的还是更基本的问题: 什么是三角剖分? 这一点你还是没有解释清楚.
用语言解释不够清楚的话可以参见下图:
这是n = 4, 5, 6时, "一般意义"的全部三角剖分, 种数分别是2, 5, 14.
其中分划所得的每个三角形的顶点都是多边形的顶点, 且不难验证这些就是全部.这些数值很好的符合乌尔班公式.
如果你所要的三角剖分数在n = 5时为10, n = 6时为20,你能否指出有哪些情况不包含于上面所列?按我的揣度, 你所求的其实不是三角剖分数, 而是以n边形的顶点为顶点的三角形个数.n = 5时如下图:
这样一来, 就有10个了, C(n,3)也能说得通了.
但是这计数的不是三角剖分, 上面那排并没有将五边形划分成三角形.这样一来不能适用乌尔班公式也没有什么不正常.
当然, 这只是我对你本意的一种猜测, 究竟如何还是需要你来解释一下.
再问： 对啦，就是这个！您所说的三角剖分的方法数量与三角剖分的个数这两个，我都求证过了，与您的详解一致。但看了您的详解我才知道，乌尔班公式是求证三角剖分方法数量的（对吗？），而非三角剖分的个数——这正是我认为乌尔班公式与阶乘结果不一致的错误原因。最后再次请您不弃肤受赐教：乌尔班的三角剖分到底是怎样的？那些乌漆麻黑的百科词条我都看不懂~~~谢谢啦！
再答： 你理解的很对, 乌尔班公式求的就是三角剖分的方法数.下面给出一种乌尔班公式的推导方法,
虽然并不是很困难, 但是理解起来需要花点功夫.
记凸n边形的三角剖分方法数为D[n].思路很明确: 尝试将n边形的三角剖分方法与n+1边形的三角剖分方法建立某种对应关系.作为建立联系的基准, 对n边形和n+1边形都选择一条基准边 (图中的绿边).然后考虑如下两种互逆的操作:
(1) 对于n边形的一种三角剖分, 任选图形中的一条线段 (图中的黄线段),再选择该线段的一个端点 (图中的红点).将该点"膨胀"为一条边 (图中的红边), 同时线段"膨胀"为一个三角形 (图中的黄三角形).这样就由n边形的三角剖分得到了n+1边形的三角剖分.注意保持基准边对应基准边.
(2) 对于n+1边形的一种三角剖分, 任选除基准边以外的一条边 (图中的红边).将该边"压缩"成一点 (图中的红点),同时剖分中以该边为一边的三角形(图中黄三角形)"压缩"成一条线段 (图中黄线段).这样就由n+1边形的三角剖分得到了n边形的三角剖分.
下图以n = 5为例, 展示了上述两种操作的代表情形(五边形变为其右边的六边形):
其中最后一行是黄线段与基准边重合的情形.
n边形的每一种三角剖分图形中, 都恰有2n-3条线段 (n条边和n-3条对角线).因此操作(1)中的黄线段有2n-3种选法.在此基础上, 红点有2种选法, 因此每种n边形剖分方法有4n-6种进行操作(1)的选择.反过来, 操作(2)中的红边有n种选法 (不能选为基准边).因此每种n+1边形剖分方法有n种进行操作(2)的选择.操作(1)和操作(2)是互逆的, 这就得到等式(4n-6)·D[n] = n·D[n+1],即D[n+1]/D[n] = (4n-6)/n.
也许表述的不是很清楚, 有疑问请继续追问.
不想扣财富的话可用私信或百度Hi.英文好的话可参考: http://en.wikipedia.org/wiki/Catalan_number比百科词条全面清楚, 上述推导就来自其中的证法4.需要注意的是这里的D[n]对应那里的C[n-2].
一般所指的三角剖分数D[n],是指将凸n边形分成n-2个三角形的方法数,
其中三角形的顶点必须是n边形的顶点.
n = 3,4,5,6时依次为1,2,5,14.
递推公式为D[n+1] = D[n]·(4n-6)/n.
也可用组合数表示为D[n] = C(2n-4,n-2)/(n-1).
凸多边形三角划分一节有n = 6的情形的图.
从你的组合解法和n = 5时得10的结果来说,
也许你想求的是以n边形的顶点为顶点的三角形的个数?
这个要简单许多,就是如你所说的C(n,3).
那么n = 5时得10,n = 6时得20都是正确的.
总之,上面是两个不同问题.
请先明确你所想求的"三角剖分数"具体是什么意义.
再问： 你的回答前后矛盾嘛~~~不赘述，哪里矛盾你自己看吧。
再答： 好吧, 我的意思是"一般意义的"三角剖分数应该是D[n]那个序列: 1, 2, 5, 14, 42, 132, 429,... 如果你想求的是"一般意义的"三角剖分数, 那么用D[n+1] = D[n]·(4n-6)/n或者D[n] = C(2n-4,n-2)/(n-1)可以得到正确的结果. 特别的D[6] = 14. 但是这个"一般意义"的三角剖分数不满足你所说的D[5] = 10, 而D[6]也不等于28或20, 所以我不知道你想求的是"何种意义的"三角剖分数? 需要麻烦你解释一下, 我再回答该种意义的三角剖分数应该怎样计算.
再问： 我所要知道的是：以平面凸多边形的顶点为三角形的三个顶点，所进行的三角剖分。其实我已经知道还是我用阶乘求组合的方式求得的结果对——当然，这么不谦虚地说话，是站在我所要的以多边形的顶点为三角形的三个顶点这一立场之上。但是，我还想知道的是：乌尔班的三角剖分公式为什么不能适用于我说的这种三角剖分？乌尔班三角剖分公式有其局限性吗？
再答： 重复一下我所说的"一般意义的"三角剖分的定义:将凸n边形分划为n-2个三角形, 其中三角形的顶点必须是n边形的顶点.
所以"以多边形的顶点为三角形的顶点"这一点并没有分歧,有分歧的还是更基本的问题: 什么是三角剖分? 这一点你还是没有解释清楚.
用语言解释不够清楚的话可以参见下图:
这是n = 4, 5, 6时, "一般意义"的全部三角剖分, 种数分别是2, 5, 14.其中分划所得的每个三角形的顶点都是多边形的顶点, 且不难验证这些就是全部.这些数值很好的符合乌尔班公式.
如果你所要的三角剖分数在n = 5时为10, n = 6时为20,你能否指出有哪些情况不包含于上面所列?按我的揣度, 你所求的其实不是三角剖分数, 而是以n边形的顶点为顶点的三角形个数.n = 5时如下图:
这样一来, 就有10个了, C(n,3)也能说得通了.但是这计数的不是三角剖分, 上面那排并没有将五边形划分成三角形.这样一来不能适用乌尔班公式也没有什么不正常.
当然, 这只是我对你本意的一种猜测, 究竟如何还是需要你来解释一下.
再问： 对啦，就是这个！您所说的三角剖分的方法数量与三角剖分的个数这两个，我都求证过了，与您的详解一致。但看了您的详解我才知道，乌尔班公式是求证三角剖分方法数量的（对吗？），而非三角剖分的个数——这正是我认为乌尔班公式与阶乘结果不一致的错误原因。最后再次请您不弃肤受赐教：乌尔班的三角剖分到底是怎样的？那些乌漆麻黑的百科词条我都看不懂~~~谢谢啦！
再答： 你理解的很对, 乌尔班公式求的就是三角剖分的方法数.下面给出一种乌尔班公式的推导方法,
虽然并不是很困难, 但是理解起来需要花点功夫.
记凸n边形的三角剖分方法数为D[n].思路很明确: 尝试将n边形的三角剖分方法与n+1边形的三角剖分方法建立某种对应关系.作为建立联系的基准, 对n边形和n+1边形都选择一条基准边 (图中的绿边).然后考虑如下两种互逆的操作:
(1) 对于n边形的一种三角剖分, 任选图形中的一条线段 (图中的黄线段),再选择该线段的一个端点 (图中的红点).将该点"膨胀"为一条边 (图中的红边), 同时线段"膨胀"为一个三角形 (图中的黄三角形).这样就由n边形的三角剖分得到了n+1边形的三角剖分.注意保持基准边对应基准边.
(2) 对于n+1边形的一种三角剖分, 任选除基准边以外的一条边 (图中的红边).将该边"压缩"成一点 (图中的红点),同时剖分中以该边为一边的三角形(图中黄三角形)"压缩"成一条线段 (图中黄线段).这样就由n+1边形的三角剖分得到了n边形的三角剖分.
下图以n = 5为例, 展示了上述两种操作的代表情形(五边形变为其右边的六边形):
其中最后一行是黄线段与基准边重合的情形.n边形的每一种三角剖分图形中, 都恰有2n-3条线段 (n条边和n-3条对角线).因此操作(1)中的黄线段有2n-3种选法.在此基础上, 红点有2种选法, 因此每种n边形剖分方法有4n-6种进行操作(1)的选择.反过来, 操作(2)中的红边有n种选法 (不能选为基准边).因此每种n+1边形剖分方法有n种进行操作(2)的选择.操作(1)和操作(2)是互逆的, 这就得到等式(4n-6)·D[n] = n·D[n+1],即D[n+1]/D[n] = (4n-6)/n.
也许表述的不是很清楚, 有疑问请继续追问.
不想扣财富的话可用私信或百度Hi.英文好的话可参考: http://en.wikipedia.org/wiki/Catalan_number比百科词条全面清楚, 上述推导就来自其中的证法4.需要注意的是这里的D[n]对应那里的C[n-2].