셔플 순열 문서 원본 보기

[[조합론]]에서 '''셔플 순열'''({{llang|en|shuffle permutation}})은 카드의 [[셔플]]을 통하여 얻을 수 있는 [[순열]]이다.

== 정의 ==
[[원순서 집합]] <math>(X,\le)</math>의 [[집합의 분할|분할]]
:<math>X = \bigsqcup_{i\in I}X_i</math>
이 주어졌다고 하자. 그렇다면, 이 분할에 대한 '''셔플 순열'''은  순열([[전단사 함수]])
:<math>\sigma\colon X \to X</math>
가운데 다음 조건을 만족시키는 것이다.
:<math>\left(x\le x' \implies \sigma(x) \le \sigma(x')\right) \qquad \forall i\in I\;\forall x,x'\in X_i</math>
이다. 이러한 셔플 순열의 집합을 <math>\operatorname{Sh}((X_{i\in I})_{i\in I})</math>라고 한다.

특히, <math>\operatorname{Sh}(p,q)</math>는 [[전순서 집합]]  <math>\{1,2,\dotsc,p+q\}</math>의 분할
:<math>\{1,2,\dotsc,p\} \sqcup \{p+1,\dotsc,p+q\}</math>
대한 셔플 순열이다. 즉,
:<math>\sigma(1)<\sigma(2)<\cdots<\sigma(p)</math>
:<math>\sigma(p+1)<\sigma(p+2)<\cdots<\sigma(p+q)</math>
을 만족시키는 순열 <math>\sigma\in\operatorname{Sym}(p+q)</math>이다.

== 성질 ==
<math>(p_1,p_2,\dotsc,p_k)</math>-셔플 순열의 수는
:<math>
|\operatorname{Sh}(p_1,p_2,\dotsc,p_k)| =
\frac{(p_1+p_2+\dotsb+p_k)!}{p_1!p_2!\dotsm p_k!}
</math>
이다.
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
<math>k=2</math>일 때, <math>(p,q)</math>-셔플은 처음 <math>p</math>개의 원소의 위치 <math>\sigma(1),\dots,\sigma(p)</math>에 의하여 완전히 결정되므로, <math>(p,q)</math>-셔플의 수는 [[이항 계수]]
:<math>\binom{p+q}p=\binom{p+q}q</math>
이다.

<math>k>2</math>일 때, <Math>(p_1,p_2,\dotsc,p_k)</math>-셔플 순열은 <Math>(p_1,\dotsc,p_{k-1})</math>-셔플 순열과 <Math>(p_1+\dotsb+p_{k-1},p_k)</math>-셔플 순열로 결정된다. 즉,
:<math>
\begin{aligned}
|\operatorname{Sh}(p_1,\dotsc,p_k)| &= 
|\operatorname{Sh}(p_1,\dotsc,p_{k-1})| \cdot \binom{p_1+\dotsb+p_k}{p_k} \\
&=  
|\operatorname{Sh}(p_1,\dotsc,p_{k-2})| \cdot \binom{p_1+\dotsb+p_{k-1}}{p_{k-1}}  \cdot \binom{p_1+\dotsb+p_k}{p_k} \\
& \;\vdots \\
&= \prod_{i=1}^k \binom {p_1+\dotsb+p_i}{p_i} \\
&= \frac{(p_1+\dotsb+p_k)!}{p_1!\dotsm p_k!}
\end{aligned}
</math>
이다.
</div></div>

== 응용 ==
셔플 수열은 [[위상수학]]에서 완전 반대칭인 것들을 다룰 때 쓰인다. 예를 들어, [[미분 형식]]의 [[쐐기곱]]은 셔플 순열들에 대한 합으로 나타낼 수 있다.

== 어원 ==
<math>(p,q)</math>-셔플 순열은 <math>p+q</math>개의 카드를, 처음 <math>p</math>개의 카드 및 끝의 <math>q</math>개의 카드로 분리한 다음, [[셔플]]을 하여 얻을 수 있는 [[순열]]이기 때문에 이러한 이름이 붙었다.

== 외부 링크 ==
* {{매스월드|id=RiffleShuffle|title=Riffle shuffle}}
* {{매스월드|id=In-Shuffle|title=In-shuffle}}
* {{매스월드|id=Out-Shuffle|title=Out-shuffle}}
* {{nlab|id=shuffle|title=Shuffle}}
{{위키데이터 속성 추적}}

[[분류:순열]]