Re: [中學] 排列組合，答案只有42但不好做
※ 引述《MathWang (5000+)》之銘言：
: 一2휵矩陣(2列5行)
: 不重複填入1~10
: 規定右比左大，上比下大
: 請問有幾種不同可能?
: 答案42，我花了一番功夫才做出
: 但若題目擴張成2莋就沒有把握了
: 請高手賜教!!
1.
這種填數字的矩陣叫作 Young tableaux,
規定 2 * 5, 就是要他的 shape 是 (5,5)
數字規定右比左大，上比下大的叫作 standard Young tablueax,
standard Young tableaux 在表現理論當中非常重要,
他的總數有公式可算, 就是 hook length formula
https://en.wikipedia.org/wiki/Hook_length_formula
在你的例子中, hook lengths 是
6 5 4 3 2
5 4 3 2 1
所以總數是 10! 除以這些數, 等於 42
2 * n 的情況, 是 (2n)!/n!/(n+1)! = {2n choose n}/(n+1) = Catalan number
2.
在 shape (n,n) 的情況下, 也有初等的組合作法啦
就是找一個 bijection 說他是 Catalan number
比方說 可以由從小到大填數字所在的 row 來造出一個 Dyck path,
又是一種對應到 Catalan 數的結構, 詳見 https://goo.gl/QXCHlE
--
「我們愛星星至深無懼於黑暗。」
"We have loved the stars too fondly to be fearful of the night."
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.206.183.194
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1444155176.A.3A8.html
※ 編輯: TassTW (71.206.183.194), 10/07/2015 02:16:32
推
10/07 12:02, , 1F
10/07 12:02, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：