[모듈식 수학 (하)] 1. 집합과 명제 (7) 부분집합의 개수 + 특정한 원소

부분집합의 개수 + 특정한 원소

---

부분집합의 개수를 구하다 보면 이런 의문이 듭니다. 만약 어떤 원소를 반드시 포함하도록 한다면 부분집합의 개수는 어떻게 될까. 오늘날 우리들은 이런 의문을 가질 새 없이 지식을 계속 습득해야 하지만 돈 많고 시간 많고 호기심 많던 옛사람들은 이런 의문도 가졌을 거에요. 

말로만 설명해볼테니 한번 이해해봅시다. 상상력을 동원해서 우리 뇌를 성장시켜보죠. 어떤 집합 A가 있다고 해봅시다. A의 원소는 n개입니다. A의 부분집합의 개수는 입니다. 지난시간에 배웠습니다. A의 원수 n개 중에서 특정한 원소 k개를 반드시 포함하고 싶은 상황입니다. 좋은 아이디어가 있습니다. 먼저 k개의 원소를 빼놓겠습니다. 그럼 A의 원소는 n-k개가 됩니다. n-k개의 원소로 만들 수 있는 부분집합의 개수는 입니다. 이제 이 각각의 부분집합에다가 우리가 빼놓은 k개의 원소를 집어 넣어줍시다. 이렇게 하면 k개의 원소를 반드시 포함하는 A의 부분집합이 구해집니다. 

k개의 원소를 반드시 포함하는 A의 부분집합의 개수 : 

이번에는 집합 A에서 k개의 원소를 포함하지 않는 원소의 개수를 구해봅시다. 원소 k개를 빼고 부분집합을 구하면 되니까 가 됩니다. 재밌는 일이 벌어집니다. 집합 A에서 원소 k개를 반드시 포함하는 부분집합의 개수와 반드시 포함하지 않는 부분집합의 개수가 같습니다. 

이번에는 집합 A의 원소 중에서 특정한 k개의 원소 중 적어도 하나를 포함하고 싶었습니다. 전체 부분집합의 개수 중에서 특정 k개의 원소 중 단 하나도 포함하지 않는 경우를 빼면 되겠죠? 전체 부분집합의 개수는 개이도 특정 k개를 단 하나도 포함하지 않는 부분집합의 개수는 입니다. 이제 아래와 같이 계산해주면 됩니다. 

특정한 k개의 원소 중 적어도 하나를 포함하는 A의 부분집합의 개수 :