這道數學題有哪些解題思路？？

12-03

首先答案形式很有誘惑力。貌似揭露n形式的答案。其實並不是，因為拉丁方陣數量並沒有公式。

n=4的時候。直接先擺好第一行，再擺好第一列。得到4！x 3！。剩下的硬算得到4種情況。再相乘得到答案。

但是當n=5時。同理擺好第一行第一列，得到5！x 4！但是剩下的情況遠遠超出5種。所以這不是通用公式。

甚至更簡單的n=3時答案也只是3！x2！而已。

這題已經有些歷史了。
這種方格叫做拉丁方陣（Latin square）。
並沒有公式。
不過有上下界的公式，不過並不精確。
請自行百度維基百科，最好看英文版的如果能看懂的話，因為會多很多信息，比如一些上下界公式。

我自行感慨一下，你不研究組合數學，永遠不知道人有多無聊，基本上以初中生能理解的數學問題，能想到的數學問題，全部都被研究過了。別說你是書上看到的題，就是你自己偶爾發神經想的題，也大多被人研究過。你找不到只是因為你不知道它網上叫什麼名字而已。題主你這個問題還好了，跟數獨像，一看就是肯定早就被提出來的問題，畢竟很容易被想到。如果你翻我的提問，你會發現我曾經問過這個問題
包含00～99的最短數字串是多長，並且有多少個？

自認已經挺奇葩的了，沒想到還是被研究過了，比較獵奇。現在想研究沒被研究過的東西。你不抽象點不行啊，最好搞點自定義的數學對象才好lol

很有趣的題目，沒做出來，說點思路，拋磚引玉。

我的思路是逐列（行）填充。不失一般性，設第一列為1,2,3...,n-1,n.
隨後往第2、3、4……n列依次填充。填充的要求是：
第k+1列一定是第1~k列每一列的錯排（如果兩種排列的對應元素均不相同，稱為一個錯排）。
某一序列的錯排的數量由錯排公式Dn給出，遞推/容斥原理容易得到。

接下來是一點構造。我是這樣考慮的：把一個序列的所有n！種排列方式構成一個空間，賦予一定的結構，考察這個空間的性質。我想從度量的角度做文章，就要構造一個度量。
這個度量應當滿足如下性質：
1.度量三條基本性質
2.如果兩個元素（兩種排列方式）x、y互為錯排，那麼這二者的度量值應該具有某些特殊性質以方便我們去搞事情。

性質2是比較重要的，直接會影響到問題的解決，所以先看性質2.直觀的來講，假如二者互為錯排，二者或許離得比較遠。那麼取dxy=不相同對應元素的數量。
比如說排列123和132 只有一個元素是對應相同的，有d=2。

dxx=0，dxy大於等於0，dxy=dyx這都是顯然的。
下證：此種d滿足三角不等式。
「相同元素」指某兩種排列中對應相同數字的位置。
設kxy是x、y相同元素的數量，易知dxy+kxy=n
dab+dac&>=dbc
等價於kab+kac&<=kbc+n
假如kab+kac&<=n，則滿足。
若kab+kac&>n，說明ab相同元素與bc相同元素有重疊，重疊了kab+kac-n個，在abc三種排列中這些位置上的數字也都是一樣的。類似於「(b交c)包含(a交b交c)",有kbc&>kab+kac-n.證畢

這個證法表述得有點不...美，用合適的集合論語言說起來會漂亮一些，或者可以直接邏輯推斷出來，先不管了。

那麼我們就獲得了一個度量，xy互為錯排當且僅當dxy=n.這意味著對於元素x，它的Dn個錯排分布在半徑為n的「球」上，且對於任意半徑k的球面上分布著C（n，k）*Dk個元素。

這樣，一個排列問題就化成了一個幾何問題，比如n=4的時候就是在這個空間里找有多少個正四面體。

比較困難的是這種度量空間長得比較奇怪，度量是離散的，且有上限n，這和歐式空間還不太一樣，長成什麼樣還想不出來。。。太抽象了orz。
要探究一下這個空間的幾何性質，這個是接下來解決問題的關鍵。

以下屬於瞎想：
從歐式幾何來看，球面上最多能畫多少個邊長為r的正三角形？或許這是一個n的上界？
還是說這種空間和歐式空間不太一樣，n並沒有上界，所有的n都可以？

目前就先想到這裡，想出來再繼續。。。

度量d的構造方法不止一種，還可以取dxy=x到y的最少置換次數，容易驗證三角不等式。這樣的話x的錯排會分布在[(1+n)/2]到n-1之間的球殼中，接下來我就不知道該怎麼辦了。。。

你把圖片橫過來再發，不行嗎？

你的字挺漂亮。。。。。

從4x4開始說吧。

首先，我們先把第一行擺好，有4A4種擺法，也就是4!種擺法；接著，我們把第一列擺好，有3A3種擺法，現在已經是4x32x22x12了；下面，還剩九個格子，我隨便拿其中一情況說一下。

=============================假裝是條分割線=============================

假設，出現了這種情況：
1 2 3 4
2 ? ? ?
3 ? ? ?
4 ? ? ?
如果我把棋盤坐標化，把左上角的格子記作（1,1），右下角的為（4,4），那麼，對於格子（2,2）有三種選擇；1、3、4。我先任選一種，比如3，（2,3）可以是1或者4，但是考慮到這一行最後一個元素，只能是4，（2,2）為4時同理。這樣，就有兩種了。（2,2）取1時，還有一種情況。

