분할 개념정리+공식

[성지훈]

지난 번 교육과정이 개정될 때 추가된 분할과 분배 단원의 개념입니다. 이 개념은 제가 학생이었을 당시에 배우지 않은 내용이라 개정된 후에 고등학교 교재를 보며 스스로 정리한 것입니다. 오류가 있을 가능성이 있음을 미리 밝히며 혹 제가 서술한 내용중 잘못된 부분이 있다면 꼭 지적해주시길 부탁드립니다. 분배는 간단하므로 분할에 집중해서 서술합니다.

1. 기본 분할.

분할이란 몇 개의 물건(또는 사람)을 몇개의 통(또는 조)에 나눠 담는 경우의 수에 대한 개념입니다.

간단한 예로 5명의 사람을 3개조로 나누는 방법은 총 몇가지인가? 라는 문제를 생각해봅시다.

우선 조 자체에 이름이 없으므로 조(또는 통)끼리는 서로 구분이 없는 경우 입니다.

반면 조원이 될 사람(또는 물건)은 모두 다릅니다.

이런 경우 조를 구분하려면 첫째로 몇명씩 조가 될 것인지를 정해야합니다.

총 5명이므로 3개조를 만드려면 1명 1명 3명 또는 1명 2명 2명 의 두가지 방식이 있습니다.

1명 1명 3명의 경우

5명중에 1명을 고르는 경우의 수*남은 4명중 1명을 고르는 경우의 수*1(남은 3명은 자동결정)*1/2(먼저뽑은 1명 1명이 서로 바뀌어도 동일하므로)=5C1*4C1*1*1/2=10

1명 2명 2명의 경우

5명중에 1명을 고르는 경우의 수*남은 4명중 2명을 고르는 경우의 수*1(남은 2명은 자동결정)*1/2(뒤에뽑은 2명 2명이 서로 바뀌어도 동일하므로)=5C2*3C2*1*1/2=15

따라서 총 25가지가 가능합니다.

이것이 조합을 이용한 기본적인 분할개념입니다. 조원 수에 따라 조합을 이용해서 차례로 곱해준 후 조원수가 동일한 조끼리는 서로 바뀌어도 동일하기 때문에 조원수가 동일한 조가 n개 존재할 때 n!을 나눠주면 됩니다.

2. 집합의 분할.

스털링넘버에서 이니셜 S를 따와서 기호 S(n,k)로 표현합니다.

집합의 분할: 한 집합을 그 집합의 부분집합들의 합집합으로 표현하는 방법의 수

(쉽게 말해 서로 다른 것들을 서로 같은 통에 빈통없이 나눠담는 방법의 수)

S(n,k): 원소의 개수가 n개인 집합을 k개의 부분집합의 합집합으로 표현하는 방법의 수

(쉽게 말해 서로 다른 n개의 공을 서로 같은 k개의 통에 빈통없이 담는 방법의 수)

여기서 부가 조건은 부분집합중 공집합은 제외되고 부분집합끼리는 서로소여야 하며 각각의 분할 방법에서 표현된 합집합은 반드시 원래의 집합과 동일해야 한다는 것입니다.쉽게 말해 어떤 원소도 빠짐없이 중복없이 부분집합에 나눠 담으라는 뜻입니다. 여기서 중요한 것은 집합의 원소는 각기 다른 것들이고 집합기호끼리는 모두 동일하다는 것입니다. 그래서 위의 괄호 속의 표현으로 바꿔 이해할 수 있습니다.

예컨데 {a,b,c}라는 집합의 분할을 모두 구해봅시다.

1개로 분할하는 경우는 {a,b,c} 한가지 ==>S(3,1)=1

2개로 분할하는 경우는 {a}U{b,c}, {b}U{a,c}, {c}U{a,b} 세가지 ==>S(3,2)=3

3개로 분할하는 경우는 {a}U{b}U{c} 한가지 ==>S(3,3)=1

4개 이상으로 분할은 불가능

따라서 {a,b,c}의 분할은 위의 5가지.

한 걸음 더 나아가 S(n,k)에서 사용할 수 있는 기본적인 공식들을 살펴보겠습니다.

이해하기 쉽도록 서로 다른 n개의 공을 서로 같은 k개의 통에 빈통없이 담는 방법의 수로 설명합니다.

S(n,1)=1

서로 다른 n개의 공을 한개의 통에 빈통없이 담는 방법은 한 통에 다 담는 방법 뿐이므로 1가지입니다.

