關於2022年AMC12一個函數的思考！

五月小講堂

本月的每日一講中

我們(men) 要深入探討一個(ge) 2022 AMC12中的一道問題：

2022 AMC12A P24

^{內(nei) 容介紹✦}

2022年的AMC12A 24考到了這樣一個(ge) 問題：  

這個(ge) 問題本身是非常容易看出答案的，雖然它位於(yu) 24題，但是選項的給法非常巧妙，這也導致我們(men) 忽略了它背後的思考。

Solution 1：

但是這個(ge) 問題還有一種思考，來源於(yu) MAA官方解答：

這就是非常著名的Parking Functions ，最早是由Henry O. Pollak提出的，在本月的問題中，我們(men) 簡單介紹一下這個(ge) function的證明，以及一些後續的發展。

Theorem (Parking Function) 對於(yu) 1,2,…n的直線排列車位，車輛事先想停入。但是如果已經被占用，則它自動停入下一個(ge) 無車的車位。我們(men) 將這個(ge) 先驗的排列稱為(wei) 一個(ge) parking function，如果所有的車子都是可以停入車位的。這樣的parking function 總共有種。

Proof: 我們(men) 增加一個(ge) 車位n+1，並把這些車位排成一個(ge) 圈，注意n+1現在認為(wei) 也可以被用來停車。

注意此時所有的車都可以停入，並且會(hui) 空著一個(ge) 位置。顯然一個(ge) 排列是個(ge) Parking Function，當且僅(jin) 當它的空位是n+1。

  注意，如果使得停入了，則將使得停入了。這意味著對於(yu) 當中隻有一個(ge) 是Parking Function（空出了n+1的位置），故答案為(wei)  熟悉圖論的同學此時一定會(hui) 發現，這個(ge) 問題的結果和上的 Rooted Forest個(ge) 數是一樣的！這裏 rooted forest 實際上是 rooted tree 的無交並，當然後者實際也就是在 tree 上指定一個(ge) root，與(yu) 之對應的概念是 free tree。 Theorem (Cayley) {1,2, … , ?}上的 Rooted Forest 有(? + 1)?-1種。   我們(men) 給出 ?=3 的例子： 有興(xing) 趣的讀者可以想想這個(ge) 定理的證明，它屬於(yu) Sylvester。當然， Parking Functions的應用不止於(yu) 此，它實際上還和無交分拆(Noncrossing partitions)有密切的關(guan) 係，它是指

  Definition Noncrossing Partition 是對於(yu) {1,2, … , ?}的一種分拆 ，使得： 若 ? < ? < ? < ?, 且 ?, ? ∈ , ?, ? ∈ 則 ? = ?.
其中稱為(wei) block。   形象地來看：

當然 Noncrossing Partition 應該是有 Catalan Number個(ge) 的，這裏我們(men) 不多對此結果作注釋。

值得提的是所謂的 Parking Function 是和極大鏈一一對應的，換言之極大鏈恰好有個(ge) 。數列 m 是{1,2,…,n+1}的Noncrossing partition 的極大鏈(maximal chain)，如果 m =

其中， 是一個(ge) {1,2,…,n+1}的 Noncrossing partition，且是通過合並的 block得到的，例如:

就是一種 maximal chain。有興(xing) 趣的讀者可以想想這種一一對應本質上是什麽(me) ？