Shuffles of posets : 부분순서집합의 섞기

국문 초록 (Abstract)

1988년, C. Greene은 섞여진 단어들(shuffled words)에 의해서 구성된 부분순서집합 W_m,n을 소개하고, 관련된 여러 조합론적 불변량들에 대한 결과들을 얻었다. R. Ehrenborg는 ^0과 ^1을 갖는 계층화된 부분순서 집합 P 위에서 급수 Fp(x)=Fp(x1, ...., xn)를 정의하였는데, R. Simion과 R. Stanley는 이 급수 Fp(x)가 대칭함수가 되기위낳 조건을 연구하여 F_Wm,n(x)가 대칭함수임을 증명하였다. 최근에 P. Hersh는 부분순서집합 W_m,n을 두가지 방향으로 일반화 하고, 여러 불변량들에 대한 결과와 급수 Fp(x)의 표현식을 얻었다. 본 논문에서는, 이항단어(binary words)라는 것을 정의하여 W_m,n이 일반화된 또다른 부분순서집합 W^(2)m,n을 제시한다. 여러 조합론적 불변량들에 대한 결과와 F_W(2)m,n(x)의 표현식이 유도될 것이다. 마지막으로, R. Strnley의 P-partition이론을 이항단어에 적용하여, 몇가지 조합론적 통계량들의 점화식을 얻을 것이다.

다국어 초록 (Multilingual Abstract)

In [Gr], C. Greene introduced posets of shuffles W_m,n which are formed by shuffles of words and gave many results on combinatorial invariants and structural properties of these posets. Independent of Greene's work, R. Ehrenborg defined a formal power series F_P (x) = F_P (x1, · · · , x_n) for a ranked poset P with ?0 and ?1. In general, the series is quasi-symmetric. R. Simion and R. Stanley studied conditions for the series FP (x) to be symmetric and proved that the related series FW_m,n(x) on Greene’s posets of shuffles W_m,n is symmetric. Recently, P. Hersh gave two generalizations of Greene’s posets of shuffles, shuffle posets allowing the repeatition of letters and k-shuffle posets constructed by shuffling k words, and determined the expression of the series F_P(x) of them. In this thesis, we give an another generalization, binary shuffle posets W^(2)_m,n, by defining binary words which are kind of trees. Their combinatorial invariants and formula of the related series F_W(2) m,n(x) will be provided. Finally, by applying Stanley’s P-partition theory to binary words, some recurrence relations of combinatorial statistics will be derived.

목차 (Table of Contents)

• Contents
• Abstract (English)
• 1 Introduction = 1
• 2 Preliminaries = 5
• 2.1 Basic Concepts = 5
• 2.2 Greene's Posets of Shuffles = 10
• 3 Binary Shuffle Posets = 24
• 4 Combinatorial Invariants = 36
• 5 Recursions and Generating Functions = 50
• 6 Quasi-Symmetric Functions = 56
• 7 P-partitions of shu es of posets = 65
• Bibliography = 79
• Abstract (Korean)