免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
Board logo

标题: [组合] 直角三角形个数 [打印本页]

作者: lrh2006    时间: 2019-2-7 23:06     标题: 直角三角形个数

QQ截图20190207235351.jpg
2019-2-7 23:54

这个怎么数好,请各位赐教,谢谢

图片附件: QQ截图20190207235351.jpg (2019-2-7 23:54, 10.03 KB) / 下载次数 1473
http://kuing.orzweb.net/attachment.php?aid=6952&k=dba82920f27094a0a5cd2a130c363d25&t=1711716842&sid=W8Vvy2


作者: kuing    时间: 2019-2-8 01:26

分类数呗
两直角边平行于坐标轴的:由于选定任一直角顶点后,另外两顶点都有三种选择,所以这种共 `4^2\times3^2=144`;
斜边平行于坐标轴的:易知只有当斜边长为 `2` 时才行,由此易数出共 `24` 个;
三边都不平行于坐标轴的:貌似就只有这样的
QQ截图20190208012525.png
2019-2-8 01:25

易数出共 `16` 个。
没有了吧?那就是 `184` 咯

图片附件: QQ截图20190208012525.png (2019-2-8 01:25, 3.79 KB) / 下载次数 1455
http://kuing.orzweb.net/attachment.php?aid=6955&k=063fb733ca463061447c4729040d0da5&t=1711716842&sid=W8Vvy2


作者: lrh2006    时间: 2019-2-9 20:50

回复 2# kuing
QQ截图20190210023840.jpg
2019-2-10 02:39

貌似落了几个,哈哈。看到答案,分类方法不一样,给你瞧瞧啊

图片附件: QQ截图20190210023840.jpg (2019-2-10 02:39, 30.55 KB) / 下载次数 1445
http://kuing.orzweb.net/attachment.php?aid=6965&k=be79718127d82cce0aa1285c84e4b2a3&t=1711716842&sid=W8Vvy2


作者: kuing    时间: 2019-2-9 22:06

唉,还是最后的漏了,还真不止上图中那一种,还有下图绿线的:
QQ截图20190208012525.png
2019-2-9 22:05

同样也是 16 个,补上就是 200 了

图片附件: QQ截图20190208012525.png (2019-2-9 22:05, 4.44 KB) / 下载次数 1453
http://kuing.orzweb.net/attachment.php?aid=6964&k=70c07cd004b501f560d8ed9b1380508c&t=1711716842&sid=W8Vvy2


作者: 青青子衿    时间: 2019-2-10 23:07

唉,还是最后的漏了,还真不止上图中那一种,还有下图绿线的:
同样也是 16 个,补上就是 ...
kuing 发表于 2019-2-9 22:06

绿色的直角三角形可以用这个恒等式去记忆
\[\tan^{-1}\left(1\right)+\tan^{-1}\left(\frac{1}{2}\right)+\tan^{-1}\left(\frac{1}{3}\right)=\frac{\pi}{2}\]
作者: realnumber    时间: 2019-2-11 09:44

改成$5\times5,6\times6,n\times n$每一次n增大,有没新的直角形要计算的?
作者: kuing    时间: 2019-2-11 13:49

回复 6# realnumber

肯定多得多了……
QQ截图20190211134607.png
2019-2-11 13:48
QQ截图20190211135110.png
2019-2-11 13:51
……
边上两个就眼花了,中间的恐怕更花……

图片附件: QQ截图20190211134607.png (2019-2-11 13:48, 11.95 KB) / 下载次数 1510
http://kuing.orzweb.net/attachment.php?aid=6967&k=6258d20815efcfd01ed89b7f3934d56b&t=1711716842&sid=W8Vvy2



图片附件: QQ截图20190211135110.png (2019-2-11 13:51, 13.61 KB) / 下载次数 1506
http://kuing.orzweb.net/attachment.php?aid=6969&k=219ab8127e11071f8ae6aaee02f149fe&t=1711716842&sid=W8Vvy2


作者: realnumber    时间: 2019-2-11 14:24

那就三个问题分开算,
$n\times n$如楼上点阵中,以其中三点为三角形顶点.
1.有几个直角三角形?
2.如果(至少有一顶点不同的)两三角形全等,则视为同一个,则有几个直角三角形?
3.如果两三角形相似,视为同一类三角形,则有几类直角三角形?
作者: kuing    时间: 2019-2-11 16:52

最近展开式灵感爆棚!我又来了!

考虑一般情况,即点阵为 `n\times m` 的情形,以下默认 `x_i\in\{1,2,\ldots,n\}`, `y_i\in\{1,2,\ldots,m\}`。

首先,直角边平行于坐标轴的个数是 `nm(n-1)(m-1)` 这个就不用我说了吧,下面研究直角边不平行于坐标轴的。

