기초 수학 - 3. 순열과 조합

팩토리얼 (Factorial)

순열이나 조합을 계산하기 위해서는 우선 팩토리얼을 알아야 합니다.

 

팩토리얼이란 1부터 n까지의 자연수를 모두 곱하는 것을 의미합니다.

 

수식으로는 다음과 같이 나타냅니다.

n! = n(n - 1)(n - 2)(n - 3) .... 1

 

---

순열 (Permutation)

순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서를 정해 나열하는 것을 뜻합니다.

 

다음과 같은 공식을 이용하여 순열의 개수를 구할 수 있습니다.

nPr = n(n - 1)(n - 2)(n - 3) ..... (n - r + 1)   (단, 0 < r ≤ n)

 

​팩토리얼을 이용하면 다음과 같이 간략화 할 수 있습니다.

 

 

 

중복 순열

중복 순열이란 서로 다른 n개의 원소에서 r개를 중복을 허용하고 순서를 정해 나열하는 것을 뜻합니다.

 

식으로는 다음과 같습니다.

n∏r = n^r

 

 

원 순열

원 순열이란 n개의 원소를 원형으로 나열하는 경우의 수를 뜻합니다.

 

식으로는 다음과 같습니다.

n! / n = (n - 1)!

 

원형으로 나열한다는 것이 잘 이해가 가지 않을 수 있는데 다음과 같이 생각해보면 됩니다.

 

사람 a , b , c 가 원형테이블에 둘러 앉는다고 했을 때, 나올 수 있는 경우의 수는 다음과 같습니다.

 

A B C 나 A C B 단 두가지의 경우의 수만 나오게 됩니다.

 

B A C , B C A 등도 되는거 아니냐라고 생각할 수 있는데, 원형으로 나열한다는 것은 첫 시작점이 존재하지 않고 순환한다고 생각해야 합니다. 즉 A B C는 B C A , C A B , A B C 이런식으로 모두 동일하게 취급이 됩니다. 

 

식을 사용해서 계산해보면 다음과 같이 나오게 됩니다.

(3 - 1)! = 2 x 1 = 2

 

---

조합 (Combination)

조합이란 서로 다른 n개 중에서 중복 없이, 순서 상관없이 r 개를 선택하는 것을 의미합니다.

 

조합은 다음과 같이 나타냅니다.

nCr = n! / (n - r)!r! = nPr / r!       단, 0 < r ≤ n

 

중복 조합

중복 조합이란 서로 다른 n개 중에서 중복을 허용하여 순서 상관없이 r 개를 선택하는 것을 의미합니다.

 

중복 조합은 다음과 같이 나타냅니다.

nHr = r+n-1Cr = r+n-1Cn-1

 

 

---

프로그래밍 언어로 구현

Java

public class Example {

	/**		순열
    		arr : 원래 배열
       	 	depth : 자리수
        	visited : 방문했는지 체크해줄 배열
        	out : 결과값 저장 배열
        */

	void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
    
        if(depth == r) {
            System.out.println(Arrays.toString(out)); 
            return;
        }

        for(int i = 0; i < n; i++) {
            if(visited[i] != true) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, depth + 1, n, r, visited, out);    
                visited[i] = false;
            }
		}
	}
    
    	/**		조합
    		arr : 원래 배열
       	 	depth : 자리수
        	visited : 방문했는지 체크해줄 배열
        */
    
    
    void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++){
            	if (visited[i]) {
                	System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
       combination(arr, visited, depth + 1, n, r);
    }

}

 

 

 

참고자료

https://namu.wiki/w/%EC%A1%B0%ED%95%A9

https://zero-base.co.kr/