OSOK [723972] · MS 2017 · 쪽지

2017-04-23 19:53:38
조회수 4,255

집합의 분할

게시글 주소: https://orbi.kr/00011844281

옯 글에 집합의 분할 관련 글이 올라와 있길래 꿀팁 하나 적어드리고 갑니다.



 집합의 분할을 쉽게 구하는 법


S(n, 2)를 예시로 들어보도록 하겠습니다....

어떤 함수 f가 있는데 정의역이 1부터 n까지 공역이 1,2가 있습니다.

만약 치역 또한 1,2 라면, 정의역의 원소들이 1 이나 2에 적어도 하나씩은 대응되어야 합니다. 


이걸 전사함수라고 합니다.


이는 즉 집합을 2개로 분할해 원소 2개에 대응시키는 것이므로,

2!*S(n,2)라고 할 수 있겠네요.


과연 이런 함수의 갯수는 얼마나 될까요? 


포함배제의 원리를 통해 구해보도록 합시다. 

전체 함수의 갯수는 2n개 입니다. 근데 1이나 2중 한개만 치역으로 갖게되는 함수의 갯수는 2*1n=2개 이네요.


따라서, 2!*S(n,2) = 2n-2 이므로, S(n,2) = 2n-1-1개 입니다.


자 그럼 일반화를 해보도록 하겠습니다.

만약 함수 g를 가정하고, 정의역이 1부터 n까지가 있고, 공역이 1부터 k까지 있다고 가정합시다.


그럼 전사함수의 갯수는 k!*S(n,k)이겠고, 포함배제를 통해 구해본다면, 이러한 함수의 갯수는 kn-kC1*(k-1)n+kC2*(k-2)n-...............(-1)i*kCi*(k-i)n+.............입니다.


따라서 구하고자 하는 것은 포함배제를 이용해 구한 식을 k!으로 나눠주면 끝입니다.


반응이 좋으면 Ferror's diagram을 이용해 자연수의 분할 관련 된 것도 알려드릴게요!!





0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.