MATH FACTORY

서로 다른 $ n $개를 $ p $개, $ q $개, $ r $개로 나누는 방법의 수는 다음과 같이 구한다. (단, $ p+q+r=n $)

1. $ p \neq q \neq r \ : \ \phantom{}_{n}\mathrm{C}_{p} \times \phantom{}_{n}\mathrm{C}_{q} \times \phantom{}_{n}\mathrm{C}_{r} $
2. $ p = q \neq r \ : \ \phantom{}_{n}\mathrm{C}_{p} \times \phantom{}_{n}\mathrm{C}_{q} \times \phantom{}_{n}\mathrm{C}_{r} \times \dfrac{1}{2!} $
3. $ p = q = r \ : \ \phantom{}_{n}\mathrm{C}_{p} \times \phantom{}_{n}\mathrm{C}_{q} \times \phantom{}_{n}\mathrm{C}_{r} \times \dfrac{1}{3!} $

1. 유한집합을 공집합이 아닌 서로소인 몇 개의 부분집합으로 나누는 것을 집합의 분할이라고 한다.
2. 원소의 개수가 $ n $인 집합을 $ k $개의 부분집합으로 분할하는 경우의 수를 기호로
   \begin{gather*}
   S (n, \ k)
   \end{gather*}와 같이 나타낸다. (단, $ 1 \leq k \leq n $)

원소의 개수가 $ n $인 집합의 분할의 수는 $ n $개 이하의 부분집합으로 분할하는 경우의 수이다.

\begin{gather*}
S(n, \ 1) + S(n, \ 2) + S(n, \ 3) + \cdots + S(n, \ n)
\end{gather*}

1. $ S( n, \ 1 ) = 1 $, $ S( n, \ n ) = 1 $
2. $ S( n, \ k ) = S( n-1, \ k-1 ) + k S( n-1, \ k ) $

1. 자연수 $ n $을 자신보다 크지 않은 몇 개의 자연수 $ n_1 $, $ n_2 $, $ n_3 $, $ \cdots $, $ n_k $의 합으로
   \begin{gather*}
   n = n_1 + n_2 + n_3 + \cdots + n_k \ \ (n_1 \geq n_2 \geq n_3 \geq \cdots \geq n_k)
   \end{gather*}와 같이 나타내는 것을 자연수의 분할이라고 한다.
2. 자연수 $ n $을 $ k $개의 자연수로 분할하는 경우의 수를 기호로
   \begin{gather*}
   P (n, \ k)
   \end{gather*}와 같이 나타낸다. (단, $ 1 \leq k \leq n $)

자연수 $ n $의 분할의 수는 자연수 $ n $을 $ n $개 이하의 자연수로 분할하는 경우의 수이다.

\begin{gather*}
P (n, \ 1) + P (n, \ 2) + P (n, \ 3) + \cdots + P (n, \ n)
\end{gather*}

1. $ P( n, \ 1 ) = 1 $, $ P( n, \ n ) = 1 $
2. $ P( n, \ k ) = P( n-1, \ k-1 ) + P( n-k, \ k ) $
3. $ P( n, \ k ) = P( n-k, \ 1 ) + P( n-k, \ 2 ) + \cdots + P( n-k, \ k ) $