[이산수학] 일대일대응을 이용한 경우의 수 세기

이번 포스팅 주제는 두 집합 사이의 일대일대응 관계를 이용하여 경우의 수 세기 이다.

 

이산수학에는 뭘 세는 문제가 많이 나온다.

그런데 세는 게 쉬우면 문제로 안내겠지. 그 문제를 일반적인 방법으로 세는 게 어려우니

다른 쉬운 방법을 통해서 세어서 문제를 푼다.

 

구체적인 예시를 들어서 보자.

1. 세 숫자 1, 2, 3 중에서 중복을 허락하여 7개의 숫자를 뽑는 방법의 수 2. 똑같은 공 7개를 서로 다른 3개의 상자 X, Y, Z에 넣는 방법의 수 3. 방정식 a+b+c=7의 음이 아닌 정수해 (a, b, c)의 개수 4. 7개의 ㅇ과 2개의 ㅣ를 일렬로 배열하는 방법의 수 5. 1, 2, 3, 4, 5, 6, 7, 8, 9 중에서 서로 다른 7개의 숫자를 뽑는 방법의 수

 

고등학교 수준의 쉬운 확통 문제니 다들 답은 쉽게 구할 수 있을 것이다.

위 5개의 문제의 답은 모두 ${}_3{\mathrm{H}}_7$로 같다. 

즉, 5개 문제의 답에 해당하는 각각의 경우의 집합에 대해

서로 일대일대응이 존재한다는 말이다.

 

만약 4번 문제가 풀라고 주어졌다. 그런데 난 4번은 못풀겠어. ㅇ과 ㅣ를 일렬로 배열하는거 너무 어려워ㅠㅠ

하지만 난 3번은 풀 수 있어. 그리고 3번과 4번이 가만 생각해보니 일대일대응관계가 있는거같아.

그러면 3번의 답이 곧 4번의 답인거니,까 4번도 풀 수 있게 되는 것이다.

 

그니까, 어떤 문제 상황이 주어졌는데 어려워서 못풀겠을 때,

그 상황과 동일한(일대일대응이 존재하는) 다른 상황(더 쉬운, 단순한 상황)을 가정하여 문제를 풀면 된다는 말이다.

 

한마디로 문제가 주어지면 우리 머릿속에 있는 개념들 중에서

그 문제 상황과 일대일대응이 존재하는 것을 골라서 대입하면 된다.

 

사실 우리는 고등학교 확통에서도 이 방법을 줄곧 사용해왔다. 인지하지 못했을 뿐.

 

이산수학에서 문제가 복잡해질 수록 일대일대응을 이용하는 경우가 많아서

굳이 하나의 게시물로 다뤄보았다.

 

 

다음 포스팅에서는 이항계수, 이항정리와 관련된 일부 개념을 알아보겠다.