再選一種情況，討論剩下的六個格子：
1 2 3 4
2 3 4 1
3 ? ? ?
4 ? ? ?
顯然，（3,2）只能是4，（4，2）就是1，剩下四格也就確定了，（2,2）位4時同理。

再來看一下，（2，2）取1會怎樣？
1 2 3 4
2 1 4 3
3 ? ? ?
4 ? ? ?
顯然，第二列確定了，現在棋盤是這樣的：
1 2 3 4
2 1 4 3
3 4 ? ?
4 3 ? ?
最後四個，我可以在主對角線上放1，也可以放2，兩種情況。

綜上，在已有的4x32x22x12的基礎上又要乘上一個4，答案可知。

=============================新的分割線================================

下面，題主還問了nxn的情況，我認為可以用類推的方法，假設在nxn的棋盤中放棋子的情況有f(n)種，得出f(n+1)和f(n)的關係即可（應該是f(n+1)=(n+1)2f(n)，可以考慮用數學歸納法），有時間我再證吧，先睡了。。。快一點了orz

PS：大家都提到了八皇后問題，我感覺這個（從某種形式上）算是它的刪減版（不考慮對角線的棋子）。所以說，這一題還有另一種解法：先擺好一種棋子，然後擺另一種，然後另一種。但是，這樣很大可能會出現剩下的方格無法形成正方形的情況，導致問題難度提升，不建議這麼解。不過，希望有學計算機，並且學過相關演算法的學長來答一下這個問題，趁機學習一波八皇后，回溯法還沒怎麼看呢0.0

-------17.1.16
看到了 Lancewu的答案，算了一下，5×5的時候已經遠遠超過了(5!)2，所以沒有規律可循，老師選4x4也是下了功夫的~

我們可以通過算出有多少種基本排法（數字排序的總數），然後通過行與列的變換來求得總變法

行與列的順序可以隨意調整，因為行與列都是滿足含有「1,2,3,4」的條件的整體
行與行之間通過相互變換有4*3*2*1=24種變法
列與列之間通過相互變換有4*3*2*1=24種變法

那麼問題的關鍵就是行(列)中的數字排序有多少種了
很明顯有4*3*2*1=24種變法

但是呢，列與列的變換的本質就是行中數字的變換，即數字排序的和列變法重複了
所以一共有24*24=576種變法

為什麼通過列變法(數字排序)和行變法可以覆蓋所有可能情況？因為每一行(列)都含有1,2,3,4，行變法和列變法(數字排序)只是改變它們的順序而已

這個應該是越往後推越難吧，不過小範圍還是有規律可循的。

為了更好的表達我的方法，我們不妨先將範圍縮小到3×3：

如上圖，用組合數來表示左上角的數字，其意義表示「在數字123三個數字中，抽取一個數字放入該位置的放法種數」，在固定了最左上角的後分別沿橫排和縱排表示剩餘的外圍數字，因為同排不重複所以分別是兩種、一種。在固定外圍了外圍的數字後，內部的四個數字便都固定且對應有唯一放法，所以都是C11。
最後將所有的組合數相乘，便是在3×3方格下的所有情況，即1×2×3×2×1×1×1×1×1＝12種。

那麼對於4×4的方格用同樣的方法用組合數先表示左上角的數字，然後推出剩餘的數字，如圖：

這裡需要注意的是，並非除外圍的數字剩餘的都是C11！！在4×4中，第二排的第二個數字就應該用C41表示。
所以將所有的組合數相乘：4×4×3×3×2×2×1×1×1×1×1×1×1×1×1×1（汗）就是在4×4方格下所有的可能性了。

……………………1.16更新……………………
綜合一下@一隻臘雞的答案，原題主的答案格式應該是（n！）2，然而3×3的情況則是小於(3!)2，而5×5的情況也是遠大於（5!）2。所以題主給的答案格式並不具備n×n情況的規律性。

這不是八皇后問題的變形嗎？你們老師看來是讓你們學習計算機的節奏【手動微笑】

正餐

抽取的組合有以下幾種：

組合1：

ABCD

BADC

CDAB

DCBA

組合2：

ABCD

BADC

CDBA

DCAB

組合3：

ABCD

BCDA

CDAB

DABC

組合4：

ABCD

BADC

CDBA

DCAB

答案：

4！*3！*4=（4!）^2

字體不錯

如果這個四乘四方陣按照題目要求填數，那麼其中任意一種數字按照每行每列不重複填寫那麼格局就確定了，不存在任何一種填法有一個數字的位置不變而其他三個數字位置不同。比如
1 * * *
* * 1 *
* 1 * *
* * * 1
在1的位置確定之後，其他數字位置就確定了

所以只要考慮1的填法就可以了：第一個1有4*4個位置可以放；第二個1排除第一個1所在行列，剩3*3個位置；第三個剩2*2個位置；最後一個只有1*1個位置

所以是4^2 * 3^2 * 2^2 * 1^2……

我覺得可以使用容斥原理來進行解答。。。晚點再具體寫出來，只是有了初步的想法。。至於題主說的n階的情況我覺得表達式是存在的，但已不是初等表達式，要使用累加和累乘。

討論n=4好了再往上我也不會了
先確定第一行二三四行以行為整體去排序總可以得到下面這樣一個4*4方格
a b c d
? a ? ?
? ? a ?
? ? ? a
這個我只會硬填只有四種
然後後三行以一行為整體去排序 3*2*1=6種
然後1234代abcd 4*3*2*1
總結起來就是 4*4*3*3*2*2*1*1了
感覺我的回答比起大神很小兒科我跑了