셔플 순열

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

정의

X = ⨆_{i \in I} X_{i}

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

σ : X \to X

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

(x \leq x^{'} ⟹ σ (x) \leq σ (x^{'})) \forall i \in I \forall x, x^{'} \in X_{i}

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

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

{1, 2, \dots, p} ⊔ {p + 1, \dots, p + q}

대한 셔플 순열이다. 즉,

σ (1) < σ (2) < \dots < σ (p)

σ (p + 1) < σ (p + 2) < \dots < σ (p + q)

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

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

| Sh (p_{1}, p_{2}, \dots, p_{k}) | = \frac{(p_{1} + p_{2} + \dots + p_{k})!}{p_{1}! p_{2}! \dots p_{k}!}

이다.

증명:

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

(\binom{p + q}{p}) = (\binom{p + q}{q})

이다.

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

\begin{matrix} | Sh (p_{1}, \dots, p_{k}) | & = | Sh (p_{1}, \dots, p_{k - 1}) | \cdot (\binom{p_{1} + \dots + p_{k}}{p_{k}}) \\ = | Sh (p_{1}, \dots, p_{k - 2}) | \cdot (\binom{p_{1} + \dots + p_{k - 1}}{p_{k - 1}}) \cdot (\binom{p_{1} + \dots + p_{k}}{p_{k}}) \\ ⋮ \\ = \prod_{i = 1}^{k} (\binom{p_{1} + \dots + p_{i}}{p_{i}}) \\ = \frac{(p_{1} + \dots + p_{k})!}{p_{1}! \dots p_{k}!} \end{matrix}

이다.

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

$(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》.