Number of $n^2\times n^2$ permutation matrices with a 1 in each $n\times n$ subgrid I found the following question in a paper I was trying to solve:
The following figure shows a $3^2 \times 3^2$ grid divided into $3^2$ subgrids of size $3 \times 3$. This grid has $81$ cells, $9$ in each subgrid.

Now consider an $n^2 \times n^2$ grid divided into $n^2$ subgrids of size $n \times n$. Find the number of ways in which you can select $n^2$ cells from this grid such that there is exactly one cell coming from each subgrid, one from each row and one from each column.
My try:
Since we have $n^2$ rows, $n^2$ columns and $n^2$ subgrids in total, we have to choose one and only one cell from each of them. Let's choose them one at a time. We can choose the first cell in $n^4$ many ways. Then, we'll have to avoid that subgrid, that column and that row that we've chosen the first one from when choosing the second cell. So, we have $n^4-n^2-2n(n-1)$ choices. We can continue this to get the total number of possible ways. But, I think there's a hole. Say, we've chosen the first cell from the subgrid of the up-left corner and the second from the subgrid just right to it so that it doesn't violate any rules. Then, when finding the number of ways we can choose the third cell, we would have substracted some of the cells twice. I think you get it. Please, if anyone can help me solving this problem, it'd be greatly appreciated.
 A: Well, in a $2^2 \times 2^2$ grid there are are 4 choices for the top left sub grid, then as the representative for the top right subgrid can't be in the same row, there are 2 choices.  As the bottom left rep can't be in the same column as the top rep the there are 2 choices.  There is only one choice left for the bottom right sub grid.
In total there are 4*2*2*1 = 16 options.  Or $[2*2][(2 - 1)2]\times[2*(2-1)][(2-1)(2-1)]$ or in general $\prod_{i=1}^n\prod_{k=1}^n ik$.
This is the same argrument in the top row of sub grids there $n^2$ choices for the first subgrid.  $(n-1)n$ for the second and so on.  This is $\prod_{k=1}^n n*k$.  For the second to top row (n-1 from the bottom) of of subgrids there are $n(n-1)$ choices for the first subgrid, $(n-1)(n -1)$ for the second and so on.  This is $\prod_{k=1}^n (n-1)k$.  For all the lth row  of sub grids there are $n(n-l)$ choices for the first subgrid, $(n -1)(n -l)$ for the second and so on.  This is $\prod_{k=1}^n (n -l)k$.  The total product for all rows of subgrids is  $\prod_{i=1}^n\prod_{k=1}^n ik$.
====
Hmmm, when I first posted I really should have continued:
$\prod_{i=1}^n(\prod_{k=1}^n ik)=$
$\prod_{i=1}^n(i^n n!)=$
$(n!)^n (n!^n) = n!^{2n}$
So for a $2^2 \times 2^2$ grid it is $(2!)^{2*2} = 2^4 =16$.
For the $3^2 \times 3^2$ grid it is $3!^{2*3} = 6^6 = 46,656$.  
(Which I figure should be $(9*6*3)*(6*4*2)*(3*2*1) = (3^4*2)(3*2^4)(3*2) = 3^6*2^6 = 6^6$.  Yep, seems to fit.)
I imagine 16 x 16 will be a monster!  $(4!)^{2*4} = 24^8 = 110,075,314,176.$  Wow!
By hand it is $(16*12*8*4)(12*9*6*3)(8*6*4*2)(4*3*2*1)=(4^4*4!)(3^4*4!)(2^4*4!)(4!) = (4!)^4(4!)^4 = 4!^{2*4}$ which.. yeah...
A: Using the counting system outlined in the comments, we can associate to each subgrid a positive integer: the number of choices in that subgrid. It's fairly clear that the number is invariant of the exact method of getting to that subgrid: however you do it, subgrid $(i,j)$ (in the usual matrix suffix notation) has associated with it $(n+1-i)(n+1-j)$ choices. Now the matrices go as follows:
\begin{eqnarray*}
n=1 &\mapsto& \begin{pmatrix}1\end{pmatrix}\\
n=2 &\mapsto& \begin{pmatrix}4&2\\2&1\end{pmatrix}\\
n=3 &\mapsto& \begin{pmatrix}9&6&3\\6&4&2\\3&2&1\end{pmatrix}\\
&\vdots&\\
n=k&\mapsto&
\begin{pmatrix}
k^{2} & k(k-1) & k(k-2) & \ldots & 2k & k\\
k(k-1) & (k-1)^{2} & (k-1)(k-2) & \ldots & 2(k-1) & k-1\\
k(k-2) & (k-1)(k-2) & (k-2)^{2} & \ldots & 2(k-2) & k-2\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
2k & 2(k-1) & 2(k-2) & \ldots & 4 & 2\\
k & k-1 & k-2 & \ldots & 2 & 1
\end{pmatrix}\\
&\vdots&
\end{eqnarray*}
For each $n$, the answer to the problem is the product of all the entries in the corresponding matrix; denote each of these numbers by $P_{n}$. Now since each matrix contains the preceding matrix as a "submatrix", it is clear that we can find a recursive formula: in particular, some thought gives
\begin{eqnarray*}
P_{n} & = & P_{n-1}n^{2}\prod_{i=1}^{n-1}(in)^{2}\\
& = & P_{n-1}n^{2n}[(n-1)!]^{2},
\end{eqnarray*}
with the initial condition $P_{1}=1$.
Now for each $n\in\mathbb{N}$ let $f(n) = (n!)^{2n}$. Clearly $P_{1}=f(1)$. Further, suppose that, for some $n\in\mathbb{N}$, we know that $P_{n-1} = f(n-1)$; then we have
\begin{eqnarray*}
P_{n} & = & P_{n-1}n^{2n}[(n-1)!]^{2}\\
& = & [(n-1)!]^{2(n-1)}n^{2n}[(n-1)!]^{2}\\
& = & (n!)^{2n}\\
& = & f(n).
\end{eqnarray*}
By induction, $P_{n} = (n!)^{2n}$ for all $n\in\mathbb{N}$.
A: I believe I've come upon a solution. Just as @WillR suggested, who showed me the right approach to it, I'm posting this as an answer. Please feel free to notify me about flaws of logic if there are any. So, here it goes:
Let's start by choosing a cell from the top-left subgrid. As we have to select cells from each subgrids, I don't think this approach would affect the final outcome. We have $n^2$ choices in choosing the first cell then. Now, we move towards the right subgrid. This time, we'll have to keep in mind that one of the rows is used. So, we have $n(n-1)$ choices left. If we continue this way, the total number of ways in which we can select $n$ cells from the topmost row is $$n^2 \cdot n(n-1) \cdot \cdot \cdot n=n^n \cdot n!$$
Now, we move to the second row from the top. Now, we don't have to worry about the used rows anymore, only the used columns. So, when choosing the first one from here, we have $n(n-1)$ choices. When we move to the second subgrid, we'll have to avoid a row, but that reduces the number of choices by $(n-1)$, not $n$. Because, the row and column we have to avoid has a common cell. Continuing this way, in case of the second row, we have a total of $(n-1)^n \cdot n!$ choices.
Continuing this way, number of choices for the $r$'th row would be $(n-r+1)^n \cdot n!$. As the choices are independent, we can multiply them to get the total number of choices. That'd be: $$\prod_{r=1}^n{n!^n \cdot (n-r+1)^n} = n!^n \cdot \prod_{r=1}^nr^n=n!^n \cdot n!^n ={n!}^{2n}$$