设直角顶点的坐标为 `A(x_0,y_0)`,另外两顶点为 `B(x_1,y_1)`, `C(x_2,y_2)` 且 `k_{AB}>0`, `k_{AC}<0`,即 `(x_1-x_0)(y_1-y_0)>0`, `(x_2-x_0)(y_2-y_0)<0`,要垂直,即 `k_{AB}\cdot k_{AC}=-1`,也即 `(y_1-y_0)/(x_1-x_0)+(x_2-x_0)/(y_2-y_0)=0`,于是,构造
\[f(x_0,y_0)=\left( \sum_{(x_1-x_0)(y_1-y_0)>0}x^{(y_1-y_0)/(x_1-x_0)} \right)\left( \sum_{(x_2-x_0)(y_2-y_0)<0}x^{(x_2-x_0)/(y_2-y_0)} \right),\]
设 `f(x_0,y_0)` 展开式中的常数项为 `c(x_0,y_0)`,那么它就是以 `A(x_0,y_0)` 为直角顶点的直角三角形个数,让 `A` 取遍所有点,然后全加起来就是所求。

综上所述,直角三角形个数就是
\[\sum_{x_0=1}^n\sum_{y_0=1}^mc(x_0,y_0)+nm(n-1)(m-1).\]

另外,为便于软件输入,有必要对 `f(x_0,y_0)` 换个写法,即
\begin{align*}
f(x_0,y_0)={}&\left( \sum_{x_1=1}^{x_0-1}\sum_{y_1=1}^{y_0-1}x^{(y_1-y_0)/(x_1-x_0)}+\sum_{x_1=x_0+1}^n\sum_{y_1=y_0+1}^mx^{(y_1-y_0)/(x_1-x_0)} \right)\\
&\times\left( \sum_{x_2=1}^{x_0-1}\sum_{y_2=y_0+1}^mx^{(x_2-x_0)/(y_2-y_0)}+\sum_{x_2=x_0+1}^n\sum_{y_2=1}^{y_0-1}x^{(x_2-x_0)/(y_2-y_0)} \right).
\end{align*}

这样就得到了 Mathematica 的如下代码:
  1. c[x0_, y0_, n_, m_] :=
  2. Coefficient[
  3.   Expand[(Sum[x^((y1 - y0)/(x1 - x0)), {x1, 1, x0 - 1}, {y1, 1, y0 - 1}] +
  4.       Sum[x^((y1 - y0)/(x1 - x0)), {x1, x0 + 1, n}, {y1, y0 + 1, m}])
  5.       (Sum[x^((x2 - x0)/(y2 - y0)), {x2, 1, x0 - 1}, {y2, y0 + 1, m}] +
  6.       Sum[x^((x2 - x0)/(y2 - y0)), {x2, x0 + 1, n}, {y2, 1, y0 - 1}])], x, 0]
  7. cc[m_, n_] :=
  8. Sum[c[x0, y0, n, m], {x0, 1, n}, {y0, 1, m}] + n m (n - 1) (m - 1)
复制代码
然后输入 cc[4,4] 得到 200,看来没写错

cc[4, 5] 得 342
cc[5, 5] 得 596
cc[6, 6] 得 1444
cc[10, 10] 得 15332
cc[20, 20] 得 337960(用时半分多钟
cc[30, 30] 得 1984564(用时约8分钟

等等……
作者: kuing    时间: 2019-2-11 17:58

回复 9# kuing

其实也不需要让 `A` 取遍所有点,因为有对称性,只需取一个角以内即可,以 `n=4` 为例,只需让 `A` 取 `(2,1)` 和 `(2,2)` 即可,算出来分别乘以 `8` 和 `4` 再加起来即可。
所以上面的程序是可以优化一下减少计算的,不过懒得弄了,因为估计也没什么卵用,就算只需算 1/8 的点,这种展开式算法应该都会和上次那个整数分拆一样,时间和空间复杂度会非常高,大数肯定算不动的。
作者: lrh2006    时间: 2019-3-9 21:03

谢谢楼上各位,学习了...
原谅我很久没有来论坛,这一个来月忙飞起来,累坏宝宝了,所以,请原谅我吧
作者: isee    时间: 2019-3-9 21:19

回复 10# kuing

叹为观止,都看不动
作者: 色k    时间: 2019-3-9 22:15

回复 12# isee

没所谓,因为那方法只是理论上如此,实际上没啥用。
作者: 青青子衿    时间: 2019-3-24 16:53

OEIS网站太丰富了
4, 44, 200, 596, 1444, 2960, 5520, 9496, 15332, 23596
http://oeis.org/A077435
作者: 色k    时间: 2019-3-24 17:20

回复 14# 青青子衿






欢迎光临 悠闲数学娱乐论坛(第2版) (http://kuing.orzweb.net/) Powered by Discuz! 7.2