순열,permutation

서로 다른 n개에서 r개를 택하여 일렬로 배열하는 것. (n≥r)

비복원추출 중복 × (불허) 순열 nPr
복원추출 중복 ○ (허락) 중복순열 nΠr=nr

MKL
symmetric_group

[edit]

1. Simple Example

5P3 = 5×4×3
이렇게 간단한 것은 계승이 포함된 그 공식을 기계적으로 쓰는 것보다 RR:경우의_수,number_of_cases를 생각해서 몇 개의 숫자를 곱하는 것이 빠르다.
일반적인 경우를 나타내기 위해선 계승이 포함된 공식이 필요한데, 분자와 분모에 같은 값을 곱하는 변형을 한다. 위의 경우
5P3 = 5×4×3 = 5×4×3×2×1 / 2×1 = 5! / 2! = 5! / (5−3)!
서로 다른 n개에서 r개를 선택하는 순열의 수는
nPr = n×(n−1)×…×(n−r+1) = n! / (n−r)!

[edit]

2. 순열의 수 계산법

서로 다른 $n$ 개에서 $r$ 개를 택하는 순열의 수는
${}_{n}\mathrm{P}_{r}=\underbrace{n(n-1)(n-2)\cdots(n-(r-1))}_{r\text{ numbers}}\quad\quad(0\lt r\le n)$

계승,factorial을 이용해 표현하면
${}_{n}\mathrm{P}_{r}=\frac{n!}{(n-r)!}\quad\quad(0\le r\le n)$

이유는,
$\frac{n!}{(n-r)!}$
$=\frac{n(n-1)(n-2)\cdots(n-r+1)(n-r)(n-r-1)\cdots 2\cdot 1}{(n-r)(n-r-1)\cdots 2\cdot 1}$
$=n(n-1)(n-2)\cdots(n-r+1)$
$=n(n-1)(n-2)\cdots(n-(r-1))$
$={}_{n}\mathrm{P}_{r}$

그 외 알아두면 좋은 성질들

${}_{n}\mathrm{P}_{n}=n!$
$\left({}_{n}\mathrm{P}_{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}\right)$
즉 이때는 계승과 같다. QQQ 그럼 아마도 순열은 계승의 일반화? n개중에 n개를 늘어놓는 경우의 수가 계승이라면, 순열은 (0, 1, 2, …, n)개를 늘어놓는 모든 경우로 일반화,generalization한?

${}_{n}\mathrm{P}_{0}=1$
$\left({}_{n}\mathrm{P}_{0}=\frac{n!}{(n-0)!}\right)$

[edit]

3. TI-Nspire

nPr(n,r)

[edit]

4. 원순열

서로 다른 n개를 원형으로 배열하는 수는
$\frac{n!}{n}=(n-1)!$

[edit]

5. 중복순열

${}_n\mathrm{\Pi}_r$ 기호는 한국에서만 쓰나?

[edit]

6. 같은 것이 있는 순열

$n$ 개 중 $p$ 개, $q$ 개, $r$ 개, …, $s$ 개가 각각 같은 것일 때,
이들을 일렬로 나열하는 순열의 수는
$\frac{n!}{p!\times q!\times r!\times \cdots \times s!}$
단, $n=p+q+r+\cdots+s$

ex1. 빨간 공 3개, 초록 공 2개, 파란 공 2개를 일렬로 배열하는 방법의 수
$\frac{7!}{3! \cdot 2! \cdot 2!}=210$

ex2. tomorrow의 8개 알파벳을 일렬로 나열하는 경우의 수는?
sol. o가 세 개, r이 두 개 있으므로
$\frac{8!}{2!\cdot 3!}=3360$

AKA 동자순열, permutation of multisets

[edit]

7. 완전순열 complete permutation

완전순열 complete_permutation = 교란 derangement
rel. 준계승,subfactorial - curr see 계승,factorial
via WpKo:완전순열

[edit]

8. 교대치환, 교대순열 alternating permutation

[edit]

9. (위아래mkl)


[edit]

10. parity of a permutation

[edit]

11. factorial 과의 관계

계승,factorial
순열 = 하강계승 falling_factorial. (namu) QQQ 항상? 완전동의어인지 확실히

[edit]

12. mkl: super-permutation (per가 두번. supermutation 아님...)

[edit]

13. tmp 1

// from Namu:순열 ; chk
aka falling_factorial (rel. 계승,factorial)
단어 permutation은 군론,group_theory(curr 군,group) 에서 치환,permutation을 뜻하며, 치환의 개수는 순열로 표현 가능.

[edit]

14. 소스, Prg Lang Impl

[edit]

15. mkl


같은 영단어
치환,permutation - writing
대체로 군,group론에서 치환? [1]
조합론,combinatorics, 확률론(확률,probability)에서 '순열'인 거?

permutation의 정의는 전단사,bijection의 planetmath부분도 참조.

[edit]

16. cmp

----
  • [1] Namu:순열각주 "이 단어는 군론에서 치환을 의미하며"