Problem
\[ f_{n,m}(x) = \sum_{K,F,C,V,5,0}(x^2-1)^{k-1}x^{2-2k}x^{\sum_{1\leq l_1 < l_2 \leq k}{a_{l_2}b_{l_1}}-a_{l_1}b_{l_2}}x^{\sum_{1\leq l \leq k} \gcd({a_l,b_l})}\]
where
\[ K: k\geq 1\]
\[ F: 0<\frac{a_1}{b_1}<\frac{a_2}{b_2}<\cdots<\frac{a_k}{b_k} < 1\]
\[C: \sum_{i=1}^k a_i = m\]
\[V: \sum_{i=1}^k b_i = n\]
\[5:\forall a_i \in \text{Z}_{>0}\]
\[0:\forall b_i \in \text{Z}_{>0}\]
Show that
\[ f_{n,m}(x) = x^{mn-m^2-n+2}\]
Solution:
Solve step by step, part by part.
Assume that each of \((a_i,b_i)\) is a vector, where b is x-axis and a is y-axis.
\[\sum_{1\leq l_1 < l_2 \leq k}{a_{l_2}b_{l_1}}-a_{l_1}b_{l_2} = \sum_{1\leq l_1 < l_2 \leq k} \det(\begin{bmatrix} a_{l_2} & a_{l_1} \\ b_{l_2} & b_{l_1} \end{bmatrix}) = \sum_{1\leq l_1 < l_2 \leq k} \det(\texttt{v}_{l_2},\texttt{v}_{l_1})\]
\[\sum_{1\leq l_1 < l_2 \leq k} \det(\texttt{v}_{l_2},\texttt{v}_{l_1}) = \sum_{1\leq l_1 \leq k-1} \sum_{l_1+1\leq l_2 \leq k} \det({\texttt{v}_{l_2},\texttt{v}_{l_1}})=\sum_{1\leq l_1 \leq k}\det(\sum_{l_1+1\leq l_2 \leq k} {\texttt{v}_{l_2},\texttt{v}_{l_1}})\]
\[ \sum_{1\leq l_1 \leq k}\det(\sum_{l_1+1\leq l_2 \leq k} {\texttt{v}_{l_2},\texttt{v}_{l_1}}) = \sum_{1\leq l_1 \leq k}\det(\texttt{s}_k-\texttt{s}_{l_1},\texttt{v}_{l_1}) = \sum_{1\leq l_1 \leq k}\det(-\texttt{s}_{l_1},\texttt{v}_{l_1})\]
Shoelace Theorem
\[\sum_{l=1}^{k-1} -\det(\texttt{s}_{l_1-1},\texttt{v}_{l_1}) = 2\text{Area}(\text{Polygon}(\texttt{v}_1,\texttt{v}_2,\cdots,\texttt{v}_k,-\texttt{s}_k)) = 2A\]
Pick Theorem. Consider
\[\text{Polygon} (\texttt{v}_1,\texttt{v}_2,\cdots,\texttt{v}_k,-m\texttt{j},-n\texttt{i})\]
As
\[A = i+\frac{b}{2}-1\]
\[\sum_{1\leq l \leq k} \gcd({a_l,b_l})+n+m = b\]
\[ nm-2A = 2i + \sum_{1\leq l \leq k} \gcd({a_l,b_l}) +n+m-2\]
\[ 2A+ \sum_{1\leq l \leq k}\gcd({a_l,b_l}) = mn-n-m+2-2i\]
Simplify the original equation
\[ f_{n,m}(x) = \sum_{\cdots}(x^2-1)^{k-1}x^{2-2k}x^{mn-n-m+2-2i}\]
Rewrite as
\[ f_{n,m}(x) = x^{mn-n-m+2}\sum_P(1-\frac{1}{x^2})^{k(P)-1}(\frac{1}{x^2})^{i(P)} \]
where
\[P: \text{Polygon}(\texttt{v}_1,\texttt{v}_2,\cdots,\texttt{v}_k,-\texttt{s}_k)\text{ is a convex polygon}\]
By imagining a path along a grid from \((0,0)\) to \((n,m)\).
Consider
\[x^{mn-n-m+2}\sum_P(1-\frac{1}{x^2})^{k(P)-1}(\frac{1}{x^2})^{i(P)}\]
since
\[\forall \frac{a_i}{b_i} < 1\]
there exist a right angle isosceles triangle where all points within cannot be selected as vertices of the convex polygon(hull). There are in total
\[\frac{m(m-1)}{2}\]
of them.
Rewrite equation to
\[x^{mn-n-m+2}\sum_P(1-\frac{1}{x^2})^{v(P)}(\frac{1}{x^2})^{o(P)}(\frac{1}{x^2})^{\frac{m(m-1)}{2}}\]
\[x^{mn-n-m+2-m(m-1)}\sum_P(1-\frac{1}{x^2})^{v(P)}(\frac{1}{x^2})^{o(P)}\]
where
\(v(P)\) = number of vertices of the convex hull/polygon
\(o(P)\) = number of points outside the convex hull/polygon.
*For clarity, if there are points that are colinear, the one that is a "turning point" is the vertex, and the others are "outside" the convex hull.
define
\(i(P)\) = number of points inside the convex hull/polygon
I will now evaluate
\[S=\sum_P(1-\frac{1}{x^2})^{v(P)}(\frac{1}{x^2})^{o(P)} = \sum_P(1-\frac{1}{x^2})^{v(P)}(\frac{1}{x^2})^{o(P)}(1-\frac{1}{x^2}+\frac{1}{x^2})^{i(P)}\]
\[S=\sum_P\sum_{k=0}^{i(P)}\binom{i(P)}{k}(1-\frac{1}{x^2})^{v(P)+k}(\frac{1}{x^2})^{o(P)+i(P)-k}\]
Note
\[i(P)+o(P)+v(P) = \text{const.}\] Consider
\[\binom{i(P)}{k}(1-\frac{1}{x^2})^{v(P)+k}\]
This process means select \(v(P)\) points for vertice, then select \(k\) points interior.
This is equivlent to finding a subset of points of size \(v(P)+k\). And then find its convex hull. As the convex hull for each subset is unique, the mapping is one to one.
Hence
\[S = \sum_{k=0}^{i(P)+o(P)+v(P)} \binom{i(P)+o(P)+v(P)}{k}(1-\frac{1}{x^2})^k(\frac{1}{x^2})^{i(P)+o(P)+v(P)-k}=1\]
So \[ f_{n,m}(x) = x^{mn-n-m+2-m(m-1)}\]
\[ \boxed{f_{n,m}(x) = x^{mn-m^2-n+2}}\]