분할과 분배

분할과 분배 Pt. 2

이전글 이전글에 이어서 이번 글에서는 나머지 2가지 경우에서 공을 상자에 나눠담는 경우를 생각해 볼 것이다. 이전글에서 이어지는 내용도 일부 있으니 파트 1을 먼저 읽고 오는 것을 추천한다. 이 글에서는 상자를 구분할 수 없는 경우에 대해 알아본다. 공을 구분할 수 없고 상자를 구분할 수 없는 경우 $n$개의 같은 공을 $k$개의 같은 상자에 빈상자를 허용하지 않으며 넣는다고 하자. $i$번째 상자에 들어가는 공의 개수를 $n_i$라고 하면 다음과 같은 식이 성립할 것이다. $n_1+n_2+\cdots+n_k=n$, 여기서 $(n_i \geq 1)$, $(i=1, 2, 3, \cdots, k)$ 즉, $n$을 $k$개의 자연수의 합으로 나타내는 경우의 수와 같으며 이를 $p(n,\:k)$라고 한다. 여기..

분할과 분배 Pt.1

다음글 분할과 분배는 기본적으로 전체를 여러개의 소부분으로 나누는 문제이다. 이를테면 $n$개의 과제를 $k$명이 나눠가지는 경우의 수이다. 분할과 분배는 종류에 따라 8가지로 나뉜다. 공을 상자에 나눠담을 때 1.공을 구분할 수 있는가 2.상자를 구분할 수 있는가 3.빈상자가 있어도 되나이다. 이 8개의 조건이 모여 총 8개의 부분경우를 만든다. 이 글에서는 이중 4가지만을 다루겠다. 공을 구분할 수 있고, 상자를 구분할 수 있는 경우 $n$개의 구분되는 공을 $k$개의 구분되는 상자에 넣는 경우를 본다. 만일 빈 상자를 허용하는 경우, $n$개의 공은 각각 $k$개의 상자로 들어갈 수 있으며, 이는 각각의 공이 $k$개의 선택지를 가지고 있음을 말한다. 즉, 곱의 법칙에서 $k^n$임을 알 수 있다...