条件を満たす場合の性質，必要条件
条件を満たさないマスを悪いマスと呼ぶ． 悪いマスは高々1個．
2つ以上存在すると仮定して，それらのうち異なる2つを\(x,y\ (x \neq y)\) とする． このとき， \begin{align} a && \cdots &&y \\ \vdots && && \vdots \\ x && \cdots && b \end{align} の形になる． よって， \(x > a > y\) かつ \(x < b < y\) となって矛盾．
条件を満たさないマスを悪いマスと呼ぶ． 悪いマスは高々1個．
2つ以上存在すると仮定して，それらのうち異なる2つを\(x,y\ (x \neq y)\) とする． このとき， \begin{align} a && \cdots &&y \\ \vdots && && \vdots \\ x && \cdots && b \end{align} の形になる． よって， \(x > a > y\) かつ \(x < b < y\) となって矛盾．
数え上げ
悪いマスを全探索する代わりに， 悪いマスを含む行と列の選び方を全探索する． その様な行と列に使われる値の集合を \(S \subset N\) とおく． \(S\) の中央の値が，悪いマスの値として一意に定まる． また， \(\vert S \vert = 2N-1\)となり， \(S\) 以外の元の個数は \(N^{2} - (2N-1) = (N-1)^{2}\) ．
よって場合の数は以下の通り．
悪いマスを全探索する代わりに， 悪いマスを含む行と列の選び方を全探索する． その様な行と列に使われる値の集合を \(S \subset N\) とおく． \(S\) の中央の値が，悪いマスの値として一意に定まる． また， \(\vert S \vert = 2N-1\)となり， \(S\) 以外の元の個数は \(N^{2} - (2N-1) = (N-1)^{2}\) ．
よって場合の数は以下の通り．
- 悪いマスの場所: \(N^{2}\)
- \(S\) の取り方: \({}_{N^{2}} C_{2N-1}\)
- \(S\) の内部の並べ方: \(((N-1)!)^{2}\)
- \(S\) の外部の並べ方: \(((N-1)^{2})!\)
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
