순열

 

📌 공부이유

알고리즘을 풀면서 요소를 나열하여 나오는 경우의 수를 구하는 경우가 많은 데 이때의 방식을 이해하고 쉽게 사용할 수 있는 식을 익히기 위해 정리!

 

📌 순열 : 순서를 고려하여 나열하는 것

서로 다른 n개에서 r개를 택하여 순서있게 나열 (단, 0 < r <= n)

엔피알이라고 읽는다(P는 순열을 뜻하는 Permutaion의 P). 그리고 수식으로 풀이하면 아래와 같다.

 

 

📍예제

1,2,3 중 2개를 선택해 순서있게 나열하는 경우의 수는 무엇인가

 

첫번째 자리는 3개 중 아무거나 올수 있기 때문에 3가지 경우 수

두번째 자리는 1개가 이미 선택되었기 때문에 남은 2개 중 선택할 수 있기 때문에 2가지 경우의 수가 있다.

이 경우를 곱하면 3x2 = 그래서 6가지 

 

이걸 위의 표기 식으로 적용하면 

 

 

여기서 순열을 좀 더 쉽게 표현하는 방법이 있다

1부터 n까지의 자연수를 차례로 곱하는 것이 n의 계승이라고 하며 n! 로 표기한다 (n 팩토리얼이라고 읽는다)

4! 라면 4*3*2*1 을 의미하며 위의 순열 표기로 봤을 때 아래와 같다 

 

*** 0일 케이스 주의 

그럼 엔피엔일 경우는 그런데 그런 nPr은?

nPr을 nPn화 시키면 (n-r)*....*1을 곱해야한다. 그리고 그식은 바로 (n-r)! 에 해당하니

n! 에서 (n-r)! 나누면 nPr 값이 되는 것이다. 

📌 같은 것이 있는,  중복이 있는 순열

위에서는 서로 다른 요소들이 있는 순열이 었는데 같은 요소가 있는 경우는 어떻게 해야할까?

이런 경우 n! / (n-r)! 에서 중복된 요소들끼리의 자리 바꿀 경우의 수를 나누어 주면 된다. 

 

아래 경우

ABCDE, ACBDE, BACDE, BCADE, CABDE, CBADE는 모두 6가지 다른 요소다

하지만 여기서 BC가 모두 A라면?

AAADE, AAADE, AAADE, AAADE, AAADE, AAADE  6가지 모두 같은 요소가 되어 버린다.

이렇게 때문에 중복요소가 3개면 아래 처럼 표현할 수 있게 된다.

그럼 나머지 DE도 다른 값으로 중복이 되면 어떻게 표현 할까 

바로 아래 처럼 표현 할 수 있다

그래서 결국 위의 예제에서 중복된 순열을 만들 경우 10가지만 나온다 

 

 

 

 

참고 자료 :