[DiscreteMath]조합이론

📚기본 계수법칙

어떤 사건이 일어날 경우의 수를 세는 문제를 계수문제라고 합니다.

📄계수의 곱셈법칙

두 사건 A, B가 일어날 경우의 수가 각각 N(A) = m, N(B) = n일 때, 사건 A, B가 동시에 일어날 경우의 수는 m x n 입니다.

\[N(A \times B) = N(A) \times N(B) = m \times n\]

📄계수의 덧셈법칙

두 사건 A, B가 일어날 경우의 수가 각각 N(A) = m, N(B) = n이고 A ∩ B = ∅ 일 때, 사건 A 또는 B가 일어날 경우의 수는 m + n 입니다.

\[N(A \cup B) = N(A) + N(B) = m + n\]

📄합집합의 크기

N(X)를 집합 X에 포함된 원소의 개수라 했을 때, 유한집합 A, B, C에 대해서 다음 규칙이 성립합니다.

\[N(A \cup B) = N(A) + N(B) - N(A \cap B)\]

\[\begin{align} & N(A \cup B \cup C) \\ & = N(A) + N(B) + N(C) - N(A \cap B) - N(B \cap C) \\ & \quad\quad -N(A \cap C) + N(A \cap B \cap C) \end{align}\]

📚순열

순열(permutation)은 객체의 집합에서 순서를 고려하여 객체를 배열하는 것입니다.

📍A, B, C, D 를 한 번씩만 이용하여 만들 수 있는 단어는 몇 가지인가?

4개의 문자를 중복없이 사용하여 일렬로 배열하면 4! = 4 x 3 x 2 x 1 = 24 가지 단어를 만들 수 있습니다.

📄순열

1 <= r <= n을 만족한는 n, r에 대해, n개의 원소를 갖는 집합에서 r개의 원소를 순서를 고려하여 뽑은 경우의 수는 다음과 같습니다.

\[P(n, r) = n(n - 1)(n - 2) ... (n - r + 1)\]

\[P(n, r) = \frac{n!}{(n - r)!}\]

📄중복집합의 순열

중복된 원소를 허용하는 중복집합의 크기가 n이고 그중에 중복된 원소의 개수가 p개, q개, … r개가 있을 때, n개 모두를 일렬로 배열하는 경우의 수는 다음과 같습니다.

\[\frac{n!}{p!q! ... r!}\]

📄중복순열

n개의 원소를 갖는 집합에서 중복을 허용하여 r개의 원소를 순서를 고려하여 뽑는 경우의 수는 다음과 같습니다.

\[n\prod{r} = n^r\]

📄원순열

n개의 원소를 갖는 집합의 모든 원소들을 원형으로 나열하는 경우의 수는 다음과 같습니다.

\[\frac{n!}{n} = \frac{n(n-1)!}{n} = (n - 1)!\]

📚조합

조합(combination)은 객체의 집합에서 순서를 무시하고 일부를 선택하는 방법입니다.

📍축구 경기에서 총 7개 팀이 참가했고 두 팀만이 결승에 올라간다면 결승에서 붙게 되는 두 팀을 선택하는 방법은?

7개 팀에서 순차적으로 두 팀을 고를 경우의 수 P(7, 2) = 7 x 6 에서 결승에 올라갈 팀이 서로 위치를 바꾸는 경우의 수 2! = 2를 나누어 줍니다.

\[\frac{P(7, 2)}{2!} = \frac{7 \times 6}{2} = 21\]

📄조합

0 <= r <= n을 만족한는 n, r에 대해, n개의 원소를 갖는 집합에서 r개의 원소를 순서 없이 뽑는 경우의 수는 다음과 같습니다.

\[C(n, r) = \frac{P(n, r)}{r!}\]

\[C(n, r) = \frac{n!}{r!(n - r)!}\]

📄이항정리

임의의 실수 x, y와 음이 아닌 정수 n이 주어졌을 때,

\[\begin{align} (x + y)^n &= \sum_{k = 0} ^{n} {C(n, k)x^{n - k}y^{k}} \\ &= C(n, 0)x^{n}y^{0} + C(n, 1)x^{n - 1}y^{1} + ... + C(n, n)x^{0}y^{n} \end{align}\]

