2019년 11월 8일

최은진의 노베부터 시작하는 확통 20 – 08강 분할과 분배

자연수의 분할

1) 자연수 n을 k개의 자연수의 합으로 쪼갠다 : P(n,k) (Partition)
2) P(n,1) = 1 P(n,n) = 1

문제: 자연수 8을 4개의 자연수로 분할하는 방법의 수를 구하시오.
P(8,4) => 내림차순으로 수작업!
8 = 5+1+1+1
= 4+2+1+1
= 3+3+1+1
= 3+2+2
= 2+2+2+2
이것은 4의 분할과도 같음. 작은 숫자(8보단 4)가 더 쉬움.
4 = 3+1, 2+2 = 2+1+1 = 1+1+1+1
언제쓰냐? 앞의 숫자가 크고, 몇개로 분할하는지 정해야함.

문제: 서로 같은 종류의 7개의 공과 3개의 상자가 있다. 공을 상자에 모두 나누어 넣으려고 할 떄, 빈 상자가 없도록 넣는 방법의 수를 구하시오.
자연수 분할. P(7,3)과 같음.
4의 분할과 같음(7-3 = 4) => 5가지

문제: 자연수 11을 3이상 7이하의 자연수로 분할하는 방법의 수를 구하시오.
수작업.
11 = 7+4
= 6+5
= 5+3+3
= 4+4+3
= 3+3+3+2… =>안됨
즉, 4가지

자연수의 분할: 자연수의 분할은 서로 같은 공을 서로 같은 종류의 상자에 넣는 방법의 수!

집합의 분할
ex) {1,2,3,4}인 집합을 서로소인 두 부분집합으로 쪼개는 방법 (공집합은 안됨)
(1) 자연수 분할 -> 4 = 3+1 (^4C_2) = 2+2 (^4C_2 * \frac{1}{2!}) => 이게 중요!
(2) 조합을 이용해서 집합의 분할을 함.
즉, 원소의 개수가 n개, 몇 개의 부분 집합의 (서로소)합
=> S(n,k)으로 표기

문제: 집합의 분할의 수 S(4,3)의 값을 구하시오.
(1) 4를 자연수 분할을 함. 즉, 2+1+1 밖에 가능하지 않음.
(2) ^4C_2 \ast ^2C_1 \ast \frac{1}{2!} (위에서 1+.. 이 두개, 즉 같은 종류가 두개를 섞는 것을 나눠줘야 함.)
답: 6

문제: 서로 다른 종류의 7개의 공과 같은 종류의 상자 3개가 있다. 공을 상자에 모두 나누어 넣으려고 할 때, 빈 상자가 없도록 넣는 방법의 수를 구하시오.
{1,2,….,7} 이 있고, 세 묶음으로 나누어 넣는다고 생각한다.
(1) 7을 3개로 분할 = 5+1+1, 4+2+1, 3+3+1, 3+2+2
(2) 5+1+1 은 1+1이 같은 종류이므로, ^7C_5 \ast ^2C_1 \ast \frac{1}{2!}
4+2+1은 그냥 ^7C_4 \ast ^3C_2 \ast ^1C_1
3+3+1은 3+3이 같은 종류이므로 ^7C_3 \ast ^4C_3 \ast ^1C_1 \ast \frac{1}{2!}
3+2+2은 2+2이 같은 종류이므로 ^7C_3 \ast ^4C_2 \ast \frac{1}{2!}
= 21 + 35*3 + 35*2 + 35*3 = 301