Consider $n$ points $A=\{A_1,\dotsc,A_n\}$, and another set of points, $B=\{B_1,\dotsc,B_n\}$ in the plane. We can assume they are all disjoint.
For each permutation $\pi$, consider the collection of line segments joining $A_i$ with $B_{\pi(i)}$, and count the total number of intersections. Call this number $int_{AB}(\pi)$, and define the polynomial $$ P_{AB}(q) = \sum_{\pi \in S_n} q^{int_{AB}(\pi)}. $$ Clearly, $P_{AB}(1)=n!$ and all coefficients are non-negative. It is an easy exercise to show that one can choose $A$ and $B$, such that $P_{AB}(q)=[n]_q!$.
Now, considering all possible choices of $A$ and $B$, there are only a finite set such polynomials. This is clear since there are only a finite number of polynomials with non-negative integer coefficients, with bounded coefficient sum.
How many polynomials can be constructed using two sets of $n$ points?
Can we characterize this set of polynomials combinatorially? That is, find a discrete set of objects equinumerous with the polynomials obtainable from $n+n$ points, plus a statistic on these objects, that generate these polynomials.
EDIT: It is probably easier to characterize cases where we keep track of all intersections. That is, $$ P_{AB}(z) = \sum_{\pi \in S_n} \prod_{i,j} z_{ij}^{int_{AB}(\pi,i,j)} . $$ where $int_{AB}(\pi,i,j)=1$ if $A_i$ intersect $B_{\pi(j)}$ and 0 otherwise. Then putting all $z_{ij}=q$, we recover the polynomial above.
