What is the recurrence relation of generating triangle?

Question

I wanna make recurrence relation of making triangle.

For all the sides $a,b,c$

$a+b+c=n$

So the series should be $\{0,0,1,0,1,1,2,1,3\dots\}$

It's really messing up my heads

If you know what I'm trying to say, please help me find recurrence relation

Answer 1

Up to my understanding, you are asking for

the number of triangles with integer sides for given perimeter $n$.

There are some ambiguities what number of triangles means. The number you gave is consistent with the assumption that two triangles of sides $( a_1, b_1, c_1 )$ and $(a_2, b_2, c_2)$ are considered to be the same when and only when $(a_2,b_2,c_2)$ is an permutation of $(a_1,b_1,c_1)$.

We will adopt this assumption for counting.

Let $a, b, c$ be the sides of any triangle. Let $N_n$ be the number of triangles for perimeter $a + b + c = n$. The number you ask equals to the size of the set $$N_n = \# \left\{ (a,b,c) \in \mathbb{Z}_{+}^3 : 1 \le a \le b \le c; \begin{align} a + b &> c\\ b + c &> a \\ c + a &> b \end{align} \right\}$$ When we assume $1 \le a \le b \le c$, two of the triangle equalities $b + c > a$, $c + a > b$ satisfied automatically. Let $p = b - a$ and $q = c - b$, the remaining triangle equality reduces to $q < a$.

Extend the definition of $N_n$ to negative $n$ by setting $N_n = 0$ whenever $n \le 0$.
The OGF for the $N_n$ equals to

$$\begin{align} f(x) &\stackrel{def}{=} \sum_{n=-\infty}^\infty N_n x^n = \sum_{n=1}^\infty N_n x^n = \sum_{\substack{1 \le a \le b \le c\\a+ b > c}} x^{a+b+c}\\ &= \sum_{a=1}^\infty x^a \sum_{p=0}^\infty x^{a+p} \sum_{q=0}^{a-1} x^{a+p+q} = \sum_{a=1}^\infty x^{3a}\sum_{p=0}^\infty x^{2p}\sum_{q=0}^{a-1} x^q = \sum_{a=1}^\infty x^{3a}\sum_{p=0}^\infty x^{2p}\left(\frac{1-x^a}{1-x}\right)\\ &= \frac{1}{1-x}\left(\sum_{a=1}^\infty(x^{3a} - x^{4a})\right)\left(\sum_{p=0}^\infty x^{2p}\right) = \frac{1}{1-x}\left(\frac{x^3}{1-x^3}-\frac{x^4}{1-x^4}\right)\left(\frac{1}{1-x^2}\right)\\ &= \frac{x^3}{(1-x^2)(1-x^3)(1-x^4)} \end{align} $$

If you really want a recurrence relation for $N_n$, you can multiply both sides of above expression by $$(1-x^2)(1-x^3)(1-x^4) = 1-x^2-x^3-x^4+x^5+x^6+x^7-x^9$$ Compare coefficients on both sides, one obtain

$$N_{n} - N_{n-2} - N_{n-3} - N_{n-4} + N_{n-5} + N_{n-6} + N_{n-7} - N_{n-9} = \begin{cases} 1, & n = 3\\ 0, & \text{ otherwise } \end{cases} $$ Together with the initial conditions $N_n = 0$ for $n \le 0$, this is enough to determine the values of $N_n$ for all $n > 0$.

This sequence $N_n$ is known as Alcuin's sequence, you can find a table of its values for small $n$ on OEIS A005044. Look at references in both the wiki and OEIS for more details.

Answer 2

Plugging your sequence into OEIS gives A005044 Among the formulas is the explicit $a(n) = (6*n^2 + 18*n - 9*(-1)^n*(2*n + 3) - 36*\sin(\pi*n/2) - 36*\cos(\pi*n/2) + 64*\cos(2*\pi*n/3) - 1)/288$