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.

• Why not consider restricting your first choice to a particular $n\times n$ subgrid? Then consider each next choice going along the rows and the columns in a systematic way. I don't think this affects the final outcome: you should still be counting all the possibilities, and other counting processes probably boil down to rotating the board or permuting the subgrids. It might help to consider the $n=2$ and $n=3$ cases first. – Will R Dec 3 '15 at 7:18
• @WillR Well... Tell me if I'm wrong... What you're trying to say is that first I should select the first cell from, say, the up-left subgrid. Then, I carry along the row and repeat the same process for all the columns. What confuses me is how am I supposed to make sure that neither a row nor a column is repeated? – SinTan1729 Dec 3 '15 at 7:23
• You can factor that into your calculation. Take $n=3$, for simplicity, since you already have the diagram. If your first choice is the little square in the very top-left, and you know you're going to make your next choice in the middle-top subgrid, then how many choices do you have? You have to avoid the top row, but you can choose any other little square, so you have $9-3=6$ choices. Same goes for the left-middle subgrid. Now for the top-right subgrid, you have to avoid the top and middle row, leaving you $3$ choices; and so on. In all, $9\cdot6\cdot6\cdot3\cdot3\cdot4\cdot2\cdot2\cdot1$? – Will R Dec 3 '15 at 7:35
• I'd like to clarify before this gets too serious: I don't have an awful lot of experience with combinatorial problems like this, so please consider what I'm saying with a very skeptical eye. – Will R Dec 3 '15 at 7:42
• @WillR No. I think it'd work. I'll try and finish the problem. I believe it'll work. – SinTan1729 Dec 3 '15 at 7:46

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...

• I believe it coincides with the answer I came up with myself. – SinTan1729 Dec 3 '15 at 9:18
• I think so too. – fleablood Dec 3 '15 at 9:30
• Just came with a result similar as you, generalising the product I got stuck into. – Cloverr Dec 3 '15 at 9:36
• I think, continuing this would give us the possible number of Sudoku puzzles in the board. If we continue this for all the numbers (let's just assume we have a $n^2+1$ base number system). – SinTan1729 Dec 3 '15 at 10:01
• For soduku we'd need a way of anticipating and ruling out impossible contradictions. And apparently many people have worked on this math. – fleablood Dec 3 '15 at 18:34

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}$.

• Whoa! This is some serious stuff! – SinTan1729 Dec 3 '15 at 10:43
• I decided to post this as a separate answer because, for me, matrices are almost inherently visual, so their implementation allows us some clearer insights. For example, without writing out the matrix, it's not immediately obvious that the recursive relationship holds between each of the special cases; once you write out the matrix, you can literally just write down the relationship, no further fancy tricks required. – Will R Dec 3 '15 at 10:47
• Yeah... And I believe it's a much more general approach... – SinTan1729 Dec 3 '15 at 10:49
• I believe the first step would be divided by $n^2$. – SinTan1729 Dec 3 '15 at 10:53
• @SayantanSantra: Ah, I see what you mean; I'll edit that. The error obviously hasn't carried through at all. – Will R Dec 3 '15 at 11:07

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}$$

• I disagree with your calculation on the top row: it shouldn't be $n\cdot n!$. In particular, take $n=3$: by counting, we get $9\cdot 6\cdot 3=162\neq18=3\cdot3!$. – Will R Dec 3 '15 at 8:24
• @WillR Sorry... My bad... I'll just rectify the answer... – SinTan1729 Dec 3 '15 at 8:26
• No need to apologize. It might be worthwhile to consider the following: you have a grid of $n\times n$ subgrids. In each subgrid, you get a certain number of choices. Consider the choices as entries in an $n\times n$ matrix; for example, when $n=3$, this gives $$\begin{pmatrix}9&6&3\\6&4&2\\3&2&1\end{pmatrix}.$$ Now the total number of choices for that value of $n$ is the product of all the entries in the matrix. Write out the matrices for $n=1,2,3,4$; do you notice a pattern? – Will R Dec 3 '15 at 8:30
• Yes, I agree with your answer now, and I think I have a fairly autonomous argument using a recursive formula (derived from the matrices - let $P_{n}$ be the product of the entries of the $n\times n$ matrix, then $P_{n}=P_{n-1}\cdot n^{2n}\cdot[(n-1)!]^{2}$), and your answer satisfies the formula and has the correct initial condition. – Will R Dec 3 '15 at 8:56
• Happy to help! Always remember to check with small numbers: it's frequently easy, and it's even more frequently helpful. – Will R Dec 3 '15 at 9:01