数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 1793|回复: 7

将圆上 3n 个点连成 n 个没有共同顶点且不相交的三角形,共有几种不同的连法?

[复制链接]
发表于 2020-11-29 21:30 | 显示全部楼层 |阅读模式
分治算法题

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2020-12-1 06:32 | 显示全部楼层
第一个三角形第一个顶点有3n种取法,其第二个顶点可紧靠第一个取右,也可(顺时针,下同)间隔(该三角形已经放好的上个顶点,下同)3a个点(a<n),则其有1+(n-1)=n种取法。第三个顶点可紧靠第二个放右,也可相应间隔3b个点(b<a),则该第三个顶点有多少种取法?
回复 支持 反对

使用道具 举报

发表于 2020-12-1 08:13 | 显示全部楼层
紧靠第二个顶点右取有n种取法,b=n-2时有n-2种取法,同理直至1种取法,共有n+(n-2)+(n-3)+(n-4)+...+1=n+[(n-2)+1]*(n-2)/2=n+(n-1)(n-2)/2
那么第一个三角形共有3n*n*[n+(n-1)(n-2)/2]种取法吗?
回复 支持 反对

使用道具 举报

发表于 2020-12-2 09:37 | 显示全部楼层
不妨先思考这个:
4进制数字1,2,3分别表示三角形顶点的一个不连续,二个连续,三个连续构造情形。它们的总和为3n,并且2的数量为a,1是a个+3m个。
这有多少种合如上要求的完整数列?
回复 支持 反对

使用道具 举报

发表于 2020-12-5 13:37 | 显示全部楼层
本帖最后由 王守恩 于 2020-12-5 14:01 编辑

是这串数吗?心里没底。
\(\frac{\Gamma(3 n + 1)}{\Gamma( n + 1)\Gamma(2 n + 2)}\)
\(a(n)=1, 3, 12, 55, 273, 1428, 7752, 43263, 246675....\)
回复 支持 反对

使用道具 举报

发表于 2020-12-6 09:05 | 显示全部楼层
本帖最后由 王守恩 于 2020-12-6 09:12 编辑
王守恩 发表于 2020-12-5 13:37
是这串数吗?心里没底。
\(\frac{\Gamma(3 n + 1)}{\Gamma( n + 1)\Gamma(2 n + 2)}\)
\(a(n)=1, 3, 12,  ...

5楼的数字串没问题(网上的方法往前推不了)。
15个点可分成5个三角形,确定第1个三角形有15种可能(如下)
01,1+02+03:55
02,1+02+06:12
03,1+02+09:09
04,1+02+12:12
05,1+02+15:55
06,1+05+06:12
07,1+05+09:03
08,1+05+12:03
09,1+05+15:12
10,1+08+09:09
11,1+08+12:03
12,1+08+15:09
13,1+11+12:12
14,1+11+15:12
15,1+14+15:55
共有55+12+09+12+55+12+03+03+12+09+03+09+12+12+55=273种不同的连法
同理,18个点(第1个三角形21种可能)有273×3+55×6+36×6+12×3+9×3=1428种不同的连法
回复 支持 反对

使用道具 举报

发表于 2020-12-7 19:47 | 显示全部楼层
本帖最后由 王守恩 于 2020-12-7 20:06 编辑
王守恩 发表于 2020-12-5 13:37
是这串数吗?心里没底。
\(\frac{\Gamma(3 n + 1)}{\Gamma( n + 1)\Gamma(2 n + 2)}\)
\(a(n)=1, 3, 12,  ...

王守恩 发表于 2020-12-5 13:37
是这串数吗?心里没底。
\(\frac{\Gamma(3 n + 1)}{\Gamma( n + 1)\Gamma(2 n + 2)}\)
\(a(n)=1, 3, 12, 55, 273, 1428, 7752, 43263,   ...


从"简单"想起。

1,n=1,a(1)=1
  3个点只能组成1个三角形。
  确定第1个三角形有1种可能
  1,1+2+3:1
  共有1=1种不同的连法

2,n=2,a(2)=3
  6个点可以组成2个三角形。
  确定第1个三角形有3种可能
  1,1+2+3:1
  2,1+2+6:1
  3,1+5+6:1
  共有1+1+1=3种不同的连法

3,n=3,a(3)=12
  9个点可以组成3个三角形。
  确定第1个三角形有6种可能
  1,1+2+3:3
  2,1+2+6:1
  3,1+2+9:3
  4,1+5+6:1
  5,1+5+9:1
  6,1+8+9:3
  共有3+1+3+1+1+3=12种不同的连法

4,n=4,a(4)=55
  12个点可以组成4个三角形。
  确定第1个三角形有10种可能
  01,1+02+03:12
  02,1+02+06:03
  03,1+02+09:03
  04,1+02+12:12
  05,1+05+06:03
  06,1+05+09:01
  07,1+05+12:03
  08,1+08+09:03
  09,1+08+12:03
  10,1+11+12:12
  共有12+03+03+12+03+01+03+03+03+12=55种不同的连法

5,n=5,a(5)=273
  15个点可以组成5个三角形。
  确定第1个三角形有15种可能
  01,1+02+03:55
  02,1+02+06:12
  03,1+02+09:09
  04,1+02+12:12
  05,1+02+15:55
  06,1+05+06:12
  07,1+05+09:03
  08,1+05+12:03
  09,1+05+15:12
  10,1+08+09:09
  11,1+08+12:03
  12,1+08+15:09
  13,1+11+12:12
  14,1+11+15:12
  15,1+14+15:55
  共有55+12+09+12+55+12+03+03+12+09+03+09+12+12+55=273种不同的连法

同理,18个点(第1个三角形21种可能)有273×3+55×6+36×6+12×3+9×3=1428种不同的连法
回复 支持 反对

使用道具 举报

发表于 2020-12-11 11:58 | 显示全部楼层
尊敬的楼主:能用您的软件验算“7752”。谢谢!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-28 16:57 , Processed in 0.075195 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表