[math] Factorial(계승), Permutation (순열) & Combination (조합)

경우의 수를 세는 방법의 기본
Factorial, Permutation and Combination

Factorial (계승)

서로 다른 물건들을 모두 순서를 주어 나열할 수 있는 모든 경우의 수.

$$ n! = n\times(n-1)\times(n-2)\times\cdots\times1 $$

• Factorial function의 경우, domain이 natural number만 가능.
• Factorial function을 complex number의 domain으로 확장한 것이 아래의 Gamma function임.

$$ \begin{aligned}\Gamma(z)&=\int^\infty_0 x^{z-1} e^x dx, (\text{Re}(z)>0)\\&=(z-1)!, (\text{if }z\text{ is natural number})\end{aligned} $$

---

Permutation (순열)

서로 다른 물건들 중 몇 개를 골라 순서를 주어 나열한 경우의 수.

$$ n\text{P}r=\dfrac{n!}{(n-r)!} $$

• $n$개를 순서대로 세울 수 있는 모든 경우와 비교할 때, 선택되지 않은 것들 $(n-4)$개들은 순서를 고려할 필요가 없으므로 하나의 경우로 처리되어야 함.
• 때문에 분모에서 $(n-r)!$로 나누어줌.

---

Combination (조합)

서로 다른 물건들 중 몇 개를 골라 순서 없이 나열한 경우의 수를 조합(combination)이라고 한다.

 

$$ n\text{C}r=\left( \begin{matrix}n\\r\end{matrix} \right)=\dfrac{n!}{(n-r)!r!}=\left( \begin{matrix}n\\n-r\end{matrix} \right) $$

• 선택만 되면 되기 때문에 분모에 $k!$ 이 들어감.
• $r$개가 선택된 경우, $r$개가 놓일 수 있는 모든 순서를 1로 처리해야하므로.

---

Permutation with Repetition (중복순열)

Permutation이 중복을 허락하지 않는 것과 달리, 중복을 허용한 경우임.

즉, $n$개 중 $r$개를 중복을 허용하여 일렬로 나열하는 경우의 수를 의미.

$$ _n\Pi_r=n^r $$

• 일렬로 나열할 때, 각각의 자리에 $n$ 모두가 선택될 수 있으므로 $n^r$이 됨.

---

Combination with Repetition (중복조합)

Circular Combination 이라고도 불림.

서로 다른 $n$개의 물건에서 중복을 허락하여 $r$개를 선택하는 경우의 수.

• 중복해서 뽑기 때문에 $n<r$인 경우도 가능함.
• 결국엔 Combination이므로 Combination으로 바꾸어 풀 수 있음.

서로 다른 $n$개의 물건에서 중복을 허락하여 $r$개를 선택하는 경우의 수 는 다음과 같이 바꿔 생각할 수 있음.

• $r$개가 선택된다는 것은 $r$개의 같은 공 이라고 생각하고
• $n$개의 다른 물건은 $n$개의 다른 방이라고 생각하고
• $r$개의 같은 공을 $n$개의 다른 방에 배분하는 문제로 바꾸어 생각할 수 있음. (←방에 있는 공의 수는 결국 방에 해당하는 물건이 선택된 횟수임)

$r$개의 같은 공을 $n$개의 다른 방에 배분하는 문제:

• $n$개의 다른 방이라는 건 $n-1$개의 칸막이가 있는 것으로 생각할 수 있음.
• 위의 문제는 엄청나게 큰 공간에 $r+n-1$개의 칸막이가 놓일 수 있는 위치가 있고, 이 위치들 중 칸막이가 들어갈 $n-1$개를 고르는 문제가 됨.
• 즉, ${(r+n-1)}C{(n-1)}$이 모든 경우의 수임.

---

중복조합의 식

$$ \begin{aligned}n\text{H}r = \left(\left(\begin{matrix}n\\r\end{matrix}\right)\right)&={(n+r-1)}\text{C}{(n-1)}=\dfrac{(n+r-1)!}{(n-1)!r!}\\&={(n+r-1)}\text{C}{r}\\&=\dfrac{\Gamma(n+r)}{\Gamma(n)\Gamma(r+1)}\end{aligned} $$

 

$\text{H}$는 Homogeneous monomial 의 $H$를 따옴.