n個連續的非零自然數排成一排，其中任何兩個連續的數都不相鄰的排法有多少種？

---

嗯，好問題

這和一個國際象棋棋盤國王的排列問題是一樣的

Hertzsprung"s problem:在n×n的棋盤上每行每列放置1個國王，共n個國王，並使之互相呈和平狀態

如果a(n)是此時所以可能的排列

那麼數列{a(n)}(Hertzsprung"s problem中有a(0)項，即括弧中的1)應該是：

(1,) 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, 831283558, 11661506218, 175203184374, 2806878055610, 47767457130566, 860568917787402, 16362838542699862, 327460573946510746, 6880329406055690790, 151436547414562736234, 3484423186862152966838, ...

應滿足：

If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).

具體的資料只找到了這個：http://oeis.org/A002464

&" dw="700" dh="99" class="origin_image zh-lightbox-thumb lazy" w="700" data-original="https://pic3.zhimg.com/v2-faa9b59c77ff26ce38280bcec4a9ccd5_r.jpg" data-actualsrc="//i1.wp.com/pic3.zhimg.com/50/v2-faa9b59c77ff26ce38280bcec4a9ccd5_hd.jpg">

至於這兩個問題的結果為什麼是一樣的，略作分析：

也以題目中的n=5時為例

那麼有：

5

4

3

2

1

現在，我們將這五個數分別向右移0,1,2,3,4格

如：

&" dw="720" dh="622" class="origin_image zh-lightbox-thumb lazy" w="720" data-original="https://pic4.zhimg.com/v2-00d50540da18fcc7478a024878713b34_r.jpg" data-actualsrc="//i1.wp.com/pic4.zhimg.com/50/v2-00d50540da18fcc7478a024878713b34_hd.jpg">

則得到新的排列

並且當如此（但不僅限如此）平移，下落時：

&" dw="720" dh="235" class="origin_image zh-lightbox-thumb lazy" w="720" data-original="https://pic2.zhimg.com/v2-51ba9c00d4071805f38062a9d65fe231_r.jpg" data-actualsrc="//i1.wp.com/pic2.zhimg.com/50/v2-51ba9c00d4071805f38062a9d65fe231_hd.jpg">

得到滿足的排列

我們發現，每一行只有一個數（根據題目），每一列只有一個數（否則下落後會幾個數重疊並且某幾處沒有數）。那麼這就是國王的放置要求一：每行每列有且僅有一個

那麼我們繼續以此例中的「4」為例

首先，橫縱向不能出現其他數字（用?佔位）

&" dw="720" dh="666" class="origin_image zh-lightbox-thumb lazy" w="720" data-original="https://pic3.zhimg.com/v2-9b1143a28ebf98177841b0031e880e61_r.jpg" data-actualsrc="//i1.wp.com/pic3.zhimg.com/50/v2-9b1143a28ebf98177841b0031e880e61_hd.jpg">

那麼4周圍的8個位置就都不能擺放，就對應了國王位置的要求二：要互相呈和平狀態

另外，若最初不是按

5

4

3

2

1

排列也沒有關係，只需要把佔位的地方移一下，就相當於國王的8個點變了一下而已，不影響最後的解

---

原題地址：http://www.lydsy.com/JudgeOnline/problem.php?id=4321

dp[i][j][0/1]代表前i個數，j對連續整數位置相鄰，i和i-1是否相鄰的狀態數

然後隨便轉移一下

以及oeis：

http://oeis.org/A002464

---

推薦閱讀：