S(n,n)=1

서로 다른 n개의 공을 n개의 통에 빈통없이 담는 방법은 1개씩 넣는 방법 뿐이므로 역시 1가지입니다.

S(n,n-1)=nC2

통이 딱 1개 부족하므로 빈통없이 담으려면 어떤 통 1개에는 2개의 공을 넣어야합니다. 이 2개의 공만 결정하면 나머지는 자동결정되므로 n개의 공 중 같이 넣을 2개를 선택하는 방법인 nC2가지.

S(n,2)=2^(n-1)-1

이 공식은 수열에서 배우는 pq꼴 점화식이나 이항정리를 이용해서 유도할 수 있는 공식입니다.

여기서는 좀 더 간편한 이항정리를 이용해서 유도해드리겠습니다.

서로 다른 n개의 공을 두개의 통에 빈통없이 담는 방법은

(1개, n-1개) -> nC1가지

(2개, n-2개) -> nC2가지

...중략...

(n-1개,1개) -> nC(n-1)가지

따라서 nC1+nC2+...+nC(n-1) 가지인데 두 통을 바꾸어도 똑같은 경우 이므로 2를 나눕니다.

그런데 이항정리에서 nC0+nC1+nC2+...+nC(n-1)+nCn=2^n이고 nC0=nCn=1이므로

nC1+nC2+...+nC(n-1)=2^n-2 가 되고 2로 나눠주면 2^(n-1)-1 이란 공식이 유도됩니다.

S(n,k)=S(n-1,k-1)+k*S(n-1,k)

기본적으로 n의 값이 작을 수록 연산이 편하기 때문에 n의 값을 낮추기 위한 공식입니다.

서로 다른 n개의 공 중 하나인 a 라는 공을 생각해봅시다.

a 공은 통에 혼자 있을 수도 있고 다른 공과 함께 있을 수도 있습니다.

혼자 있을 경우 -> a 공 혼자 하나의 통을 차지했으므로 나머지 n-1개의 공으로 k-1개의 통을 채워야겠죠. 이 경우의 수가 S(n-1,k-1)입니다.

다른 공과 함께 있을 경우 -> a 공을 제외한 n-1개의 공으로 k개의 통을 채운 뒤 a 공을 k개의 통 중 하나에 추가해야겠죠. 이 경우의 수가 S(n-1,k)*k 입니다.

이 두가지 경우 외에는 없으므로 S(n,k)는 둘의 합으로 표현됩니다.

3. 자연수의 분할

파티션에서 이니셜 P를 따와서 기호 P(n,k)로 표현합니다.

​자연수의 분할: 어떤 자연수를 자연수들의 합으로 표현하는 방법의 수

(쉽게 말해 서로 같은 것들을 같은 통에 빈통없이 나눠담는 방법의 수)

P(n,k): 자연수 n을 k개의 자연수의 합으로 표현하는 방법의 수

(쉽게 말해 서로 같은 n개를 서로 같은 k개의 통에 빈통없이 나눠담는 방법의 수)

예컨데 자연수 3을 분할해봅시다.

1개로 분할하는 경우는 그냥 3 한가지==>P(3,1)=1

2개로 분할하는 경우는 1+2 한가지==>P(3,2)=1

3개로 분할하는 경우는 1+1+1 한가지==>P(3,3)=1

4개 이상으로 분할은 불가능

따라서 3의 분할은 총 3가지 입니다.

여기서 한 걸음 더 나아가기 위해 위의 괄호속의 표현을 이해하면 좋습니다.

위에 예를 든 3의 분할 중 P(3,2)는 1+2를 (1)+(1+1) 과 같이 생각할 수 있고 여기서 괄호를 통으로 생각하면 됩니다. 즉, P(3,2)는 서로 같은 3개를 서로 같은 2개의 통에 빈통없이 나눠 담는 방법의 수와 같고 좀 더 일반화 하면 P(n,k)는 서로 같은 n개를 서로 같은 k개의 통에 빈통없이 나눠담는 방법의 수와 같습니다.

이제 집합의 분할에서와 같이 기본적인 공식들을 살펴봅시다.

이해하기 쉽도록 서로 같은 n개의 공을 서로 같은 k개의 통에 빈통없이 담는 방법의 수로 설명합니다.

P(n,1)=1

서로 같은 n개의 공을 1개의 통에 담는 방법은 한 통에 다 담는 방법 뿐이므로 1가지.

