partition

\( \newcommand{\rbinom}[2]{\left\langle\!{{#1}\atop{#2}}\!\right\rangle} \newcommand{\secondstirlingnum}[2]{\left\{\!{{#1}\atop{#2}}\!\right\}} \newcommand{\firststirlingnum}[2]{\left[\!{{#1}\atop{#2}}\!\right]} \) 상자에 공을 담는 문제를 살펴보자 해보자. 여기서는 \(8\)가지의 경우를 살펴볼 것이다. 즉 공의 구별 여부, 상자의 구별 여부, 그리고 비어 있는 상자의 가능 여부에 따른 셈하기를 살펴볼 것이다. 구별되지 않는 \(r\)개의 공을 구별되지 않는 \(n\)개의 상자에 담을 때, 빈상자가 없도록 담는 경우의 수는? \(\rightsquigarrow\) 이는 어떤 의미에서는 쉽다고 말 할 수 있겠으나, 이를 쉽다고 여길…

자연수 \(r\)의 분할(partition)이란, 합하여 \(r\)이 되는 자연수들의 모임이다. 만일 \(n\)개의 자연수를 합하여 \(r\)을 만들었다면, '\(r\)이 \(n\)개의 부분(part)들로 분할되었다'라고 말한다. 예를 들어, \(5\)는 \(7\)개의 분할, \( 5;\, 4+1,\ 3+2;\, 3+1+1,\ 2+2+1;\, 2+1+1+1;\, 1+1+1+1+1, \) 을 갖는다. \(5\)의 분할을 셀 때, 예를 들어 \(3+2\)와 \(2+3\)은 동일한 것으로 여긴다는 것에 유의하자. 또한 \(5\)를 한 개의 부분으로 분할하는 방법은 한 가지; \(5\)를 두 개의…