Re: [中學] 排列組合 (一路領先的應用)

[TassTW (塔矢)]

※ 引述《justin0602 (justin)》之銘言：
: http://picmoe.net/d.php?id=1355251595684
: 1.我不清楚為什麼這題目可以聯想這麼做  這樣有一對一的對應?
:   一種捷徑方式對應一種滿足題意的情況
: 2.請問又為什麼不能通過PQRST (這問題好像也包含在問題1裡面)
: 3.那走捷徑 不能通過 PQRST
:   請問大家為什麼要像題目這樣做???
:   扣掉不滿足的走法 為什麼用虛線那些路來算
:   虛線又是什麼東西??? 無中生有出來的
:  (如果不用這特殊做法 角註累加法就沒辦法這樣推廣到一般的情況)
:   但我又看不懂這特殊作法
1.
寫解答的人只知道一半, 蠻可惜的,
他給的那個數字, 化簡以後是 (2n 取 n)/(n+1)
這個數字是組合數學中的王者 Catalan number
http://en.wikipedia.org/wiki/Catalan_number

Catalan number 有幾十種有意義的模型,
除了 wiki 以外可以看 OEIS
http://oeis.org/A000108
而原題的 "standard Young tableaux of shape (n,n) 總數"
和解答中的 "Dyck paths of length 2n 總數",
都是有名的例子

為什麼能想到, 有可能是先試試簡單的例子:
n=1 => 1 種
n=2 => 2 種
n=3 => 5 種

" 啊 他是 Catalan number "

也有可能是在列舉可能的方法時,
發現如果要滿足 "右>左", 每次填大一號時一定只有兩個位置可以填
就能一一對應到向右或向上走

2.
此時需求是 "上>下",
所以代表說每一步上排格子數一定不能大於下排
也就是走 Dyck path 時不能越過對角線

3.
特殊作法的詳細說明可以看 wiki

4.
另外, 這個數字也有表現理論的意義,
我們知道對於對稱群 Sn 來說, 所有的 simple modules 和 partitions of n 一一對應,
(他們被稱為 Specht module) 也就是和所有 Young tableaux 一一對應,

Specht module 的維度可以被 hook formula 給出,
而在這個 2*n 方格, 也就是 Young tableau of shape (n,n) 的情況下,

hook formula 告訴我們維度是

(2n)! / Π 每個格子的 hook length

hook length 就是該格子向右向下看有多少其他格子再 +1,
就是

n+1  n  n-1 ... 2
 n  n-1 n-2 ... 1

所以維度就是 (2n)!/(n+1)!/n! = (2n 取 n)/(n+1),
Catalan 數! 又是你!

--
在馬橋，與「他」近意的詞還有「渠」。
區別僅在於「他」是遠處的人，相當於那個他；  我想找的是他，但只能找到渠。
「渠」是眼前的人，近處的人，相當於這個他。  我不能不逃離渠，又沒有辦法忘記他。

　　　　馬橋語言明智地區分他與渠，指示了遠在和近在的巨大差別。
　　　指示了事實與描述的巨大差別，局外描述與現場事實的巨大差別。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 137.54.11.82
推 WINDHEAD    :他還跟 semicircle distribution的moment有關XD
推 hcsoso      :前幾天在分析 random walks on trees 時它也有出現..
→ TassTW      :樓上那個和 expander family 有關嗎?
※ 編輯: TassTW          來自: 76.104.25.4          (12/12 11:16)
推 microball   :推!! 又學到一個東西
→ TassTW      :一二樓要不要寫一下 catalan number 在你們的狀況
→ TassTW      :是怎麼有關的啊
推 WINDHEAD    :那個要問隨機矩陣的專家比較準  我不懂XD