경우의 수

경우의 수는 더하고 곱하고 빼고 나누는 사측연산을 통해 구할 수 있다.

+ (더하기)

A or B; 두 사건 A, B가 동시에 일어나지 않을 때, A의 경우의 수 +B의 경우의 수

윗옷 3개 중 1개를 골라 입는 경우의 수

1 + 1 + 1 = 3 가지

* (곱하기)

A and B; 두 사건 A, B가 동시에 일어날 때, A의 경우의 수 * B의 경우의 수

- 동시에

윗옷 3개와 바지 2개를 매치하는 경우의 수

( 1 + 1 + 1 ) * ( 1 + 1 ) = 3 * 2 = 6 가지

- 연속해서

a 에서 b를 거쳐 c로 가는 방법.

a 에서 b로 가는 방법 2 가지 * b에서 c로 가는 방법 3 가지
( 1 + 1 ) * ( 1 + 1 + 1 ) = 2 * 3 = 6

- (빼기)

중복되는 경우의 수를 뺴준다.

집합을 생각하면 좀 더 쉽게 이해할 수 있다.

만약 집합 A와 B의 교집합이 공집합이 아니라면, A와 B의 합은 A의 B의 합집합이 아니다.

A도 B와의 교집합에 해당하는 부분을 가지고 있고, B또한 A와의 교집합에 해당하는 부분을 가지고 있기 때문에,

교집합에 해당하는 부분이 2배인 상태이다.

그러므로 A와 B의 합에서 교집합 부분을 한번 빼 주어야 한다.

A와 B의 합집합 = A + B - A와 B의 교집합

/ (나누기)

순서에 의미가 없는 경우의 수를 나눠준다

1. 같은 원소(a, a, a) 끼리의 순서

2. 순서가 이미 정해져 있을 때

경우의 수 체크포인트

1. 순서가 의미가 있나?

2. 중복 허용?

3. (원소는 서로) 같은 것? 다른 것?

순열: 서로 다른 n개의 원소 중 r개를 택해 순서있게 (자리 차별성 있게) 나열하는 경우의 수.

이를테면 영희, 철수, 맹구를 한 줄로 세우는 경우의 수를 말한다.

3! = 3*2*1 = 6

1 (영희 철수 맹구)   2 (영희 맹구 철수)

3 (철수 영희 맹구)   4 (철수 맹구 영희)

5 (맹구 영희 철수)   6 (맹구 철수 영희)   총 6 가지.

중복순열: 순서 있게 원소를 나열한다는 점에서 순열이다. 순열과 다른 점은 중복을 허용하는 순열이라는 점이다. 이미 다른 자리에 배치한 원소라도 상관없이 또 다시 택할 수 있다는 뜻이다.

3번 연달아 동전 던지기를 한다고 해보자. 한번 던질 때 앞면 또는 뒷면이라는 결과를 얻을 수 있다. 두 번째로 던질 때 또 앞면 또는 뒷면이라는 결과를 얻을 수 있고, 세번째도 마찬가지로 이전에 어떤 결과를 얻었든지 앞면 또는 뒷면 중 하나의 결과를 얻을 수 있다.

따라서 동전을 3번 던졌을 때, 얻을수 있는 경우의 수는 2*2*2 = 2**3 = 8이다.

1 (앞면 앞면 앞면)  2 (앞면 앞면 뒷면)

3 (앞면 뒷면 앞면)  4 (앞면 뒷면 뒷면)

5 (뒷면 앞면 앞면)  6 (뒷면 앞면 뒷면)

7 (뒷면 뒷면 앞면)  8 (뒷면 뒷면 뒷면)   총 8가지

조합: 서로 다른 n개의 원소 중 r개를 순서 고려하지 않고 뽑는 경우의 수 이다.

동그랑땡, 깻잎전, 동태전, 고추전이 각 1개 씩 남아 있는데, 이 중 내 몫 2개를 골라 먹을 수 있다면, 조합을 사용해서 경우의 수를 계산해 볼 수 있다.

(동그랑땡 깻잎전), (동그랑땡 동태전), (동그랑땡 고추전)

(깻잎전 동그랑땡), (깻잎전 동태전), (깻잎전 고추전)

(동태전 동그랑땡), (동태전 깻잎전), (동태전 고추전)

(고추전 동그랑땡), (고추전 깻잎전), (고추전 동태전)   총 12/2 = 6 가지

중복조합: 서로 다른 n개의 원소 중 중복허용해서 r개를 뽑는 경우의 수 이다.

충분한 양의 동그랑땡, 깻잎전, 동태전, 고추전이 있어서, 내 몫 2개를 고를때 동그랑 땡만 2개 골라도 괜찮다면, 중복조합으로 내 몫 2개를 고르는 모든 경우의 수를 계산해 볼 수 있다.

( (4+2-1)*(4+2-2) ) / 2 = 10

	순서	중복	formula
순열	O	X	nPr = n! / r!
원순열	O	X	nPr = nPr * 1/n
중복순열	O	O	nㅠr = n ** r
같은 것이 있는 순열	O	X	모든 것! / 같은 것!
조합	X	X	nCr = nPr / r!
중복조합	X	O	nHr = n-1+r Cr