# Combinatorial characterization of intersecting intervals in the plane

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.

• This could already be interesting if all the $n+n$ points are on a straight line, i.e. a 1-dimensional version of the 2-D problem. It might also be appealing to limit the general location of the points, say anywhere on a circle, etc. – T. Amdeberhan Oct 6 '16 at 22:58
• @T.Amdeberhan: Yes, I agree - I am looking a bit on the case when the points in A are of the form (t,t^2) for t=1,2,...n. There are a few generalizations also that I have in mind, but not come up with a good definition: Find a symmetric polynomial defined in a similar spirit. Find a generalization/construction that detects topology/genus of the underlying surface. – Per Alexandersson Oct 6 '16 at 23:18