Problem. Let $N$ be a positive integer. For each permutation $\pi$ of $[N]:=\{1,2,\cdots ,N\}$, let $f(\pi)$ be the number of inversions of $\pi$, and let $g(\pi)$ be $n$ minus the number of cycles of $\pi$. For each $i\in[N]$, $\epsilon_i\in\{0,1,2\}$ is given. Let $S$ denote the set of all permutations $\pi$ of $[N]$ such that for each $i\in[N]$, $p_i>i$ if $\epsilon_i=1$ and $p_i< i$ if $\epsilon_i=2$. Compute $$\sum_{\pi\in S}f(\pi)g(\pi),$$ modulo a fixed positive integer, in $O(N^2)$ time.

Solution. For $n\in\mathbb N$, let $T_n$ be the set of all injective maps with domain and range contained in $[n]$. For $Q\in T_n$, denote $D(Q)=(\text{domain of }Q)$ and $R(Q)=(\text{range of }Q)$. Define $f,g:T_n\rightarrow \mathbb N$ by \begin{align*} f(Q)=&\#\{((i,j),(i',j'))\in Q:i< i',j>j'\}+ \\ &\#\{(i,i')\in[n]^2:i< i',i\notin D(Q),i'\in D(Q)\}+\#\{(j,j')\in[n]^2:j< j',j\notin R(Q),j'\in R(Q)\}. \end{align*}

$$ g(Q)=n-(\text{number of connected components when viewed as a graph on the set } [n] \text{ of vertices}).$$

For $n'\ge n$, $f(Q)$ and $g(Q)$ do not change when $Q$ is interpreted as an element of $T_{n'}$. If $D(Q)=R(Q)=[n]$, $f(Q)$ and $g(Q)$ agree with the functions given in the statement. For a subset $T\subseteq T_n$, we denote $f(T)=\sum_{Q\in T}f(Q)$, $g(T)=\sum_{Q\in T}g(Q)$, and $fg(T)=\sum_{Q\in T}fg(Q)$ where $fg(Q)=f(Q)g(Q)$.

For $0 \le n \le N$ and $k \in \mathbb{Z}$, let $S_{n,k}$ be the set of $Q \in T_n$ such that $|Q| = k$ and

• For any $i \in [n]$ such that $\epsilon_i = 1$, either $i \notin D(Q)$, or $i \in D(Q)$ and $Q(i) > i$.
• For any $i \in [n]$ such that $\epsilon_i = 2$, $i \in D(Q)$ and $Q(i) < i$.

In particular, $S_{N,N} = S$, and we want to compute $fg(S_{N,N})$.

By definition, $|S_{0,0}|=1$, $f(S_{0,0})=g(S_{0,0})=fg(S_{0,0})=0$, and $S_{n,k}=\emptyset$ for $k< 0$. Let $1\le n\le N$ and $0\le k\le n$. We compute the cardinality and $f,g,fg$ values of $S_{n,k}$ in terms of $S_{n-1,k}, S_{n-1,k-1}, S_{n-1,k-2}$. Let $$ X_0=\{Q\cup \{(i,n)\}:Q\in S_{n-1,k-1},i\in[n-1]\setminus D(Q)\}, \ \ X_1=\{Q\cup \{(n,j)\}:Q\in S_{n-1,k-1},j\in [n-1]\setminus R(Q)\}, $$ $$ X_2=\{Q\cup \{(n,n)\}:Q\in S_{n-1,k-1}\}, \ X_3=\{Q\cup \{(i,n),(n,j)\}:Q\in S_{n-1,k-2}, i\in [n-1]\setminus D(Q), j\in [n-1]\setminus R(Q)\}. $$ Clearly $S_{n,k}$ equals the disjoint union $$ S_{n,k}=\begin{cases} S_{n-1,k}\coprod X_0\coprod X_1\coprod X_2\coprod X_3 & \epsilon_i=0\\ S_{n-1,k}\coprod X_0 & \epsilon_i=1\\ X_1\coprod X_3 & \epsilon_i=2 \end{cases}. $$ Since $X_0$ and $X_1$ have the same cardinality and $f,g,fg$ values by symmetry, we need to find formulas for $X_0,X_2,X_3$, which leads to formulas for $S_{n,k}$.

