請問各位老師一題，

將1、2、3、4、5、6六個數字按大、小、大、小、大、小的方式(614352)排列有幾種？

20240129_175306.jpg (49.7 KB)

2024-1-30 09:05

我只會土法鍊鋼

[ 本帖最後由 iammark 於 2024-1-30 09:05 編輯 ]

令 an 為 1n 依大、小、大、小... 的方法數(由左至的第奇數個數，比相鄰的數大)

注意到 1n 依小、大、小、大... 的方法數亦為 an

易知 a1=1a2=1a3=2

以 n 的位置來分類方法，有以下

4XXX

XX4X

a4=a3+C23a2C11a1=5

5XXXX

XX5XX

XXXX5

a5=2a4+C24a2C22a2=10+6=16

6XXXXX

XX6XXX

XXXX6X

a6=a5+C25a2C33a3+C45a4C11a1=16+20+25=61

[ 本帖最後由 tsusy 於 2024-1-30 21:32 編輯 ]

此排列稱為交錯排列(Alternating permutation)
數字小，可以慢慢討論，數字一大就無法用高中方法算…

這是有名的安德烈問題(André's problem)，大約1880年左右提出的。
原問題是小大小大…
答案是歐拉數列(Euler Number)，見OEIS: A000111

這個沒有公式，
但可以利用其遞迴式，解微分方程，得到指數生成函數為 sec(x)+tan(x)
是一個很漂亮的結果。

Stanley, 2010年,有寫了一篇Survey，得到它的漸近式為 2n!(2)n+1。

可以搜尋上面這些關鍵字，應該會得到不少說明。

[ 本帖最後由 DavidGuo 於 2024-2-1 21:41 編輯 ]

謝謝老師的回應

謝謝老師精采的解法