Recursive (Counting) GeneratingFunction Challenging

Problem - 4427

As shown, an isosceles trapezoid is obtained by removing the top part of an equilateral triangle. The lengths of its two bases are $a$ and $b$, respectively, which are both integers. Both bases and sides are equally divided into unit-length parts. Their ending points are then connected to create several segments which are parallel to either two bases or one side. Find the number of equilateral triangles in this diagram.


One way to solve this problem is to use recursion and also the conclusion of # 4426. For convenience, let $h=b-a$.

Let $u_b$ and $d_b$ be the numbers of upward and downward equilateral triangles, respectively. Then the difference between $u_b$ and $u_{b-1}$ are those triangles whose bases are on the bottom line. The difference between $d_b$ and $d_{b-1}$ are those triangles whose downward vertices are on the bottom line.

For a  triangle to have its base on the bottom line, the length of its base cannot be longer than $h$. On the other hand, any two points not apart bigger than $h$ on the bottom can be a base of a triangle. Hence, the number of such triangles equals to the number of two points among $(b+1)$ points whose are not apart bigger than $h$. This is the same as # 4226 where setting $n=(b+1)$, $k=2$, and $m=h$. So $$\begin{align*} u_b-u_{b-1}=\ & h\left(b+1-\frac{1}{2}(h+1)\right)\\=\  &(a+h+1)h - \frac{h(h+1)}{2}\\=\ & ah +\frac{h(h+1)}{2}\end{align*}$$

where $u_a=0$. Considering $b$ as a constant and $h=a-b$ as a variable, then $$\begin{align*} u_b=\ & u_{b-1} + ah + \frac{h(h+1)}{2}\\=\ &a\sum_{i=0}^{h}i+\sum_{i=0}^{h}\frac{i(i+1)}{2}\\=\ &a\frac{h(h+1)}{2}+\sum_{i=0}^{h}\binom{i+1}{2}\\=\ &a\binom{h+1}{2}+\binom{h+2}{3} \end{align*}$$

In order to establish the recursion of $d_n$, two different cases need to be considered: $b\le 2a$ and $b > 2a$. The difference between these two cases is whether $a$ can be the base of a triangle whose vertex reaches $b$.

When $b\le 2a$, then every line can be a good base for triangles. Let's consider the line with distance of $k$, as shown. Then every segment of length $(b-a-k)$ has a bijective relation with a triangle whose vertex lying on the bottom base.

The length of this line is $(a+k)$. Therefore, the number of good triangles is $$(a+k)-(b-a-k)+1=(2a-b+1)+2k$$

It follows that $$\begin{align*} d_{b}-d_{b-1}=\ &\sum_{k=0}^{b-a-1}\left((2a-b+1)+2k\right)\\=\ &(b-a)(2a-b+1) + (b-a-1)(b-a)\\=\ &a(b-a)\\=\ &ah \end{align*}$$

Because $d_a=0$, it follows that $$d_b= d_{b-1}+ah=a\sum_{i=0}^{h}i=a\binom{h+1}{2}$$

When $b > 2a$, no every line can be used as the base to construct an equilateral triangle whose vertex can reach the bottom line. So, the starting index in the previous sum should be lifted to $(\lfloor{\frac{b+1}{2}}\rfloor-a)$, where $\lfloor{x}\rfloor$ returns the largest integer not exceeding the give real number $x$. Accordingly, $$\begin{align*} d_b=\ & d_{b-1} + \sum_{k=\lfloor{\frac{b+1}{2}}\rfloor-a}^{b-a-1}\left((2a-b+1)+2k\right)\\=\ &d_{b-1}+\left(b-\left\lfloor{\frac{b+1}{2}}\right\rfloor\right)\cdot\left\lfloor{\frac{b+1}{2}}\right\rfloor\end{align*}$$

Using even-odd analysis can show that $$\left(b-\left\lfloor{\frac{b+1}{2}}\right\rfloor\right)\cdot\left\lfloor{\frac{b+1}{2}}\right\rfloor=\left\lfloor{\frac{b^2}{4}}\right\rfloor$$

Also note that $d_a=0$, so $$d_{b}=d_{b-1}+\left\lfloor{\frac{b^2}{4}}\right\rfloor=\sum_{k=a}^{2a}d_{k} + \sum_{k=2a+1}^{b} \left\lfloor{\frac{k^2}{4}}\right\rfloor$$

By the early result when $b\le 2a$ and note $h=2a-a=a$ in this case, the first term above equals $a\binom{a+1}{2}$. The second term can be calculated by analyzing the odd-even parity of $b$.

When $b=2m$ is even, then $$\begin{align*} \sum_{k=2a+1}^{b} \left\lfloor{\frac{k^2}{4}}\right\rfloor =\ &a(a+1)+(a+1)^2+(a+1)(a+2)+\cdots+m(m-1)+m^2\\=\ &2\sum_{k=a+1}^{m}k(k-1)+\sum_{k=a+1}^{m}k\\=\ &4\left(\binom{m+1}{3}-\binom{a+1}{3}\right)+\left(\binom{m+1}{2}-\binom{a+1}{2}\right) \end{align*}$$

It follows in this case $$\begin{align*} d_b =\ &a \binom{a+1}{2}+4\left(\binom{m+1}{3}-\binom{a+1}{3}\right)+\left(\binom{m+1}{2}-\binom{a+1}{2}\right)\\=\  &4\binom{m+1}{3}+\binom{m+1}{2}-\binom{a+1}{3}\end{align*}$$

When $b=2m+1$ is odd, then the result above needs to include one additional term $m(m+1)$ which can be written as $2\binom{m+1}{2}$. Accordingly, $$d_b=4\binom{m+1}{3}+3\binom{m+1}{2}-\binom{a+1}{3}$$

Consolidating the two cases and replace $m$ with $\left\lfloor{\frac{b}{2}}\right\rfloor$ gives: $$d_b=4\binom{\left\lfloor{\frac{b}{2}}\right\rfloor+1}{3}+(2+(-1)^b)\binom{\left\lfloor{\frac{b}{2}}\right\rfloor+1}{2}-\binom{a+1}{3}$$

The total number will be $u_b+d_b$. So, in conclusion, the answer is (where $h=b-a$)

  • if $b \le 2a$, then $$2a\binom{h+1}{2}+\binom{h+2}{3}$$
  • if $b > 2a$, then $$a\binom{h+1}{2}+\binom{h+2}{3}+4\binom{\left\lfloor{\frac{b}{2}}\right\rfloor+1}{3}+(2+(-1)^b)\binom{\left\lfloor{\frac{b}{2}}\right\rfloor+1}{2}-\binom{a+1}{3}$$

report an error