Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
From oeis.org/A333829 we can infer that the coefficient of $x^m$ in $T_n(x)$, which is $\frac{1}{mn+1}\binom{mn+1}{m}$, is the Ehrhart polynomial for the $n$-dimensional polytope which is the convex hull of length $n+1$ nondecreasing parking functions. I haven't checked this and don't know of a reference, nor do I know why this Ehrhart polynomial also counts trees. But if this all checks out, the reciprocity theorem for Ehrhart polynomials might help with a combinatorial explanation.
The OEIS page for the Lucas polynomials uses a different normalization. Here is a corrected version of my comment on them. The polynomials $h_n(x)$ in Tim's answer have the generating function $\sum_{n=0}^\infty h_n(x) y^n = (2-xy)/(1-xy-xy^2)$. They are given by $h_0(x)=2$ and $$h_n(x) = \sum_{k=0}^{\left\lfloor n/2\right\rfloor}\frac{n}{n-k}\binom{n-k}{k}x^{n-k}$$ for $n>0$. They are related to the Chebyshev polynomials of the first kind $T_n(x)$ by $$h_n(x) = 2(-\sqrt{-x})^{n} T_n(\sqrt{-x}/2)$$ so their roots can be determined from the roots of the Chebyshev polynomials.
So $f_{2n}(x) = (-x)^n U_n(\sqrt{-x}/2)^2$, where $U_n$ is the Chebyshev polynomial of the second kind. Most likely there is some sort of expression for $f_{2n+1}(x)$ in terms of Chebyshev polynomials but it will not be as simple.
The geometry of the universe of Arthur C. Clarke's short story "The Wall of Darkness" is claimed to be an "Alice handle." See scifi.stackexchange.com/questions/63411/…
The binomial coefficient $\binom cn$ is defined to be $c(c-1)\cdots (c-n+1)/n!$ for all $c$. Then $\binom {-c}{n} = (-1)^n \binom{c+n-1}{n}$. Vandermonde's theorem as I stated it is an identity of polynomials in $a$ and $b$, so it is valid for all $a$ and $b$, not just nonnegative integers. If we set $a=-i-1$ and $b=i-m-1$ in $\sum_{j=0}^n \binom{a}{j}\binom{b}{n-j} = \binom{a+b}{n}$ and simplify using $\binom {-c}{n} = (-1)^n \binom{c+n-1}{n}$ we get $(-1)^n\sum_{j=0}^n \binom{i+j}{j}\binom{m-i+n-j}{n-j}=(-1)^n\binom{m+n+1}{n}$, which is equivalent to your identity.
See Louis Comtet, Advanced Combinatorics. Reidel, Dordrecht, 1974, pp. 139–140 and D. H. Lehmer, Numbers associated with Stirling numbers and $x^x$, Rocky Mountain J. Math. 15 (1985), no. 2, 461–479, Number Theory (Winnipeg, Man., 1983).
An application of the diamond lemma to enumeration can be found in the proof of Theorem 4.4 in my paper with Ji Li, Enumeration of point-determining graphs, J. Combin. Theory Ser. A 118 (2011), 591–612, doi.org/10.1016/j.jcta.2010.03.009.
