조합론에서 셔플 순열(영어: shuffle permutation)은 카드의 셔플을 통하여 얻을 수 있는 순열이다.
원순서 집합
의 분할
![{\displaystyle X=\bigsqcup _{i\in I}X_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f86c1a49b1728c77f3c6bdf8573742614666aaf1)
이 주어졌다고 하자. 그렇다면, 이 분할에 대한 셔플 순열은 순열(전단사 함수)
![{\displaystyle \sigma \colon X\to X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35b50628251daaf650583f48dca7a4f426516e10)
가운데 다음 조건을 만족시키는 것이다.
![{\displaystyle \left(x\leq x'\implies \sigma (x)\leq \sigma (x')\right)\qquad \forall i\in I\;\forall x,x'\in X_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d48d2fdb0d978f000edde5ff3b4a9fb4f47d62c)
이다. 이러한 셔플 순열의 집합을
라고 한다.
특히,
는 전순서 집합
의 분할
![{\displaystyle \{1,2,\dotsc ,p\}\sqcup \{p+1,\dotsc ,p+q\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e752c6e79d98ea632a4ab4a50e67cb9034f5b485)
대한 셔플 순열이다. 즉,
![{\displaystyle \sigma (1)<\sigma (2)<\cdots <\sigma (p)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4651beb6f32e29ed18e31b6c7e367eca7d9640ca)
![{\displaystyle \sigma (p+1)<\sigma (p+2)<\cdots <\sigma (p+q)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33470b00288e82d82c453af70ec3efc4c1b75bfa)
을 만족시키는 순열
이다.
-셔플 순열의 수는
![{\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}!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/479187ab9e58dbba659d0014ddd093e213ccb1dd)
이다.
증명:
일 때,
-셔플은 처음
개의 원소의 위치
에 의하여 완전히 결정되므로,
-셔플의 수는 이항 계수
![{\displaystyle {\binom {p+q}{p}}={\binom {p+q}{q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f6921e75da17eadf2d1ddc4effa625a399344cb)
이다.
일 때,
-셔플 순열은
-셔플 순열과
-셔플 순열로 결정된다. 즉,
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45e9cad0deeb3bc29c90a9a9e67c11e0ecc4dd13)
이다.
셔플 수열은 위상수학에서 완전 반대칭인 것들을 다룰 때 쓰인다. 예를 들어, 미분 형식의 쐐기곱은 셔플 순열들에 대한 합으로 나타낼 수 있다.
-셔플 순열은
개의 카드를, 처음
개의 카드 및 끝의
개의 카드로 분리한 다음, 셔플을 하여 얻을 수 있는 순열이기 때문에 이러한 이름이 붙었다.
외부 링크[편집]