순열,조합

순열, 조합을 배우는 이유는?

컴퓨터는 수학의 근본을 두고 있다. 알고리즘 안에 들어가는 개념들은 수학에서 온다.

DFS, BFS 같은 문제는 경우의 수가 대부분 들어간다.

DFS, BFS 배우면서 겸사겸사 수학의 확률을 정리해 보려고 한다.

1.순열

n개 중 r개를 뽑아서 순서있게 나열하는 경우의 수.

예시)

A B C에서 2개를 뽑아서 순서 있게 나열하시오.

(1) A - B

(2) A - C

(3) B - A

(4) B - C

(5) C - A

(6) C - B

답 : 6

A - B, B - A 순열은 순서가 존재하기 때문에 두 가지는 같지 않다.

2.조합

서로 다른 n개의 원소를 가지는 어떤 집합 (사실, 집합은 서로 다른 원소의 모임으로 정의된다.)에서 순서에 상관없이 r개의 원소를 선택하는 것이다. 즉, 선택의 순서와 상관없이 같은 원소들이 선택되었다면 같은 조합이며 다른 원소들이 선택되었다면 다른 조합이다.

참고

이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다. 가능한 조합의 수는 이항계수와 같다.

예시)

A B C에서 2개를 뽑아서 순서 있게 나열하시오.

(1) A - B

(2) B - C

(3) C - A

답 : 3

조합의 성질

• 첫 번째

위의 (5-2)! = 3! 은 같고 (5-2)! = 2!도 같다.

위의 성질을 공식화하면 중요~ 이항개수, 이항정리 성질 등에서 필요

• 두 번째

공식

통분을 해서 계산

정리해준다.

아래와 같이 정리가 된다.

정리 후기 오랜만에 학교시절에 배웠던 것을 배우니 새로운 느낌은 아니지만 정리를 깔끔히 한번 하니깐 이해가 쭈~욱 된다. 정리하길 잘 한듯.. 😀😀