📍(x+y)¹⁰의 전개식에서 x²y⁸의 계수를 구하시오.

\[C(10, 8) = C(10, 2) = \frac{10 \times 9}{2 \times 1} = 45\]

📚이산확률

확률은 어떤 사건이 일어날 것인지 혹은 일어났는지에 대한 가능성을 표현하는 방법입니다.

• 표본공간: 실험의 모든 결과의 집합
• 사건: 표본공간의 부분집합

📄수학적 확률

표본공간 S가 유한하며, 각각의 결과들이 나타날 가능성이 모두 동일하다고 했을 때, S의 부분집합 사건 E가 나타날 확률은 다음과 같습니다.

\[P(E) = \frac{|E|}{|S|}\]

이때 표본공간의 S의 모든 원소 s에 대해 다음 두 가지가 성립합니다.

\[\begin{gather} 0 <= P(s) <= 1 \\ P(\varnothing) = 0, \quad P(S) = 1 \end{gather}\]

표본공간 S의 사건 A, B에 대해 다음 사실이 성립합니다. 만약 A, B가 서로소이면, \(P(A \cup B) = P(A) + P(B)\)

📍하나의 주사위를 두 번 던졌을 때, 숫자의 합이 6일 확률을 구하시오.

• 표본공간: 36
• 사건: (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)

확률은 5/36 입니다.

📄조건부 확률

표본공간 S에 두 사건 A, B가 있고 P(B) > 0이라고 할 때, 사건 B가 일어났다는 가정하에 사건 A가 일어날 확률을 조건부 확률 P(A|B)라고 합니다.

\[P(A|B) = \frac{P(A \cap B)}{P(B)}\]

📍하나의 주사위를 두 번 던졌을 때, 두 눈의 합이 8이 나왔다고 할 때, 첫 번째 주사위의 눈이 홀수일 확률을 구하시오.

첫 번째 주사위의 눈이 홀수인 사건을 A, 눈의 합이 8인 사건을 B라고 했을 때,

• B = {(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)}

• A ∩ B = {(3, 5), (5, 3)}

• P(B) = 5 / 36
• P(A ∩ B) = 2/ 36

\[P(A|B) = \frac{P(A \cap B)}{P(B)} = \frac{2}{5}\]

📚점화식

n번째 항이 그 전의 항들로 표현됨으로써 귀납적으로 쉽게 구할 수 있는 경우 해당 수열을 점화식으로 표현할 수 있습니다. 점화식은 수열의 항 사이에서 성립하는 관계식을 말합니다. 주어진 수열의 점화식을 푼다는 것은 수열의 일반항인 a_n을 n에 관한 식으로 나타내는 것을 의미합니다.

수열 {a_i} = a₁, a₂, …, a_n, a_{n + 1}, …에서 a_{n + 1} = f(a_n) (단, n >= 1)를 만족하는 f를 수열 {a_n}의 점화식이라고 합니다.

📍피보나치 수열을 점화식으로 나타내시오.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

초기조건은 F₀ = 1, F₁ = 1으로 수열의 처음 두 개의 항으로 구성됩니다.

\[F_n = \begin{cases} 1 & (n = 0) \\ 1 & (n = 1) \\ F_{n - 1} + F_{n - 2} & (n > 1) \end{cases}\]

📚비둘기집 원리

비둘기집 원리는 비둘기의 수가 집의 수보다 많을 경우 적어도 한 개의 비둘기 집에는 2마리 이상의 비둘기가 들어가게 된다는 것을 의미합니다. k개의 상자에 k + 1개 이상의 물체를 넣게 되면 적어도 하나의 상자는 2개 이상의 물체를 포함하게 됩니다.

비둘기집 원리는 상자의 수보다 물체의 수가 많으면 적어도 두 물체는 같은 상자 속에 들어간다고 하지만, 물체의 수가 상자 수의 배수보다 클 때는 아래와 같은 일반화된 형태로 표현할 수 있습니다.

k개의 상자에 N개의 물체를 넣게 되면, 적어도 하나의 상자는 \(\lceil \frac{N}{k} \rceil\)개 이상의 물체를 포함하게 됩니다.