篇名 | On the Cardinality of Permutations for Interval Exchange Transformations |
---|---|
卷期 | 10:2 |
並列篇名 | 針對區段交換轉換之排列的計數 |
作者 | 郭定 |
頁次 | 081-087 |
關鍵字 | enumerative combinatorics 、 interval exchange transformation 、 permutation 、 derangements 、 isomorphic. 、 計數組合學 、 區段交換轉換 、 排列 、 錯位排列 、 同構 |
出刊日期 | 201409 |
The basic problem of enumerative combinatorics is counting the number of elements for a set. This paper focuses on a particular set GN, which is the subset of permutations of N items for interval exchange transformations. In mathematics, an interval exchange transformation is a type of dynamical system. Unlike a “sieve” method that begins with a larger set and somehow eliminates the unqualified elements, a decomposition approach was used in this study. Based on the results of using this approach, we propose a concise formula of the cardinality of GN. In addition, we related the set of GN,N to the set of BN,N, where GN,N denotes the subset of GN that is composed of all permutations with a prefix “N”, and BN,N denotes the set of permutations without a succession. For N ≥ 1, we proved and thus propose that BN,N and GN+1,N+1 are isomorphic and that BN,N is postequivalent to GN+1,N+1.
計數組合學的基本問題是研究如何計算一個特定的有限集合之組成個數。本研究選擇n項排列的一個特定的部份集合GN作為研究對象,此部份集合乃是提供運作於n個區段上的區段交換轉換之用。就數學上而言,區段交換轉換是一種動態系統。針對GN的計數,本研究採用拆解法而有別於常見的篩選法。利用此方法我們針對GN 的個數提出一個很簡潔的計算公式。除此之外,我們將集合GN,N 聯結至集合BN,N。此處,GN,N是集合GN的一個部份集合,它是以N起頭的所有排列;而BN,N是一個由沒有任何兩個相鄰遞增位置是相鄰遞增數字的所有排列組成的集合。我們提出並證明當N ≥ 1時GN+1,N+1與BN,N是同構的,而且BN,N是後-等同於GN+1,N+1。