확률 - 순열 / 조합 / 이항정리
1. 순열 (Permutation)
순열은 순서대로 배열하는 방법을 뜻한다.
순서 를 고려해야한다는게 중요하다.
주어진 원소를 어떤 순서로 배열할 수 있는지 계산을 해야하는데,
숫자 1, 2, 3이 있다고 할때 이들을 배열한는 방법은 아래와 같이 6 가지 이다.
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
중복되는 숫자가 없으므로, 계산할 경우 6 가지 이다.
이유는, 첫번째 자리에 3가지 숫자 중 하나를 놓을 수 있고 (1,2,3), 두번째 자리는 그 외에 두개, 마지막 자리에 한개를 놓을 수 있어서.
3 x 2 x 1 = 6가지이다.
이걸 팩토리얼로 표현하자면, 3! 으로도 표현한다.
Factorial (팩토리얼) n!은 1부터 n까지의 모든 수를 곱한 값 이다.
순열도 위의 내용과 상당히 관련이 있다.
반에 학생이 30명이고, 반장 부반장을 뽑는다고 하자 그러면 총 경우의 수는 몇인가?
30명중에 반장을 뽑으면, 29명이 남고 거기서 부반장을 뽑아야 한다.
이걸 순열에서 공식으로 쓰면 30P2 이라고 한다.
30명 중에 2명을 뽑는다는거고 P는 Permutation의 약자인다.
팩토리얼을 적용해서 공식을 보면 아래와 같다.
$$ nPr = \frac{n!}{(n-r)!} $$
예제를 추가하면, 전체학생 30명 (n = 30), 반장 부반장 2명 (r = 2) 로 계산한다.
그러면 아래처럼 나오는데 아래에서 1~28까지 곱하는건 분자/분모로 제외하고 남는게 29x30만 남는다.
$$ 30P2 = \frac{30!}{(30-2)!} = \frac{30!}{28!} $$
즉 30P2 = 30 x 29 = 870 이 된다.
정리하자면, 순열은 일정 원소들을 순서대로 세웠을 때 이다.
반장 부반장도, 반장을 세우고 부반장을 세워서 순열을 사용했다.
예제 1: 6P3 - 3P3 + 3P0 x 3!
- (6x5x4) - (3x2x1) + 1 x (3x2x1) = 120 + 6 - 6 = 120
* 3P0 은 아무것도 선택하지 않는다라는 걸 선택했기 때문에 1가지 방법이 있다.
예제 2: kP1 + kP2 = 36, k = ?
$$ kP1+kP2=k+k⋅(k−1)kP1 + kP2 = k + k \cdot (k - 1)kP1+kP2=k+k⋅(k−1) $$
$$ k+k⋅(k−1)=36k + k \cdot (k - 1) = $$
$$ 36k+k⋅(k−1)=36 k+k2−k=36k + k^2 - k = $$
$$ 36k+k2−k=36 $$
$$ k2=36k^2 $$
$$ 36k2=36 $$
$$ k=36=6k = \sqrt{36} = 6k=36=6 $$
$$ k=6k $$
$$ k=6 $$
예제 3: A,B,C,D를 모두 일렬로 나열할때 A가 제일 마지막에 오도록 나열하는 방법의 수
- 마지막 자리가 정해졌다 x,y,z,A 그리고 x에는 3개중 하나, y는 2개중 하나, z는 한개가 올수 있다.
- 즉 3! 혹은 3P3이 되어서 6가지 이다.
예제 4: POWER에서 P와 R을 이웃하게 나열하는 방법의 수
- PR이 나열되야하니까 이걸 그냥 하나의 자릿수로 본다.
- 즉 4P4 = 24인데, RP도 역시 이웃되는 방법이니 4P4 + 4P4 해서 48 이다.
예제 5: 0,1,2,3,4의 숫자 중에 각각 다른 3장을 뽑아서 3자리 자연수를 만드는데 그중 짝수의 갯수는?
- 일의자리가 0, 2, 4가 올 경우가 짝수일 경우 이다.
- 다만, 0이 백의 자리에 갈 수 없는 경우를 고려해야한다.
- 일의자리가 0이될 경우는 일의자리에 0을 두고, 아무거나 2개를 더 뽑으면 되서 4P2 = 12가지 이다.
- 일의자리가 2 인 경우,백의자리가 0이 오면 안된다. 그래서 백의자리에는 3개중 하나가 올수 있고, 십의자리도 3개중 하나가 올 수 있다.
- 3x3 = 9
- 일의자리가 4인경우도 같게 9이다
- 12 + 9 + 9 = 30
2. 조합 (Combination)
조합은 순서에 상관없이 일정 개수의 원소를 선택하는 방법이다.
순열과 다르게 `순서`가 중요하지 않다.
순열은 뽑아서 순서대로 나열을 하는거라면,
조합은 그냥 뽑아서 주기만 하면 된다.
3개의 숫자 1,2,3에서 2개를 고른다.
첫번째에는 1,2,3 중에 하나가 올 수 있고, 두번째에도 1,2,3중에 하나가 올 수 있다.
로또를 생각해 보자.
로또 추첨기에서는 1 4 8 42 33 11 9 25 이렇게 순서에 상관없는 숫자들이 뽑힌다.
하지만 이 번호의 조합은 순서에 상관없이 1등을 가르킨다.
순열과 비교
- 순열 (Permutation):
- 순열은 순서가 중요한 경우를 세는 개념이다. 아무것도 뽑지 않아도 그 자체를 하나의 경우로 본다.
- 조합 (Combination):
- 조합은 순서를 신경 쓰지 않고 "몇 개를 뽑는다"는 게 중요한 개념이다.
조합은 Combination 의 약자를 따와서 nCr로 쓴다.
5C3이 있다고 하면 조합에선 5개중에 3개를 뽑는다는 의미다.
순열이 `뽑아서 나열한다` 이고 `조합은 뽑는다` 이므로
즉 순열 / 뽑은걸 나열하는 경우의수 = 조합 이다.
$$ nCr = \frac{nPr}{r!} $$
위의 순열을 풀면 아래처럼 만들 수 있다.
$$ nCr = \frac{n!}{r!(n−r)!} $$
조합의 성질 (중요)
8C7 = 8C1 이다.
이유는 8개중 7개를 뽑는다는건 8개중에 뽑지 않을 1개를 선택한다는거와 같은말 이기 때문이다.
즉 5C3 = 5C2 이다.
예제 1: 4C2 + 8C6 + 3C1 =
- 6 + 28 + 3 = 37
- 8C6 이런건 8C2로 계산해서 구하면 쉽다.
- 순열을 사용하면서 답을 구하자. (ex: 8C6 = 8P2 / 2!)
예제 2: k+1C4 = 2x kC4 k = ?
k = 7
예제 3: A,B,C,D,E 중 3개를 선택할때
- 모든 방법의 수?
- 5C3 = 5x4x3x2x1 / 3x2x1(2x1) 에서 하나씩 지워도 된다 = 10
- A는 선택하고 B는 선택하지 않는 경우의 수?
- B는 일단 뽑히면 안되고, A는 무조건 뽑아야하니, 전체 뽑아야하는공은 3개, 그리고 그 중에서 A는 이미 뽑았으니, 나머지 뽑아야하는공은 2개
- 즉, 3C2 = 3x2x1 / 2x1(1) = 3
3. 이항정리 (Binomial Theorem)
이항정리는 아래의 식을 전개하는 방법이라고 생각하면 편하다.
$$ (a+b)^n $$
일단 전개를 해보면 아래처럼 된다.
`a^n + a^n-1*b + a^n-2*b^2 + ... + b^n`... 이런식으로 간다.
(a + b)^2를 전개해보자.
`(a + b)^2 = a^2 + 2ab + b^2` 이렇다.
(a + b)^3를 전개해보자..
(a + b)(a + b)(a + b) 이렇게도 쓸수 있고, `(a + b)^3 = a^3 + 3a^2*b + 3a*b^2 + b^2` 가 된다.
`a^3 + 3a^2*b + 3a*b^2 + b^2` 여기서 각 항의 계수를 보자
`1 * a^3 + 3 * a^2*b + 3 * a*b^2 + 1 * b^2` => 즉 1, 3, 3, 1 이다.
왜 1, 3, 3, 1 이 되냐면,
(a + b)(a + b)(a + b) 이렇게 전개했을때,
1* a^3은 a를 3번 뽑는 경우의 수가 1 = aaa
3* a^2*b는 a 2번, b 1번 뽑는 경우의 수가 3 = aab
3* a*b^2는 a 1번, b 2번 뽑는 경우의 수가 3 = abb
1* b^2는 b를 3번 뽑는 경우의 수가 1 = bbb
이기 때문에 1, 3, 3, 1 이다.
몇개중에 몇개 뽑는다.. 라는 개념은 조합과 관련이 있기 때문에,
a를 3번 뽑는 경우의 수가 1 인걸 조합 공식으로 써보면 3C0 = 1
a 2번, b 1번 뽑는 경우의 수가 3 인걸 조합 공식으로 써보면 3C1 = 3
a 1번, b 2번 뽑는 경우의 수가 3 인걸 조합 공식으로 써보면 3C2 = 3
b를 3번 뽑는 경우의 수가 1인걸 조합 공식으로 써보면 3C3 = 1
이렇게 된다.
즉 식에 대입하면,
`3C0 * a^3 + 3C1 * a^2*b + 3C2 * a*b^2 + 3C3 * b^2` 이렇게 된다.
이제 이것을 일반화 해야한다 (중요)..
---
# 일반화
다시 `( a + b )^n` 이걸로 돌아가서, 위의 조합을 사용해서 식을 다시 써보자
`nC0 * a^3 + nC1 * a^n-1*b + nC2 * a^n-2*b^2 + nC3 * a^n-3b^3 + ... + nCn * b^n`
이걸 수열의 합의 기호인 시그마를 이용하면 아래처럼 표현할 수 있다.
```
n
∑ nCr * a^n-r * b^r
r=0
```
여기서 `nCr`이 이항계수이고,`nCr * a^n-r * b^r` 이 이항정리의 일반항 이라고 한다.
---
예제 1: (ax + 2/x)^5 에서 x^3 항의 계수가 160일때 a = ?
이항정리 공식에 대입을 해보자...지금으로서는, n = 5, a = ax, b = 2/x 밖에 모른다.
```
5
∑ 5Cr * ax^5-r * x/2^r = (ax + 2/x)^5
r=0
```
각 항을 계산해 보자..
이항정리의 일반항이 `nCr * a^n-r * b^r` 이거와 같기 때문에, 여기서 보면,
`5Cr * ax^5-r * x/2^r` 이러한 형태로 각 항들이 구성 된다.
이 항을 한번 해석해보면,
`5Cr`: 5개중에 r개 뽑는다 = 5개의 항 중에 r개를 선택한다.
`ax^5-r`: a와 x가 각각 5-r 만큼 곱해진다. 즉, a`^5-r _ x^5-r`로 나타낼 수 있다.
`x/2^r`: 2와 1/x가 각각 r번 곱해진다. 즉, `2^k * x^-r`가 된다.
따라서 위의 항들 다시 구성해보면,
`5Cr * a^5-r * x^5-r * 2^ r * x^-r` 이다.
x에 관한 지수를 합칠 수 있다. (`x^5-r 그리고 x^-r`)
그래서 결론적으로 `5Cr * a^5-r * 2^r * x^5-2r` 이다.
그런데 x^3 = 160을 주어줬으니, 우리는 `x^5-2r = x^3` 인걸 찾으면 되고,
`5-2r = 3` 에서 r이 1일때 x^3이 존재한다는걸 알 수 있다.
이제 식에 r=1을 대입한다.
`5C1 * a^4 * 2^1 * x^3`
= `5 * a^4 * 2 * x^3`
= `10 * a^4 * x^3`
근데 x^3 의 계수가 160 이므로,
= `10 * a^4 = 160`
= `a^4 = 16`
= `a = -2 or 2`
즉 a 는 2 혹은 -2 이다.