P(n,n)=1

서로 같은 n개의 공을 n개의 통에 담는 방법은 1개씩 넣는 방법 뿐이므로 역시 1가지.

P(n,n-1)=1

1개의 통이 부족하므로 빈통없이 담으려면 1개의 통에는 2개의 공이 들어가야 합니다. 이 2개의 공만 결정하면 나머지는 자동결정되므로 서로 같은 n개의 공 중 같이 넣을 2개의 공을 선택하는 방법인 1가지(모두 같으므로).

P(n,2)=[n/2]

n이 홀수인 경우와 짝수인 경우로 나눠서 생각한 뒤 통합.

1. P(2k,2)의 경우

1+(2k-1)

2+(2k-2)

...중략...

(k-1)+(k+1)

k+k

(k+1)+(k-1)

...중략...

(2k-1)+1

에서 k+k 이후 굵게 표시한 줄부터 중복되므로 k가지.

2. P(2k+1,2)의 경우

1+2k

2+(2k-1)

...중략...

k+(k+1)

(k+1)+k

...중략...

2k+1

에서 k+(k+1)이후 굵게 표시한 줄부터 중복되므로 k가지.

즉, P(2k,2)=P(2k+1,2)=k 이므로 P(n,2)=n을 2로 나눈 몫=[n/2]

P(n,k)=P(n-k,1)+P(n-k,2)+...+P(n-k,k) (단, P(a,b)에서 a<b 인 경우는 불가능하므로 0)

집합의 분할과 마찬가지로 n의 값이 작을 수록 연산이 편하기 때문에 n의 값을 낮추기 위한 공식입니다. 이 공식은 주로 n개의 똑같은 블럭을 이용해서 설명되어 있으나 여기서는 그대로 공과 통을이용해서 설명하겠습니다.

n개의 똑같은 공을 k개의 통에 빈통없이 담기위해 일단 하나씩 넣습니다.

통에는 각각 1개씩 공이 이미 들어있으므로 빈통이 없다는 조건이 만족되었고 남은 n-k개의 공은 그 k개의 통들 중 마음대로 집어 넣을 수 있습니다.

남은 공을 1개의 통에 다 넣는 경우의 수는 P(n-k,1)

남은 공을 2개의 통에 분할해서 넣는 경우의 수는 P(n-k,2)

...중략...

남은 공을 k개의 통에 분할해서 넣는 경우의 수는 P(n-k,k)

에서 전체 경우의 수는 위 공식과 같이 도출됩니다.

-주의-

여기까지 배우게 되면 중복순열, 중복조합, 집합의 분할, 자연수의 분할 4가지 개념 사이에 혼동이 생기는 학생들이 많습니다.

명확히 구분짓자면 이렇습니다.

중복순열: 서로 다른 n개의 통 중 서로 다른 r개를 넣을 통을 중복허락해서 선택(빈통가능)=n파이r

-통을 뽑는 순서가 달라지면 들어가는 물건들이 다르므로 순서를 고려해야하는 순열개념-

중복조합: 서로 다른 n개의 통 중 서로 같은 r개를 넣을 통을 중복허락해서 선택(빈통가능)=nHr

-통을 뽑는 순서가 달라져도 들어가는 물건들이 같으므로 순서가 무관한 조합개념-

집합의 분할: 서로 같은 k개의 통에 서로 다른 n개를 빈통없이 담는 방법=S(n,k)

-집합의 원소(통에 넣을 물건)끼리는 다르고 집합기호(원소들을 담을 통)끼리는 동일-

자연수의 분할: 서로 같은 k개의 통에 서로 같은 n개를 빈통없이 담는 방법=P(n,k)

-1(통에 넣을 물건)끼리는 모두 같고 자리(통)의 구분도 무의미하므로 동일-

[김탁]

참 좋은 글 감사합니다.
읽고 지나기엔 많이 아까우니
워터마크라도 찍어
첨부파일로
널리 알리시면 좋겠네요.
물론 새로 워드작업이 필요하지
않을 때입니다.

[성지훈]

제가 그 정도까지 적극적이진 않아서요...ㅎㅎ
그냥 수년전에 블로그에 작성했던 글들 중 정리가 필요하다 생각하는 것들을 하나 둘 옮겨놨을 뿐입니다.
제 글임을 안 밝히셔도 상관없으니 맘껏 활용하시고 한 사람에게라도 도움이 된다면 좋겠습니다.