01. 순열(Permutation)

 

1. 1. 경우의 수(Number of cases)

- 사건(Event): 동일하게 반복할 수 있는 어떤 실험이나 관찰에 의하여 일어나는 결과.

 

- 경우의 수(Number of cases): 어떤 사건이 일어날 수 있는 가짓수.

 

 

- 사건 A의 경우의 수를 m, 사건 B의 경우의 수를 n이라 하면

 

  1) 두 사건이 동시에 일어나지 않을 때 사건 A 또는 사건 B가 일어나는 경우의 수는 m + n.

 

  2) 두 사건이 동시에 일어날 때 사건 A 그리고 사건 B가 일어나는 경우의 수는 m X n.

 

 

- 약수의 개수(Number of divisors) 구하는 법: 약수의 개수를 구하고자 하는 수를 소인수분해 하고 소인수분해로 나온 소수들의 지수 값에 각각 + 1을 더한 뒤 모든 값들을 곱한다.

 

  ex ) A^p X B^q X C^r 의 약수의 개수 -> (p + 1)(q + 1)(r + 1). [A, B, C는 소수]

 

---

 

1. 2. 순열(Permutation)

- 순열(Permutation, _nP_r): 서로 다른 n개에서 서로 다른 r (n ≥ r)개를 택하여 일렬로 배열하는 것.

 

- _nP_r = n X (n - 1) X (n - 2) X … X (n – r + 1).

 

- n!(Factorial) = _nP_n = n X (n - 1) X (n - 2) X … X 3 X 2 X 1.

 

- _nP_r = n! / (n - r)!

 

- _nP₀ = 1, 0! = 1.

 

- 적어도(at least)라는 말이 오면 전체 경우의 수에서 반대로 가정한 경우의 수를 뺀다.

 

---

 

1. 3. 원순열(Circular permutation)

- 원순열(Circular permutation): 서로 다른 n개 에서 서로 다른 r개를 택하여 원형으로 배열하는 것.

 

 

- 원순열의 수(Number of circular permutation)

 

  1) 순열의 수 / 배열하는 원소의 개수.

 

  2) 서로 다른 n개를 전부 원형으로 배열하는 원순열의 수 = n! / n = (n - 1)!.

  

  3) 서로 다른 n개에서 일부인 r개를 택하여 원형으로 배열하는 원순열의 수 = _nP_r / r.

 

  4) 원이 아닌 정사각형에 n명을 앉히는 방법: (n - 1)! X n/4.

 

      원이 아닌 직사각형에 n명을 앉히는 방법: (n - 1)! X n/2.

 

      원이 아닌 정삼각형에 n명을 앉히는 방법: (n - 1)! X n/3.

 

      즉, 원순열의 수 X 서로 다른 자리의 수 를 하면 된다.

 

---

 

1. 4. 중복순열(Permutation with repetition)

- 중복순열(Permutation with repetition, _nΠ_r): 서로 다른 n개에서 중복을 허용하여 r개를 택하여 일렬로 배열하는 것.

 

- 기존 순열과 다른 점은 r개를 뽑을 때 중복을 허용한다는 점이다.

 

- _nΠ_r = n^r. (n은 받는 쪽, r은 주는 쪽).

 

 

1. 5. 같은 것이 있는 순열(Permutation of multisets)

- n개 중에서 같은 것이 각각 p개, q개, … , r개 씩 있을 때 순열의 수는

 

   n! / p!q!...r! [n = p + q + … + r].

 

- n개 중에서 순서가 정해진 것이 p개(연속된 한 묶음 X) 있을 때 순열의 수는

 

   n! / p! .

 

---