셔플 순열

3. 성질

$(p\_1,\; p\_2,\; \backslash 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$개의 원소의 위치 $\backslash sigma(1),\backslash dots,\backslash sigma(p)$에 의하여 완전히 결정되므로, $(p,q)$-셔플의 수는 이항 계수

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

이다.

$k>2$일 때, $(p\_1,\; p\_2,\; \backslash dotsc,\; p\_k)$-셔플 순열은 $(p\_1,\; \backslash dotsc,\; p\_\{k-1\})$-셔플 순열과 $(p\_1+\backslash 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$개 요소의 매핑 방식에 의해 완전히 결정되므로, $(p,q)$-셔플의 개수는 다음과 같다.

:$$\backslash binom\{p+q\}\{p\}.$$

그러나, 서로 다른 리플 셔플의 수는 $n$이 되도록 하는 모든 $p$와 $q$의 선택에 대해 이 공식을 합한 값(즉, $2^n$)과는 약간 다르다. 왜냐하면 항등 순열은 서로 다른 $p$와 $q$ 값에 대해 $(p,q)$-셔플로 여러 방식으로 표현될 수 있기 때문이다.

대신, $n=1,2,3,\backslash dots$에 대해, $n$장의 카드로 이루어진 덱의 서로 다른 리플 셔플 순열의 수는 다음과 같다.

:1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ...

더 일반적으로, 이 숫자에 대한 공식은 $2^n-n$이다. 예를 들어, 52장 카드 덱의 리플 셔플 순열은 4503599627370444개이다.

리플 셔플 순열이면서, 리플 셔플의 역순열이기도 한 순열의 수는

:$$\backslash binom\{n+1\}\{3\}+1.$$

$n=1,2,3,\backslash dots$에 대해, 이것은

:1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ...

이며, $n=52$일 때 정확히 23427개의 가역 셔플이 있다.

3. 1. (p,q)-셔플 순열의 개수

3. 2. 일반적인 셔플 순열의 개수

4. 순열 패턴

순열의 패턴은 순열에서 일부 $k$개의 값들의 부분 수열로부터 형성된 더 작은 순열로, 해당 값들을 순서를 유지하면서 1부터 $k$까지의 범위로 축소하여 얻는다. 몇몇 중요한 순열 집합들은 금지된 패턴의 유한 집합으로 특징지을 수 있으며, 이는 리플 셔플 순열에도 적용된다. 즉, 리플 셔플 순열은 321, 2143, 2413을 패턴으로 가지지 않는 순열과 정확히 일치한다.^[3] 예를 들어, 리플 셔플 순열은 유일한 최소 금지 패턴으로 2143을 갖는 vexillary 순열의 하위 클래스이다.^[6]

4. 1. 금지된 패턴

4. 2. 다른 순열 집합과의 관계

5. 완전 셔플

'''완전 셔플'''은 덱을 동일한 크기의 두 묶음으로 나누어 두 묶음 사이를 번갈아 가면서 섞는 리플 셔플 방식이다.^[7] 완전 셔플에는 인 셔플과 아웃 셔플의 두 가지 유형이 있으며, 숙련된 사람들은 이를 일관되게 수행할 수 있다.^[7]

이러한 셔플 순열을 사용하여 덱을 반복적으로 섞으면 일반적인 리플 셔플보다 훨씬 덜 무작위화되며, 몇 번의 완전 셔플 후에 원래 상태로 돌아간다.^[7] 특히 52장의 카드 덱은 52번의 인 셔플 또는 8번의 아웃 셔플 후에 원래 순서로 돌아간다.^[7] 이 사실은 여러 카드 마술 트릭의 기초가 된다.^[7]

5. 1. 인 셔플과 아웃 셔플

5. 2. 셔플과 순환

6. 확률 분포

길버트-섀넌-리드 모델은 인간이 수행하는 셔플과 잘 일치하는, 셔플에 대한 임의의 확률 분포를 설명한다.^[4] 이 모델에서, 항등 순열은 (n+1)/2ⁿ의 확률로 생성되며, 다른 모든 리플 순열은 1/2ⁿ의 동일한 확률로 생성된다. 이 모델의 분석을 바탕으로, 수학자들은 52장의 카드 덱을 완전히 무작위화하기 위해 7번의 리플 셔플을 수행할 것을 권장했다.^[5]

6. 1. 길버트-섀넌-리드 모델

6. 2. 무작위성과 셔플 횟수

7. 대수적 응용

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

리플 셔플은 셔플 대수를 정의하는 데 사용될 수 있다. 이는 기저가 단어 집합이고, 곱셈이 두 단어의 모든 리플 셔플의 합인 셔플 곱(샤 기호 ш로 표시)인 호프 대수이다.^[2]

외대수에서, $p$-형식과 $q$-형식의 외적은 $(p,q)$-셔플의 합으로 정의될 수 있다.^[2]

7. 1. 셔플 대수

7. 2. 외대수

8. 어원

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

참조

_[1] 간행물 Shuffling cards and stopping times https://statweb.stan[...]
_[2] 서적 An Introduction to Homological Algebra Cambridge University Press
_[3] 간행물 Restricted permutations
_[4] 서적 Group representations in probability and statistics Institute of Mathematical Statistics
_[5] 뉴스 In Shuffling Cards, 7 Is Winning Number https://www.nytimes.[...] 1990-01-09
_[6] 간행물 Permutation patterns, continued fractions, and a group determined by an ordered set Department of Mathematics, Chalmers University of Technology
_[7] 간행물 The mathematics of perfect shuffles