Generating function for lattice paths making aribitrary (i,j)-up-right move in one step and fitting rectangular (m,n)?

Question

There is the following beautiful formula (see Qiaochu Yuan excellent blog):

$$ \sum_{\lambda \in Young~diagrams~fitting~rectangle~m~n} q^{Box~count(="area~under~the~curve")~of~\lambda} = \binom{n+m}{n}_q $$

Conceptually it gives count of $F_q$ points of the Grassmanian via the summation over Schubert cells (left hand side) and via linear algebra (right hand side). Such formulas generalzies to partial flag varieties and simple Lie groups. Setting q=1 we get: number of such diagrams = binomial coefficient - which is rather obvious and it is suprising that we get generation function so easily - just change from binomial to q-binomial coefficient - yet another $F_{un}$-miracle.

Young diagram can be seen as special lattice paths - just those moving up-1 or right-1 - North-East lattice paths and box count is the same as the "area under the curve"

Question: What is known about count/generating function for lattice paths going from the left-down corner to the right-top corner of the rectangular (m,n) and that can make arbitrary (i,j)-move in one step ? (Generating function should be considered as above - $q^{"area~under~ the~ curve"} $ ).

Examples of paths and areas under them.

From motivation given below it seems to me that paths making e.g. step (2,2) or (1,1)+(1,1) should be considered as different paths.

Motivation: Such paths appears e.g. in quite different field - statistics/machine learning. The path is called "ROC"-curve (receiver operatator characteristic) and "area under curve" (AUC) characterizes the quality of the "predictor".
That is the most commonly used measure of quality for machine learning tasks.

The case of Young diagram (or NE-path) corresponds to the situation where all values of "predictor" are distinct, while in general there can be repeated values of the predictor and one arrives to (i,j)-moves.

The light-red curve corresponds:

1 0 1 1 0 0 0 here 1=up, 0=right
6 5 4 3 3 2 1 here are values of the "predictor" 

The green curve corresponds:

1 0 1 1 0 0 0 here 1=up, 0=right
2 2 2 1 1 1 1 here are values of the "predictor" 

PS

The best source (known to me) which explains subtle details on AUC-ROC is Alexander Dyakonov's blog (the case of coincident values of the "predictor" commonly not exposed well).

PS

From the $F_1$-perspective counting such objects may correspond to something related to Lie algebra of $S_n$ whatever it be.

Answer 1

Let $\mathscr{L}(m,n)$ be the set of paths $p$ in the $m\times n$ box, $A$ the area function, and let $\oplus\colon \mathscr{L}(m_1,n_1)\times \mathscr{L}(m_2,n_2)\to \mathscr{L}(m_1+m_2,n_1+n_2)$ denote concatenation of paths.

Observe that for $(m,n)\not=(0,0)$, we have $\mathscr{L}(m,n)=\sqcup_{(i,j)\not=(0,0)}(i,j)\oplus\mathscr{L}(m-i,n-j)$, because each lattice path decomposes as a first non-zero step, followed by a lattice path in the smaller box beyond it. We also have $A((i,j)\oplus p)=\frac{ij}{2}+j(m-i)+A(p)=j(m-\frac{i}{2})+A(p)$, and more generally $A(p\oplus q)=A(p)+A(q)+n_1m_2$.

We will use the notation $(m,n)\gneq(i,j)$ to mean $m\geq i$, $n\geq j$, and $(m,n)\not=(i,j)$. Sometimes $0=(0,0)$.

Let $L(x,y,q)=\sum_{m,n\geq0}\sum_{p\in \mathscr{L}(m,n)}q^{A(p)}x^my^n$. Then

$$L(x,y,q)=1+\sum_{(m,n)\gneq0}\left(\sum_{0\neq(i,j)\leq (m,n)}\left(\sum_{p\in \mathscr{L}(m-i,n-j)}q^{A((i,j)\oplus p)}\right)\right)x^my^n$$

$$=1+\sum_{(m,n)\gneq0}\left(\sum_{0\neq(i,j)\leq (m,n)}\left(\sum_{p\in \mathscr{L}(m-i,n-j)}q^{j(m-\frac{i}{2})+A(p)}\right)\right)x^my^n$$

$$=1+\sum_{(m,n)\gneq0}\left(\sum_{0\neq(i,j)\leq (m,n)}q^{j(m-\frac{i}{2})}x^iy^j\sum_{p\in \mathscr{L}(m-i,n-j)}q^{A(p)}x^{m-i}y^{n-j}\right)$$

$$=1+\sum_{0\lneq (i,j)\leq (m,n)}\left(q^{j(m-\frac{i}{2})}x^iy^j\sum_{p\in \mathscr{L}(m-i,n-j)}q^{A(p)}x^{m-i}y^{n-j}\right)$$

$$=1+\sum_{(i,j)\gneq0}\left(\sum_{(m,n)\geq (i,j)}q^{j(m-\frac{i}{2})}x^iy^j\sum_{p\in \mathscr{L}(m-i,n-j)}q^{A(p)}x^{m-i}y^{n-j}\right)$$

Setting $m'=m-i$ and $n'=n-j$, we have

$$=1+\sum_{(i,j)\gneq0}\left(\sum_{(m',n')\geq (0,0)}q^{j(m'+\frac{i}{2})}x^iy^j\sum_{p\in \mathscr{L}(m',n')}q^{A(p)}x^{m'}y^{n'}\right)$$

$$=1+\sum_{(i,j)\gneq0}\left(x^iy^jq^{\frac{ij}{2}}\sum_{(m',n')\geq (0,0)}q^{jm'}\sum_{p\in \mathscr{L}(m',n')}q^{A(p)}x^{m'}y^{n'}\right)$$

$$=1+\sum_{(i,j)\gneq0}\left(x^iy^jq^{\frac{ij}{2}}\sum_{(m',n')\geq (0,0)}\sum_{p\in \mathscr{L}(m',n')}q^{A(p)}(xq^j)^{m'}y^{n'}\right)$$

$$=1+\sum_{(i,j)\gneq0}\left(x^iy^jq^{\frac{ij}{2}}L(xq^j,y,q)\right)$$

$$=1-L(x,y,q)+\sum_{i,j\geq0}\left(x^iy^jq^{\frac{ij}{2}}L(xq^j,y,q)\right)$$

We therefore obtain $$L(x,y,q)=\frac{1}{2}\left(1+\sum_{i,j\geq0} x^iy^jq^{\frac{ij}{2}}L(xq^j,y,q)\right)$$

$$=\frac{1}{2}\left(1+\frac{1}{(1-xq^{\frac{1}{2}})}\sum_{j\geq0} (yq^{\frac{1}{2}})^jL(xq^j,y,q)\right)$$

$$=\frac{1-xq^{\frac{1}{2}}}{1-2xq^{\frac{1}{2}}}\left(1+\frac{1}{(1-xq^{\frac{1}{2}})}\sum_{j\geq1} (yq^{\frac{1}{2}})^jL(xq^j,y,q)\right)$$

Notice that for $q=1$, we obtain $L(x,y,1)=\frac{1-x-y+xy}{1-2x-2y+2xy}$

---

This is as far as I shall tread. I admit I haven't done much other than formal power series manipulation.

I unfortunately don't know of an interpretation of this along the lines of Qiaochu's blog post, but would be quite interested in such a thing.