For $Q\in T_{n-1}$ and $i\in [n-1]\setminus D(Q)$, $j\in[n-1]\setminus R(Q)$, let $$ h_Q(i)=\#\{i'\in [n-1]\setminus D(Q):i'< i\}, \ \ k_Q(j)=\#\{j'\in[n-1]\setminus R(Q):j'< j\}. $$ If we sum $h_Q$ (resp. $k_Q$) over all $i\in[n-1]\setminus D(Q)$ (resp. $j\in[n-1]\setminus R(Q)$), each pair $i'< i'$ (resp. $j'< j$) is counted once, so we have the equality $$ \sum_ih_Q(i)=\sum_jk_Q(j)=\binom{n-1-|Q|}{2}. $$ By the definitions of $f$ and $g$, we have $$ f(Q\cup \{(i,n)\})=f(Q)+h_Q(i)+n-k, \ f(Q\cup \{(n,n)\})=f(Q)+2(n-k),$$ $$f(Q\cup \{(i,n),(n,j)\})=f(Q)+h_Q(i)+k_Q(j)+2(n-k)+1, $$ $$ g(Q\cup \{(i,n)\})=g(Q)+1, \ \ g(Q\cup \{(n,n)\})=g(Q), \ \ g(Q\cup \{(i,n),(n,j)\})=g(Q)+2-\delta_{j,\pi(i)} $$ where for each $Q$, $\pi:[n-1]\setminus D(Q)\rightarrow [n-1]\setminus R(Q)$ is the bijection such that $Q^k(\pi(i))=i$ for some $k\in \mathbb N$. Here, $Q^k$ is the map $Q$ composed $k$ times. In other words, starting at $\pi(i)$ and following the graph $([n-1],Q)$ along the directed edges ends at $i\notin D(Q)$, and conversely, $i$ determines $\pi(i)$ by following the graph in reverse direction. In particular, if $i\notin D(Q)\cup R(Q)$, then $\pi(i)=i$.

Considering the number of choices for $i,j$ in each of $X_0,X_2,X_3$, we deduce $$ |X_0|=(n-k)|S_{n-1,k-1}|, \ |X_2|=|S_{n-1,k-1}|, \ |X_3|=(n-k+1)^2|S_{n-1,k-2}|. $$ We compute \begin{align*} f(X_0)&=\sum_{Q}\sum_i(f(Q)+h_Q(i)+n-k)=\sum_Q\left((n-k)f(Q)+\binom{n-k}{2}+(n-k)^2\right)\\ &=(n-k)f(S_{n-1,k-1})+\frac{3(n-k)^2-(n-k)}2 |S_{n-1,k-1}|,\\ f(X_2)&=\sum_{Q}(f(Q)+2(n-k))=f(S_{n-1,k-1})+2(n-k)|S_{n-1,k-1}|,\\ f(X_3)&=\sum_Q\sum _i\sum_j(f(Q)+h_Q(i)+k_Q(j)+2(n-k)+1)\\&=\sum_Q\left((n-k+1)^2f(Q)+2(n-k+1)\binom{n-k+1}{2}+(2(n-k)+1)(n-k+1)^2 \right)\\ &=(n-k+1)^2f(S_{n-1,k-2})+(3(n-k)+1)(n-k+1)^2|S_{n-1,k-2}|. \end{align*} It is relatively easy to compute $$g(X_0)=(n-k)(g(S_{n-1,k-1})+|S_{n-1,k-1}|), \ g(X_2)=g(S_{n-1,k-1}), $$ $$ g(X_3)=(n-k+1)^2g(S_{n-1,k-2})+(n-k+1)(2(n-k)+1)|S_{n-1,k-2}|. $$ Finally, we compute \begin{align*} fg(X_0)&=\sum_Q\sum_i (f(Q)+h_Q(i)+n-k)(g(Q)+1)\\ &=(n-k)(fg(S_{n-1,k-1})+f(S_{n-1,k-1}))+\frac{3(n-k)^2-(n-k)}{2}(g(S_{n-1,k-1})+|S_{n-1,k-1}|),\\ fg(X_2)&=\sum_Q(f(Q)+2(n-k))g(Q)=fg(S_{n-1,k-1})+2(n-k)g(S_{n-1,k-1}),\\ fg(X_3)&=\sum_Q\sum _i\sum_j(f(Q)+h_Q(i)+k_Q(j)+2(n-k)+1)(g(Q)+2-\delta_{j,\pi(i)})\\ &=(n-k+1)^2fg(S_{n-1,k-2})+(n-k+1)(2(n-k)+1)f(S_{n-1,k-2})\\&+(3(n-k)+1)(n-k+1)^2g(S_{n-1,k-2})+(3(n-k)+1)(n-k+1)(2(n-k)+1)|S_{n-1,k-2}|\ \\ &\left(\because\sum_i\sum_j(h_Q(i)+k_Q(j)+2(n-k)+1)\delta_{j,\pi(i)}=(3(n-k)+1)(n-k+1)\right). \end{align*} Since we are computing modulo a fixed positive integer, addition and multiplication take $O(1)$ time. Hence given the cardinality and $f,g,fg$ values for $S_{n-1,k-2},S_{n-1,k-1},S_{n-1,k}$, we can compute them for $S_{n,k}$ in $O(1)$ time. Therefore, we have an algorithm that computes the desired value $fg(S_{N,N})$ in $O(N^2)$ time.