Is there a neater way to solve 2016 AIME ii #13 (and generalize it?) 2016 AIME II #13:

Beatrix is going to place six rooks on a $6 \times 6$ chessboard where both the rows and columns are labeled $1$ to $6$; the rooks are placed so that no two rooks are in the same row or the same column. The $value$ of a square is the sum of its row number and column number. The $score$ of an arrangement of rooks is the least value of any occupied square.The average score over all valid configurations is $\frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.

You can find solutions on the AoPS wiki. My solution was similar to solution $1$. Without the flavortext, I believe the problem is:

Let $(a_1,a_2,a_3,a_4,a_5,a_6)$ and $(b_1,b_2,b_3,b_4,b_5,b_6)$ be random not-necessarily-distinct permutations of $(1,2,3,4,5,6)$. Find the expected value of $\min(a_i+b_i)$ where $1\le i\le 6$.

The solutions all include "bashing" out all possible cases (finding the probability the min is $2$, etc.). Is there a way to do this without "bashing"? Can this be extended, changing $6$ to a general $n$?
 A: You have actually slightly overcomplicated the problem. A simpler version is

Let $(a_1, ..., a_n)$ be a permutation of $(1, ..., n)$, randomly chosen where all permutations have equal probability. Find the expected value of $K = \min\limits_{1 \leq i \leq n} i + a_i$.

where the chessboard is $n \times n$ and there are $n$ rooks being placed. Here, $a_i$ is the column number for the rook placed on row $i$.
In this particular problem, $n = 6$. But we are trying to find a "nice" solution, so let's leave $n$ unspecified.
Suppose $0 \leq j \leq n$. How many permutations are there where $K > j$?
It turns out that the answer is $b_j := (n + 1 - j)^j (n - j)!$. To see this, consider the fact that for $1 \leq i \leq j$, we must pick $a_i$ such that $j - i < a_i \leq n$ (which gives us $n - (j - i) = n + i - j$ options), but we cannot pick any of the $i - 1$ values already picked (so we have a total of $n + 1 - j$ options). So when we pick the first $j$ values of the permutation, there are $(n + 1 - j)^j$ possibilities. To pick the remaining $n - j$ choices, we have no constraints except that we not pick any of the previous $j$ choices, so this gives us $(n - j)!$ choices for the last part regardless of how we picked the first part.
For convenience, extend $b_j = 0$ when $j = n + 1$, since there are $0$ ways to make $K > n + 1$ (this is because $K \leq 1 + a_1 \leq 1 + n$).
We wish to compute $\sum\limits_{j = 1}^{n + 1} j (b_{j - 1} - b_j)$. We see that this is equal to $(\sum\limits_{j = 0}^n b_n) - (n + 1)b_{n + 1} = \sum\limits_{j = 0}^n b_n$.
So we must compute $\sum\limits_{j = 0}^n (n + 1 - j)^j (n - j)!$. Writing $u = n - j$, we can write the sum as $\sum\limits_{u = 0}^n (u + 1)^{n - u} u!$.
I do not see any way to simplify this sum.
So the expected value in question will be $\frac{\sum\limits_{u = 0}^n (u + 1)^{n - u} u!}{n!}$. This is simple enough that we can explicitly calculate the value for $n = 6$.
