이산수학 11. 조합적 증명과 개수 세기(Counting)

안녕하세요 블레이즈입니다. 

조합적 증명은 조합적 논증이라고도 합니다. 

하나의 문제 상황을 두 개의 스토리 라인으로 푸는 방식이라고 보면 되는데요, 아래의 1번 문제를 보시면 이해가 편할 것 같습니다. 

 

첫 번째 문제입니다. 조합적 증명으로 풀이하라고 해서 그 방식으로 풀어봤습니다. 

 

저는 이렇게 목표를 먼저 쓰고 풀이하는 걸 선호합니다. 

 

n명으로 구성된 위원회를 만들어야 하는데 위원회장은 반드시 수학교수이가 되려면 그 경우의 수는 총 몇가지일까요? 

이를 두 개의 방법으로 풀어보겠습니다.

첫 번째 방법은 위원회에 포함될 수학 교수의 인원수 먼저 정하고 나머지 인원을 컴퓨터공학과 교수 중 뽑는 방법입니다. 

이 때, 수학 교수가 k 명이라면 위원회장을 뽑을 경우의 수는 k가 되겠죠. 

두 번째 방법은 위원회장이 될 수학교수를 먼저 뽑은 다음, 위원회의 멤버를 수학과 교수, 컴퓨터공학과 교수 구분하지 않고 무작위로 뽑는 방법입니다.

논리적으로 방법1과 방법2의 경우의 수는 동일해야 할 것입니다. 

이것이 바로 조합적 증명 풀이법이라고 할 수 있습니다. 

 

 

 

 

두 번째 문제입니다. 저는 non-empty set S의 원소의 개수가 짝수일 때와 홀수일 때로 나눠서 풀었습니다. 

 

비어있지 않은 집합의 부분집합에 대하여 

원소의 개수가 홀수인 부분 집합과 짝수인 부분 집합의 개수가 동일함을 보여라. 

 

 

감사합니다. 

블레이즈 테크 노트