순열
n가지의 물건 중 r개의 물건을 순서 구분하여 고르는 경우의 수
\({}_{n}\mathrm{P}_{r} = \underbrace{n \times (n - 1) \times \cdots \times (n - (r - 1))}_{r\text{ numbers}} = \frac{n!}{(n - r)!} \quad(0 \le r \le n)\)
- \({}_{n}\mathrm{P}_{n} = n!\)
- \({}_{n}\mathrm{P}_{0} = 1\)
중복순열
n가지의 물건 중 중복을 허용하여 r개의 물건을 순서 구분하여 고르는 경우의 수
\({}_{n}\mathrm{\Pi}_{r} = \underbrace{n \times n \times \cdots \times n}_{r\text{ numbers}} = n^{r} \quad (0 \le r \le n)\)
같은 것이 있는 순열
n가지의 물건 중 같은 물건이 각각 p, q, r개일 때, n개의 물건을 모두 택하여 순서 있게 고르는 경우의 수
\(\frac{n!}{p!q!r!} \quad (p + q + r = n)\)
원순열
n가지의 물건 중 r개의 물건을 원형으로 배열하는 경우의 수
\(\frac{{}_{n}\mathrm{P}_{r}}{r} \quad (0 \le r \le n)\)
조합
n가지의 물건 중 r개의 물건을 순서 구분 없이 고르는 경우의 수
\({}_{n}\mathrm{C}_{r} = \frac{{}_{n}\mathrm{P}_{r}}{r!} = \frac{n!}{r!(n - r)!} \quad (0 \le r \le n)\)
- \({}_{n}\mathrm{C}_{0} = {}_{n}\mathrm{C}_{n} = 1\)
- \({}_{n}\mathrm{C}_{r} = {}_{n}\mathrm{C}_{n - r}\)
- 파스칼의 삼각형 : \({}_{n}\mathrm{C}_{r} = {}_{n - 1}\mathrm{C}_{r - 1} + {}_{n - 1}\mathrm{C}_{r}\)
중복조합
n가지의 물건 중 중복을 허용하여 r개의 물건을 순서 구분 없이 고르는 경우의 수
\({}_{n}\mathrm{H}_{r} = {}_{n + r - 1}\mathrm{C}_{r}\)
이항정리
N이 양의 정수일 때, \((a + b)^{n}\) 을 전개하면 아래와 같은 식으로 정리된다.
\((a + b)^{n} = {}_{n}\mathrm{C}_{0}a^{n} + {}_{n}\mathrm{C}_{1}a^{n - 1}b + {}_{n}\mathrm{C}_{2}a^{n - 2}b^{2} + … + {}_{n}\mathrm{C}_{k}a^{n - k}b^{k} + … + {}_{n}\mathrm{C}_{n}b^{n}\)
이것을 이항정리라 하고, \((a + b)^{n}\) 을 전개했을 때 각 항들의 계수를 이항계수라고 한다.
이항계수를 아래 그림과 같이 삼각형으로 배열한 것을 파스칼의 삼각형이라고 한다.
728x90
반응형
'알고리즘 > 조합론' 카테고리의 다른 글
| [백준] 1722번 순열의 순서 (JAVA) (0) | 2023.03.08 |
|---|---|
| [백준] 1256번 사전 (JAVA) (0) | 2023.03.07 |
| [백준] 1010번 다리 놓기 (JAVA) (0) | 2023.03.06 |
