➕ 경우의 수

동시에 일어날 경우 곱셈
따로 따로 고려할 경우 덧셈

➖ 팩토리얼 (Factorial)

서로 다른 n개를 나열하는 경우의 수
n! : n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱하기

0! 은 1로 약속되었다.

✖ 순열 (Permutation)

순서대로 뽑아서 줄을 세우는 것
nPr : n개 중에서 r개를 뽑아서 줄을 세우는 것
n부터 r뺀 값 만큼 1씩 내려가면서 곱하면 구할 수 있다.
예를 들어, 5P3이라면 5에서 3뺀 값은 2이므로 5 * 4 * 3 = 60

팩토리얼로 변환하여 표현할 수도 있다.

위의 공식이 나오는 이유
5P3 = 5 * 4 * 3
= (5 * 4 * 3)(2 * 1) / (2 * 1)
= 5! / 2!
= 5! / (5-3)!

순열 top 5

1. 이웃하도록

이웃할 경우 보따리에 넣어 하나로 취급하고 계산하고, 그 안에서 순서가 뒤바뀔 경우를 곱해준다.

Q. a,b,c,d가 있을 때 a,b가 이웃할 경우의 수를 구하시오.
둘을 A라는 보따리 안에 넣은 후 A,c,d의 경우의 수를 구하고, [a,b], [b,a]인 경우를 고려하여 곱하면 된다.

2. 이웃하지 않도록

칸막이를 만들어 다른 요소를 먼저 줄세우고, 그 사이에 이웃하면 안되는 요소를 넣는다.

Q. 남자 3명, 여자 3명이 있을 때, 남자가 이웃하지 않을 경우의 수를 구하시오.
먼저 '0 여 0 여 0 여 0'처럼 세운 후, 남자를 생긴 4 자리 중 3자리에 넣는다.

이웃하지도, 이웃하지 않는 상태가 있으므로 여사건으로 풀 수 없다. (a,b,a,a,b,b-> 이웃 x, 동시에 이웃함) 단, 두명은 여사건 가능.

Q. 의자 6개에 여자 2명, 남자 3명이 앉을 때, 여학생이 이웃하지 않게 하는 경우의 수를 구하시오.
칸막이를 남자 3명과, 남은 의자 1개라고 생각한다. 따라서 4! * 5P2 = 480 이다.
하지만 2명이 이웃할 경우, 전체 경우에서 이웃하는 경우를 뺄 수 있다. 따라서 6! - 5!*2 = 480 이다.

3. 두 종류가 교대로

1. a = b + 1 (그 이상으로는 차이날 수 없음)
   더 큰 수를 먼저 줄 세우고 그 사이에 작은 수를 세운다. or 작은 수를 세우고 그 사이와 양 옆을 큰 수로 감싼다.

   남자가 5명, 여자가 4명일 때, [ 0 남 0 남 0 남 0 남 0 남 0 ] 이렇게 줄을 세운다. 단 여기서, 이웃하지 않도록! 과 다르게, 양 끝의 경우를 지운다. 양 끝에 서면 남자가 이웃하게 된다. 따라서 경우의 수는 5!(남자) * 4!(여자)이다.

2. a = b
   이웃할 경우, 경우가 더 늘어난다. a가 먼저 올지, b가 먼저 올지를 생각해야 하므로 경우의 수에 2를 곱해준다.

   [ 남 여 남 여 남 여 ] 일수도 있지만, [ 여 남 여 남 여 남 ] 일수도 있으므로, 3!(남) * 3!(여) * 2로 구할 수 있다.

4. ~사이에 ~가 오도록

주어진 조건의 요소들을 박스안에 넣고 생각한다. 박스 밖의 경우의 수와, 박스 안의 경우의 수를 곱해서 구할 수 있다.

Q. 부모와 3명의 아이가 있을 때, 부모 사이에 한 명의 자식이 오는 경우의 수를 구하시오.
일단 부모와 한 아이를 박스에 넣는다.
박스 안에서는, 우선 부모는 [ 부, 모 ]가 올수도 [ 모, 부 ]가 올 수도 있으므로 2!이며, 아이는 3명 중에 선택해야 하므로 3P1이다. 그 다음으로 박스 밖의 상황을 보면, 두 아이와 한 박스를 정렬해야 한다. 따라서 3!이다. 결과적으로 경우의 수는 2! * 3P1 * 3!이다.

적어도 한쪽 끝에 ~가 오도록

여 사건으로 풀 수 있다. 전체 경우의 수에서 모두 다 양 끝에 오지 않을 경우의 수를 뺄셈하여 구한다.

Q. 여 3 남 3가 있을 때 여자가 적어도 한끝에 올 경우의 수를 구하시오.
우선 총 경우의 수는 6!이다. 모두 양 끝에 오지 않을 경우의 수는, 남자 세 명 중 두 명을 양 끝에 배치할 경우의 수(3P2) x 남은 네 자리를 아무렇게나 차지할 경우의 수(4!) 이므로, 6! - 3P2 * 4!로 구할 수 있다.

➗ 조합

순서 상관 없이 서로 다른 n개중에 r개를 선택하는 경우의 수
nCr : n개 중에서 r개를 선택하는 것
더 간단할 것 같지만, 순서대로 선택하여 순서를 취소하는 방법으로 구해야 한다.
조합은 순열로 바꾼 후 구할 수 있다.

r!로 나누는 이유는, 만약 [1,2,3]을 나열할 경우 순열에서는 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]을 모두 다른 경우의 수로 보지만, 조합은 모두 같은 경우로 보기 때문이다. 따라서 중복되는 결과값을 없애야 한다.
순열은 팩토리얼로 바꿀 수 있기 때문에, 조합 또한 순열로 바꾼 뒤 팩토리얼로 바꿀 수 있다.

조합 top 5

1. a와 b가 C 안에 포함되도록

미리 a와 b를 C 안에 포함시켜 놓고 구한다.

Q. 임원 후보 10명이 있고, 임원을 3명 뽑을 때, a와 b가 임원에 포함될 경우의 수를 구하시오.
미리 a, b를 임원으로 올리고, 나머지 8명 중에서 1명을 뽑는다. 따라서 8C1 로 구할 수 있다.

2. a와 b가 C 안에 포함되지 않도록

a와 b를 아예 제외하고 구한다.

Q. 임원 후보 10명이 있고, 임원을 3명 뽑을 때, a와 b가 임원에 포함되지 않을 경우의 수를 구하시오.
a, b를 고려하지 않고, 나머지 나머지 8명 중에서 3명을 뽑는다. 따라서 8C3 로 구할 수 있다.

3. a, b 중 적어도 1명이 C 안에 포함되도록

여 사건으로 구한다. 전체 경우의 수에서, a와 b가 모두 포함되지 않을 경우의 수를 빼면 구할 수 있다.

4. n명 중 악수하는 방법의 수

악수는 2명이서 하므로, 전체 n명 중에서 2명을 뽑으면 구할 수 있다.

Q. 5명이 서로 악수하는 경우의 수를 구하시오.
5C2 = 10, 10가지이다.

5. 도형의 개수

1. 직선의 개수 => nP2, 세 점이 일직선일 경우 중복을 삭제
2. 삼각형의 개수 => nP3, 세 점이 일직선일 경우는 삼각형 x, 삭제
3. 직사각형의 개수, 정사각형의 개수, 평행사변형의 개수.....