找回密码
 欢迎注册
查看: 42008|回复: 48

[讨论] 周长为整数的三角形计数问题

[复制链接]
发表于 2018-2-6 14:16:23 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

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

×
定义周长为n的三角形,三边长均为正整数,假设用
t(n)表示这种三角形中相互不全等的三角形的个数,求t(n)的递推公式

已知:
t(1) = 0
t(2) = 0
t(3) = 1
t(4) = 0
t(5) = 1
t(6) = 1
t(7) = 2
t(8) = 1
t(9) = 3

点评

惊现!我还以为你弃坑了:P  发表于 2018-2-6 20:08
真是无心恋帖呀  发表于 2018-2-6 14:37
是呀  发表于 2018-2-6 14:30
久违了  发表于 2018-2-6 14:29
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 14:26:02 | 显示全部楼层
  1. arr = Length[ Select[IntegerPartitions[#, {3}], #[[1]] < #[[2]] + #[[3]] && #[[2]] > #[[1]] - #[[3]] &]] & /@Range[0, 100];
  2. FindGeneratingFunction[arr, x] // FullSimplify
复制代码

生成函数是\[f(x)=\frac{x^3}{(1 - x^2)(1 - x^3)(1 - x^4)}\]

https://oeis.org/A005044答案有了,就是不知道怎么给出解释了.

点评

嗯嗯,学习了  发表于 2018-2-6 20:54
其实看到这种类型的母函数就能想到整数拆分(或不等方程有序非负整数解),之前论坛出现过好多次这种问题  发表于 2018-2-6 20:41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 15:17:26 | 显示全部楼层
wayne 发表于 2018-2-6 14:26
生成函数是\[f(x)=\frac{x^3}{(1 - x^2)(1 - x^3)(1 - x^4)}\]

https://oeis.org/A005044答案有了,就 ...

假设三边是$a\leqb\leqc,$为了去掉不等号的限制,令$b=a+s,c=b+t$,其中$s,t$为非负数,
代入$a+b>c$,得$a+a+s>a+s+t$,即$a>t$,令$a=t+k+1$,其中$k$为非负数,
得$a+b+c=3a+2s+t=3(t+k+1)+2s+t=4t+3k+2s+3=n$
问题归结为最后一个方程的非负整数解。可以套用这个生成函数。

评分

参与人数 1威望 +6 金币 +6 贡献 +6 经验 +6 鲜花 +6 收起 理由
wayne + 6 + 6 + 6 + 6 + 6 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 18:31:08 | 显示全部楼层
我来凑一凑热闹!欢迎大家批评!可以化简吗?

        \(\D t(12k+\ \ 3 )=t(12k+\ \ 6 )=1+\ \ 6 k+6C_{k}^2\)

        \(\D t(12k+\ \ 5 )=t(12k+ \ \ 8 )=1+ \ \ 7 k+6C_{k}^2\)

        \(\D t(12k+ \ \ 7 )=t(12k+10)=2+\ \ 8 k+6C_{k}^2\)

        \(\D t(12k+ \ \ 9 )=t(12k+12)=3+\ \ 9 k+6C_{k}^2\)

        \(\D t(12k+11)=t(12k+14)=4+10k+6C_{k}^2\)

        \(\D t(12k+13)=t(12k+16)=5+11k+6C_{k}^2\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 20:34:12 | 显示全部楼层
由2#母函数可得通项公式\[t_n=\frac{1}{288}\left(6n(n+3)-(-1)^n(18n+27)-36\sqrt{2}\sin\frac{(2n+1)\pi}{4}+64\cos\frac{2n\pi}{3}-1\right)\]
  1. t[n_] := (6 n (n + 3) - 36 Sqrt[2] Sin[(2 n + 1) Pi/4] +
  2.     64 Cos[2 n Pi/3] - 9 (2 n + 3) (-1)^n - 1)/288
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 21:00:06 | 显示全部楼层
楼上的可以继续化简一下:\[t_n =\left [\frac{n^2}{12}\right]-\left\lfloor \frac{n}{4}\right\rfloor  \left\lfloor \frac{n+2}{4}\right\rfloor\]
中括号\([a]\)是\(a\)取圆整,即四舍五入,第二个$\lfloor a\rfloor$是\(a\)向下取整,即取整数部分

点评

看错一个符号,应该没问题  发表于 2018-2-6 22:17
n=4,大家都等于0呀  发表于 2018-2-6 22:05
n=4时似乎有点差别  发表于 2018-2-6 21:54
不知是否有严格推导保证,可以尝试一下很大的 `n`,看看是否成立:)  发表于 2018-2-6 21:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 21:56:41 | 显示全部楼层
这个题目不难,我们考虑$t(n+3)$,其中三边长度满足
\(\begin{cases}0\lt a\le b\lt c\\ a+b>c\\ a+b+c=n+3 \end{cases}\)
我们分两类
i)\(a+b-c=1\),对于这种情况,必然有n是偶数而且\(c=\frac{n}{2}+1,1\le a \le \lfloor\frac{n}{4}\rfloor+1\),所以共\(\lfloor\frac{n}{4}\rfloor+1\)种情况
ii)\(a+b-c\ge2\),这时必然有\(a\ge2\),于是我们可以分别用\(a=a-1,b=b-1,c=c-1\)做替换变换为$t(n)$中的解,所以正好$t(n)$个
于是我们得出
\(t(n+3)=t(n)+\begin{cases}\lfloor\frac{n}{4}\rfloor+1&当n是偶数\\0&当n是奇数\end{cases}\)
或者可以改写为
\(\begin{cases}t(4k+3)=t(4k)+k+1\\t(4k+2)=t(4k-1)\\t(4k+1)=t(4k-2)+k\\t(4k)=t(4k-3)\end{cases},k\ge 1\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 22:12:46 | 显示全部楼层
考虑到 \[-\frac 19 \leqslant \frac{1}{288}\left(-36\sqrt{2}\sin\frac{(2n+1)\pi}{4}+64\cos\frac{2n\pi}{3}\right)\leqslant \frac 29\]故可加上一个小数 `\alpha`,使得 `\frac 19< \alpha < \frac 79`,则通项公式可表示为 \[t_n=\left\lfloor\frac{6n(n+3)-(-1)^n(18n+27)-1+\alpha}{288}\right\rfloor\]比如令 `\alpha=1/4`,则有\[t_n=\left\lfloor\frac{6n(n+3)-(-1)^n(18n+27)+46}{288}\right\rfloor\]

点评

太好了!谢谢kastin!  发表于 2018-2-7 12:30
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-7 11:03:54 | 显示全部楼层
\(t(n+3)=t(n)+\begin{cases}\lfloor\frac{n}{4}\rfloor+1&当n是偶数\\0&当n是奇数\end{cases}\)
或者可以改写为
\(\begin{cases}t(4k+3)=t(4k)+k+1\\t(4k+2)=t(4k-1)\\t(4k+1)=t(4k-2)+k\\t(4k)=t(4k-3)\end{cases},k\ge 1\)
于是
\(\begin{cases}t(4k+3)=t(4k)+k+1=t(4k-3)+k+1\\t(4k+2)=t(4k-1)=t(4k-4)+k\\t(4k+1)=t(4k-2)+k=t(4k-5)+k\\t(4k)=t(4k-3)=t(4k-6)+k-1\end{cases},k\ge 1\)
于是记$s(n)=t(n+1)-t(n)$,那么\(s(n)=s(n-6)+\begin{cases}1&当n \equiv 0,2&\pmod 4\\ 0&当n \equiv 1&\pmod 4\\ -1&当n \equiv3&\pmod 4\end{cases}\)
其中最后部分是一个周期为4的函数,可以写成$a+b(-1)^n+ci^n+d(-i)^n$的形式,然后递推下去就可以找到母函数了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-7 13:02:23 | 显示全部楼层
本帖最后由 王守恩 于 2018-2-7 18:37 编辑
mathe 发表于 2018-2-7 11:03
\(t(n+3)=t(n)+\begin{cases}\lfloor\frac{n}{4}\rfloor+1&当n是偶数\\0&当n是奇数\end{cases}\)
或者可以 ...


      一边围着火炉取暖,一边聆听大师们无私讲解,机遇太好了!我来添点柴!

        \(\D 当 n=2 k时,\ \ t(n)=\left[\frac{k^2}{12}\right]\)

        \(\D 当 n=2 k+1时,t(n)=\left[\frac{(k+2)^2}{12}\right]\)

       中括号[a]是a取圆整,即四舍五入。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 14:34 , Processed in 0.048784 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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