作者darkseer ( )
看板IMO_Taiwan
標題[問題] 濫用看板2
時間Mon Aug 27 07:40:10 2018
我又要來濫用看板啦！
在表現理論(representation theory)的研究裡，我們知道組合常常有深刻的應用。
對於一個正整數n，我們考慮n的所有partitions，
例如n=4時，我們把它們記為(1111), (211), (22), (31), (4)
現在我有一個吃partition吐出正整數的未知函數，不知道為什麼它是well-defined，
但偏偏好像是。用電腦跑例子出來它的值是：
f(1)=1,
f(11)=1, f(2)=2,
f(111)=1, f(21)=3, f(3)=3,
f(1111)=1, f(211)=4, f(22)=2, f(31)=4, f(4)=4,
f(11111)=1, f(2111)=5, f(221)=5, f(311)=5, f(32)=5, f(41)=5, f(5)=5
f(111111)=1, f(21111)=6, f(2211)=9, f(222)=2, f(3111)=6, f(321)=12,
f(33)=3, f(411)=6, f(42)=6, f(51)=6, f(6)=6
f(1111111)=1, f(211111)=7, f(22111)=14, f(2221)=7, f(31111)=7, f(3211)=21,
f(322)=7, f(331)=7, f(4111)=7, f(421)=14, f(43)=7, f(511)=7, f(52)=7
f(61)=7, f(7)=7,
f(11111111)=1, f(2111111)=8, f(221111)=20, f(22211)=16, f(2222)=2,
f(311111)=8, f(32111)=32, f(3221)=24, f(3311)=12, f(332)=8, f(41111)=8,
f(4211)=24, f(422)=8, f(431)=16, f(44)=4, f(5111)=8, f(521)=16, f(53)=8,
f(611)=8, f(62)=8, f(71)=8, f(8)=8
所以這個函數究竟是什麼啊啊啊啊啊!!!??
教我這個函數是什麼的人，他的名字可能有5%機率出現在某個猜想上吧XD
----
喔耶我知道了，提示(按\開燈看)：
(1)把奇數長和偶數長的給異號，例如f(111)=1, f(21)=-3, f(3)=3。
(2)看成S_n的rep'ns
結果在組合書(MacDonald, Symmetric functions and Hall Polynomials
第二版，習題2.20)
裡的習題(一題一題看XD)找到了很短的closed formula! 隔一頁防雷再開燈看好了，
看到之後，覺得怎麼就沒想到呢...
closed formula:
l(u)=u的長度，例如l(522)=3, u_i表示每個相同數字的部分，例如
u=522就有u_1=5, u_2=22，則f(u)=n*(l(u)-1)!/\prod l(u_i)!
例如f(544432211)=26*8!/3!*2!*2!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.5.70.218
※ 文章網址: https://webptt.com/m.aspx?n=bbs/IMO_Taiwan/M.1535326812.A.F18.html
1F：→ darkseer: 唔，我覺得我知道了，雖然是從表示論的地方猜到的 08/27 15:43
2F：推 Dawsen: 為什麼f(22) 不是4？ 08/27 22:35
3F：→ darkseer: 就很奇怪XD 我其實還不知道他的closed formula， 08/27 23:33
4F：→ darkseer: 但我知道他的定義和表示論意義了(which is what I need) 08/27 23:33
5F：→ darkseer: 加個提示好了(開燈看) 08/27 23:34
※ 編輯: darkseer (24.5.70.218), 08/27/2018 23:36:48
6F：推 yclinpa: 與 {1,2,...,n} 的非空子集有關嗎？ 08/28 09:07
7F：→ darkseer: To樓上：如果有的話我還不知道 08/28 15:26
8F：→ yclinpa: 橫排加起來等於 2^n - 1 , 就猜猜看 08/28 16:12
9F：→ darkseer: 強耶!! 我沒有發現，我要想一下這是為什麼... 08/28 17:25
10F：→ darkseer: 想不出來，明天再想。也許樓上大大製造了新的組合猜想XD 08/28 17:36
11F：→ darkseer: 找到了closed formula，但還不知道為什麼加起來2^n-1 :O 08/30 04:57
※ 編輯: darkseer (24.5.70.218), 08/30/2018 05:00:53
12F：推 parity: 我是潛水版友，提示(2)和(1)搭配還是看不懂。可以私下提 09/03 00:17
13F：→ parity: 示嗎 XD 09/03 00:17
14F：→ darkseer: 我錯了，反應慢QQ 其實那個需要的群論/表示論有點多 09/03 01:17
15F：→ darkseer: 不如直接看最後一頁的公式，然後想yclinpa的組合對應XD 09/03 01:18
16F：→ darkseer: 就是加起來是2^n-1那個 有個組合對應的證明挺有趣 09/03 01:18
17F：推 parity: 喔喔，好的感謝。 09/03 12:13