臺灣博碩士論文加值系統

　　透過排序指標的啟發，T. K. Petersen 和B. E. Tenner 在論文「The depth of a permutation, Journal of Combinatorics, 6 (2) 2015: 145–178」提出了深度統計量：描述將一個排列經過一系列兩位置交換回到單位排列所需的最小成本。
他們證明了深度統計量可以簡單地由勝位數來計算：對任意排列π = π1π2 · · · πn ∈ Sn，其深度為dep(π) =Σi∈Exc(π)(πi − i)，其中，Exc(π) = {i : πi > i, 1 ≤ i ≤ n} 表示π 的勝位集。
令exc(π) = |Exc(π)| 表示π 的勝位數。本論文將研究深度和勝位數的雙統計量聯合分佈，並透過代數計算與組合雙射方法，證明了一些有趣的對稱性。

　　Motivated by the sorting index, T. K. Petersen and B. E. Tenner in “The depth of a permutation, Journal of Combinatorics, 6 (2) 2015: 145–178” defined a statistic called depth, which describes the minimum “cost” needed to sort a permutation to the identity by a series of transpositions. They showed the depth of a permutation π = π1π2 · · · πn ∈ Sn can be simply given by dep(π) = Σi∈Exc(π)(πi−i), where Exc(π) = {i : πi > i, 1 ≤ i ≤ n} refers to the set of excedances. Denote by exc(π) = |Exc(π)| the number of excedances in π. In this thesis, we study the joint distribution of the two related statistics dep and exc over Sn. We show some interesting symmetric properties by both algebraic and combinatorial (bijective) methods.

謝誌 (Acknowledgement)　i
中文摘要　ii
英文摘要 (Abstract)　iii
目錄 (Contents)　iv
圖目錄 (List of Figures)　v
表目錄 (List of Tables)　vi

1 排列統計量　1
　1.1 長度函數與Mahonian 統計量　1
　1.2 深度統計量　4
　1.3 勝位數與深度的聯合分布　5
2 exc-dep 表格的確切值　10
　2.1 Dn(0) : dep = exc　10
　2.2 Dn(1) : dep = exc + 1　11
3 exc-dep 表格上的組合雙射　13
　3.1 Dn(0) : dep = exc　13
　3.2 Dn(1) : dep = exc + 1　15
4 exc-dep 表格內的巴斯卡性質　20
5 結語　30
　5.1 主要結果　30
　5.2 未來工作　31
參考文獻(References)　32

[1] R. M. Adin, I. Gessel, and Y. Roichman, Signed Mahonians, J. Combin. Theory Ser. A 109 (2005) 25–43.
[2] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Grad. Texts in Math., vol. 231, Springer, New York, 2005.
[3] R. J. Clarke, E. Steingrímsson, and J. Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in Appl. Math. 18 (1997) 237–270.
[4] S.-P. Eu, T.-S. Fu, H.-C. Hsu, H.-C. Liao, and W.-L. Sun, Signed mahonian identities on permutations with subsequence restrictions, J. Combin. Theory Ser. A 170 (2020) 105–131.
[5] D. Foata and M. P. Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978) 143–159.
[6] P. A. MacMahon, The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913) 281–322.
[7] D. E. Knuth, The Art of Computer Programming, vol. 3, Addison–Wesley, 1998.
[8] T. K. Petersen, The sorting index, Adv. in Appl. Math. 47 (2011) 615–630.
[9] T. K. Petersen, R. Biagioli, M. Novick, and A. Woo, Depth in classical Coxeter groups, J. Algebr. Comb. 44 (2016) 645–676.
[10] T. K. Petersen and T. K. Tenner, The depth of a permutation, J. Comb. 6 (1–2) (2015) 145–178.
[11] O. Rodriguez, Note sur les inversions, ou dérangements produits dans les permutations, J. Math. 4 (1839) 236–240.
[12] M. Wachs, An involution for signed Eulerian numbers, Discrete Math. 99 (1992) 59–62.