수학 공식 | 확률과 통계 > 분할

분할

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

$ p \neq q \neq r \ : \ \phantom{}_{n}\mathrm{C}_{p} \times \phantom{}_{n}\mathrm{C}_{q} \times \phantom{}_{n}\mathrm{C}_{r} $

$ 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!} $

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

집합의 분할

유한집합을 공집합이 아닌 서로소인 몇 개의 부분집합으로 나누는 것을 집합의 분할이라고 한다.

원소의 개수가 $ 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*}

집합의 분할의 수의 성질

$ S( n, \ 1 ) = 1 $, $ S( n, \ n ) = 1 $

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

자연수의 분할

자연수 $ 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*}

와 같이 나타내는 것을 자연수의 분할이라고 한다.

자연수 $ 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*}

자연수의 분할의 수의 성질

$ P( n, \ 1 ) = 1 $, $ P( n, \ n ) = 1 $

$ P( n, \ k ) = P( n-1, \ k-1 ) + P( n-k, \ k ) $

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