셔플 순열(영어: shuffle permutation)은 조합론(combinatorics)에서 정의되는 개념으로, 카드의 셔플(shuffle)을 통하여 얻을 수 있는 순열을 가리킨다. 이는 수학의 여러 분야, 특히 위상수학과 외대수(exterior algebra) 등에서 활용된다.
정의
원순서 집합 $(X, \leq)$의 분할 $X = \bigsqcup_{i \in I} X_i$이 주어졌을 때, 이 분할에 대한 셔플 순열은 전단사 함수(순열) $\sigma : X \to X$ 가운데 다음 조건을 만족시키는 것이다:
$$ (x \leq x' \implies \sigma(x) \leq \sigma(x')) \quad \forall i \in I ; \forall x, x' \in X_i $$
즉, 각 분할 블록 $X_i$ 내의 원소들 사이의 순서가 순열 $\sigma$에 의해서도 그대로 유지되는 순열을 의미한다.
특히, $(p, q)$-셔플 순열은 전순서 집합 ${1, 2, \dots, p+q}$를 ${1, 2, \dots, p}$와 ${p+1, \dots, p+q}$로 분할한 경우에 해당하며, 다음 조건을 만족시키는 순열 $\sigma \in \operatorname{Sym}(p+q)$이다:
$$ \sigma(1) < \sigma(2) < \cdots < \sigma(p) $$ $$ \sigma(p+1) < \sigma(p+2) < \cdots < \sigma(p+q) $$
성질
$(p_1, p_2, \dots, p_k)$-셔플 순열의 개수는 다음과 같은 다항 계수(multinomial coefficient) 형태로 주어진다:
$$ |\operatorname{Sh}(p_1, p_2, \dots, p_k)| = \frac{(p_1 + p_2 + \cdots + p_k)!}{p_1! , p_2! , \cdots , p_k!} $$
$k=2$인 경우, $(p, q)$-셔플 순열의 수는 이항 계수 $\binom{p+q}{p} = \binom{p+q}{q}$와 같다. 이는 처음 $p$개의 원소가 놓일 위치를 선택하는 경우의 수와 동일하기 때문이다.
응용
셔플 순열은 위상수학에서 완전 반대칭(completely antisymmetric)인 대상들을 다룰 때 사용된다. 예를 들어, 미분 형식(differential form)의 쐐기곱(wedge product)은 셔플 순열들에 대한 합으로 나타낼 수 있다. 또한 셔플 대수(shuffle algebra)의 정의와 성질 연구에도 핵심적인 역할을 한다.
어원
$(p, q)$-셔플 순열이라는 명칭은 $p+q$장의 카드를 처음 $p$장과 나머지 $q$장의 두 묶음으로 나눈 뒤, 이 두 묶음을 섞는(셔플하는) 과정에서 얻을 수 있는 순열이라는 데에서 유래하였다. 카드의 리플 셔플(riffle shuffle)과 같은 물리적 셔플 방식이 수학적으로 모델링될 때 이러한 순열이 자연스럽게 등장한다.
관련 개념
셔플 순열은 완전 셔플(perfect shuffle)의 수학적 분석, 피셔-예이츠 셔플(Fisher-Yates shuffle) 알고리즘, 리플 셔플 순열(riffle shuffle permutation) 등 카드 셔플과 관련된 다양한 조합론적 주제와 연결된다. 또한 군론(group theory)에서는 셔플 순열들의 집합이 특정한 군 구조를 형성하기도 한다.
