周长为整数的三角形计数问题

无心人

定义周长为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

wayne

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答案有了，就是不知道怎么给出解释了．

lsr314

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$
问题归结为最后一个方程的非负整数解。可以套用这个生成函数。

王守恩

我来凑一凑热闹！欢迎大家批评！可以化简吗？

        \(\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\)

kastin

由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

复制代码

wayne

楼上的可以继续化简一下：\[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\)向下取整，即取整数部分

mathe

这个题目不难，我们考虑$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\)

kastin

考虑到 \[-\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\]

mathe

\(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$的形式,然后递推下去就可以找到母函数了

王守恩

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取圆整，即四舍五入。