경우의 수 공식

순열

$\displaystyle _{n}P_{r} = \frac{n!}{(n-r)!}$

서로 다른 n개에서 r개를 택해
일렬로 나열하는 경우의 수

 

중복순열

$\displaystyle _{n}\Pi_{r} = n^{r}$

중복을 허용하여
서로 다른 n개에서 r개를 택해
일렬로 나열하는 경우의 수

 

같은 것이 있는 순열의 경우
그 수 만큼 계승을 나눈다.
ex. $\frac{n!}{p!q!\cdots r!}$

---

조합

$\displaystyle _{n}C_{r} = \frac{_{n}P_{r}}{r!} = \frac{n!}{r!(n-r)!}$

서로 다른 n개에서
순서를 무시하고 r개를 택하는 경우의 수

$_{n-1}C_{r-1} + _{n-1}C_{r} = _{n}C_{r}$
$_{r}C_{0} + _{r+1}C_{1} + _{r+2}C_{2} + \cdots + _{n}C_{n-r} = _{n+1}C_{n-r}$

$_{r}C_{r} + _{r+1}C_{r} + _{r+2}C_{r} + \cdots + _{n}C_{r} = _{n+1}C_{r+1}$

중복조합

$\displaystyle _{n}H_{r} = _{n+r-1}C_{r}$

서로 다른 n개에서
중복을 허락하여 r개를 태하는 경우의 수

 

x+y+z ≤ 10의 경우의 수는
x+y+z+w = 10으로 $_{4}H_{10}$을 계산하면 된다.

---

함수의 개수

정의역의 개수를 a,
공역의 개수를 b라 하면

전체 f 가짓수는 $b^{a}$이고
상수함수의 경우 b가지이다.

$x_{1} \neq x_{2} → f(x_{1}) \neq f(x_{2})$인
일대일 대응 함수의 가짓수는 $_{b}P_{a}$이다.

$x_{1} < x_{2} → f(x_{1}) < f(x_{2})$의 경우
순서가 정해진 배열과 같으므로 $_{b}C_{a}$이다.

$x_{1} < x_{2} → f(x_{1}) ≤ f(x_{2})$의 경우
순서가 정해진 배열과 같으므로 $_{b}H_{a}$이다.