2014年5月27日

作者/游森棚(任教臺灣師範大學數學系)

首先要跟讀者鄭重道歉的是,兩個月前的專欄文章〈塗塗抹抹〉裡,最後一欄關於染色多項式的對數凹猜想,在2011年已經被數學家Seymour找到一個反例反證了,也就是說,對數凹的猜想不成立。不僅如此,後續還有很多新的發展,因此要謝謝直接來信或透過編輯通知我的三位讀者。我一方面慚愧學藝不精,一方面也很高興這個專欄(或《科學月刊》)是真的有人在關心的。以後一定盡量不要犯這樣的錯誤。

最近讀了幾篇論文,都和「蛇」有關——數學上的蛇,不是生物上的蛇。問題的起點很有意思,下筆跟讀者分享才赫然發現蛇年可惜剛剛過去。但如果要應景, 就要再等十一年,所以還是寫在這裡。

我們都知道1、2、3,……,n 的排列有n!個,但是每個排列的「形狀」卻是很不一樣的。所謂形狀即由左至右讀排列數字「往下變小」或「往上變大」的走勢。比如1234567是一路往上,7654321是一路往下,7123465 是「下上上上上下」。 而5142736是很特別的「下上下上下上」,如圖。
好,如果規定形狀要像最後一例一樣「下上下上下上下上……」,這樣長度 n = 3, 有兩個:312、213; 長度 n = 4 有五個:4231、3241、4132、3142、2143。

讀者可以暫停試試看列出長度 n = 5 的16 個。那,長度為 n 時有多少個呢?

這樣的排列叫做交錯排列(alternating permutations)。令 En 是長度為 n 的排列的總數,寫個程式跑一下,可以得到最初的數據{En}n≥0=1, 1, 1, 2, 5, 16, 61, 272, ............【更詳細的內容,請參閱第534期科學月刊】

沒有留言: