셔플 순열

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

정의

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

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

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

${\displaystyle \sigma \colon X\to X}$

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

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

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

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

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

대한 셔플 순열이다. 즉,

${\displaystyle \sigma (1)<\sigma (2)<\cdots <\sigma (p)}$

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

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

성질

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

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

이다.

증명:

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

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

이다.

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

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

이다.

응용

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

어원

${\displaystyle (p,q)}$-셔플 순열은 ${\displaystyle p+q}$개의 카드를, 처음 ${\displaystyle p}$개의 카드 및 끝의 ${\displaystyle 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》 (영어).