원소의 개수가 n개인 집합 A에 대하여,

• 1. 특정 원소 k개를 반드시 원소로 갖는 부분집합의 개수:
  → 2^n-k 개 (단, k < n)
• 2. 특정 원소 k개를 원소로 갖지 않는 부분집합의 개수:
  → 2^n-k 개 (단, k < n)
• 3. 특정 원소 k개는 반드시 원소로 갖고, 특정 원소 l개는 원소로 갖지 않는 부분집합의 개수:
  → 2^n-k-l 개 (단, k+l < n)

핵심은 조건이 걸린 원소들을 미리 제외하고, 나머지 원소들로 만들 수 있는 부분집합의 개수를 세는 것이에요!

개념정리 149-1: 나머지 원소들의 선택!

원소의 개수가 n개인 집합 A의 부분집합을 만들 때, 각 원소마다 부분집합에 ‘포함될 것인가(O)’ 또는 ‘포함되지 않을 것인가(X)’의 두 가지 선택이 있다고 했죠? 그래서 부분집합의 총개수는 2ⁿ개였어요.

이제 특정 원소에 조건이 붙는 경우를 생각해 봅시다.

• 특정 원소 k개를 반드시 포함해야 한다면?
  그 k개의 원소는 이미 부분집합에 ‘포함(O)’으로 선택이 결정된 것이나 마찬가지예요. 우리는 그 k개의 원소를 제외한 나머지 (n-k)개의 원소들에 대해서만 ‘포함(O)’ 또는 ‘미포함(X)’을 결정하면 됩니다. 따라서 이 경우 부분집합의 개수는 2^n-k개가 됩니다.
  예를 들어, 집합 {b, c}의 부분집합은 ∅, {b}, {c}, {b,c} 네 개인데, 여기에 반드시 포함되어야 하는 원소 a를 추가하면 {a}, {a,b}, {a,c}, {a,b,c}가 되는 것과 같아요.
• 특정 원소 k개를 반드시 포함하지 않아야 한다면?
  그 k개의 원소는 이미 부분집합에 ‘미포함(X)’으로 선택이 결정된 것이죠. 우리는 그 k개의 원소를 제외한 나머지 (n-k)개의 원소들로 만들 수 있는 부분집합의 개수를 세면 됩니다. 이 역시 2^n-k개가 됩니다.
  예를 들어, 집합 A={a,b,c}에서 a를 원소로 갖지 않는 부분집합은, A에서 a를 제외한 집합 {b,c}의 부분집합(∅, {b}, {c}, {b,c})과 같아요.

결국, 조건이 주어진 특정 원소들은 그 선택이 이미 정해진 것으로 보고, 나머지 원소들로 만들 수 있는 부분집합의 개수를 세는 것이 핵심 원리랍니다!

개념정리 149-2: n-k, n-k-l을 지수에!

원소의 개수가 n개인 집합 A에 대하여 다음과 같은 경우들의 부분집합 개수를 공식으로 정리해 봅시다.

1. 특정 원소 k개를 반드시 원소로 갖는 부분집합의 개수

전체 n개의 원소 중에서 이미 포함하기로 결정된 k개의 원소를 제외한 나머지 (n-k)개의 원소들로 만들 수 있는 부분집합의 개수와 같아요.

2^n-k 개

2. 특정 원소 k개를 원소로 갖지 않는 부분집합의 개수

전체 n개의 원소 중에서 포함하지 않기로 결정된 k개의 원소를 제외한 나머지 (n-k)개의 원소들로 만들 수 있는 부분집합의 개수와 같아요.

2^n-k 개

(놀랍게도 1번 경우와 개수가 같죠? )

3. 특정 원소 k개는 반드시 원소로 갖고, 다른 특정 원소 l개는 원소로 갖지 않는 부분집합의 개수

전체 n개의 원소 중에서 포함하기로 결정된 k개와 포함하지 않기로 결정된 l개를 모두 제외한 나머지 (n-k-l)개의 원소들로 만들 수 있는 부분집합의 개수와 같아요.

2^n-k-l 개