셔플 순열

조합론에서 셔플 순열(영어: shuffle permutation)은 카드의 셔플을 통하여 얻을 수 있는 순열이다.

정의

원순서 집합 $(X,\leq )$의 분할

$X=\bigsqcup _{i\in I}X_{i}$

이 주어졌다고 하자. 그렇다면, 이 분할에 대한 셔플 순열은 순열(전단사 함수)

$\sigma \colon X\to X$

가운데 다음 조건을 만족시키는 것이다.

$\left(x\leq x'\implies \sigma (x)\leq \sigma (x')\right)\qquad \forall i\in I\;\forall x,x'\in X_{i}$

이다. 이러한 셔플 순열의 집합을 $\operatorname {Sh} ((X_{i\in I})_{i\in I})$라고 한다.

특히, $\operatorname {Sh} (p,q)$는 전순서 집합 $\{1,2,\dotsc ,p+q\}$의 분할

$\{1,2,\dotsc ,p\}\sqcup \{p+1,\dotsc ,p+q\}$

대한 셔플 순열이다. 즉,

$\sigma (1)<\sigma (2)<\cdots <\sigma (p)$

$\sigma (p+1)<\sigma (p+2)<\cdots <\sigma (p+q)$

을 만족시키는 순열 $\sigma \in \operatorname {Sym} (p+q)$이다.

성질

$(p_{1},p_{2},\dotsc ,p_{k})$-셔플 순열의 수는

$|\operatorname {Sh} (p_{1},p_{2},\dotsc ,p_{k})|={\frac {(p_{1}+p_{2}+\dotsb +p_{k})!}{p_{1}!p_{2}!\dotsm p_{k}!}}$

이다.

증명:

$k=2$일 때, $(p,q)$-셔플은 처음 $p$개의 원소의 위치 $\sigma (1),\dots ,\sigma (p)$에 의하여 완전히 결정되므로, $(p,q)$-셔플의 수는 이항 계수

${\binom {p+q}{p}}={\binom {p+q}{q}}$

이다.

$k>2$일 때, $(p_{1},p_{2},\dotsc ,p_{k})$-셔플 순열은 $(p_{1},\dotsc ,p_{k-1})$-셔플 순열과 $(p_{1}+\dotsb +p_{k-1},p_{k})$-셔플 순열로 결정된다. 즉,

${\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}}$

이다.

응용

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

어원

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

외부 링크

• Weisstein, Eric Wolfgang. “Riffle shuffle”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “In-shuffle”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Out-shuffle”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Shuffle”. 《nLab》 (영어).