GATE CSE 1994 | Question: 2.4

Question

The number of subsets $\left\{ 1,2, \dots, n\right\}$ with odd cardinality is ___________

Comments

The case is same for even and odd cardinality i.e. 2^n-1

 

https://math.stackexchange.com/questions/1338787/number-of-subsets-with-even-number-of-elements

Answer 1

Answer: $2^{n-1}$

No. of subsets with cardinality $i = {}^nC_i$

So, no. of subsets with odd cardinality = $\sum_{i = 1, 3, \dots, n-1} {}^nC_i  \\ = 2^{n-1} \text{(Proof given below)} $

---

We have,

${}^nC_0+ {}^nC_1 + {}^nC_2 + \dots + {}^nC_n = 2^n$

${}^nC_0+ {}^nC_1 + {}^nC_2 + \dots + {}^nC_n  =\begin{cases} {}^{n+1}C_1+ {}^{n+1}C_3+ \dots +{}^{n+1}C_n, n \text{ is even }  \\ {}^{n+1}C_1+ {}^{n+1}C_3+ \dots +{}^{n+1}C_{n-1} +{}^{n}C_{n}, n \text{ is odd }  \end{cases}$

$\left(\because {}^{n}C_r + {}^{n}C_{r-1} = {}^{n+1}C_r \right) = 2^n$ 

$\implies \left.\begin{matrix} {}^{n}C_1+ {}^{n}C_3+ \dots +{}^{n}C_{n-1}, n \text{ is even} \\ {}^{n}C_1+ {}^{n}C_3+ \dots +{}^{n}C_{n}, n \text{ is odd} \end{matrix} \right\}= 2^{n-1}  \left(\text{ replacing }n \text{ by }n-1, {}^nC_n = {}^{n-1}C_{n-1} \right)$

---

Proof for ${}^{n}C_r + {}^{n}C_{r-1} = {}^{n+1}C_r$

${}^{n}C_r + {}^{n}C_{r-1}  = \frac{n!}{r! (n-r)!} +  \frac{n!}{(r-1)! (n-r+1)!}$

$=  \frac{ n! (n-r+1) + n! r} {r! (n-r+1)!}$

$= \frac {n! (n+1)}{r! (n-r+1)!}$

$= \frac{(n+1)!}{r! (n-r+1)! } = {}^{n+1}C_r$

Comments

I think the equation which you have written is wrong. It should be opposite.

nC0+nC1+nC2+⋯+nCn={n+1C1+n+1C3+⋯+n+1Cn, when n is odd

                                       =n+1C1+n+1C3+⋯+n+1Cn−1+nCn when n is even   }

---

Yes, Even I am also feeling the same

---

More intuitive approach:

Write the expansion of (1 + 1)^n ------------ Equation 1
Write the expansion of  (1 – 1)^n ------------- Equation 2
 

Then do Equation 1 – Equation 2. You will get 2^n on LHS and 2*(required expansion) on RHS. So, required expansion = 2^n / 2 = 2^(n – 1)

---

nvs16

Thanks!

Answer 2

For each subset it can either contain or not contain an element. For each element, there are 2 possibilities.So 2^n subsets but question is about odd cardinality, that makes it half of 2^n = 2^n/2 =   2^(n-1)

Comments

k, i will do that

---

if given a set A={2} containing only one element. Then its power set will be:

1. P(A) = {∅,{2}}
2. P(A) = {{∅},{2}} 

So my question is which one is correct 1 or 2?

---

1 is correct...

Answer 3

Cardinality of a set is number of elements in the set

The subsets of the set {1,2,3,4.................,n}

are {}- Even cardinality

{1}-Odd cardinality

{1,2}-Even cardinality

{1,2,3}- odd cardinality

.......................

So, in a set of n elements , number of subsets 2ⁿ

Among which exactly half is odd

So, no of subsets with odd cardinality 2ⁿ/2 = 2^n-1

Comments

@Srestha, Even the above argument would hold for even values??Isn't it??Am I correct Srestha??

---

yes ..

---

Thank you Srestha. :)

Answer 4

Answer is $2^{n-1}$

Using counting argument

Let the #subsets of odd cardinality be denoted by $f(n)$

We know that there are $f(n-1)$ subsets of odd cardinality for set of n-1 elements.
so there are $2^{n-1} - f(n-1)$ subsets of even cardinality for set of n-1 elements.

Now the nth element comes. Now it may or may not be included in the subsets we are counting.

So there are $f(n-1)$ subsets of odd cardinality that don't include nth element.
now we can include nth element in the original subset(that is subset from n-1 element) only if the original subset had even cardinality(so to make resultant subset of odd cardinality).

so $f(n) = f(n-1) + 2^{n-1} - f(n-1) = 2^{n-1}$
   
Intuitivaly half of the total subsets are of even cardinality. But those who believe in Bertrand Russell's quote Obviousness is the enemy of correctness may need this argument.

Comments

we can also use symmetry.

total no. of subsets possible=2^n.

no. of subsets with odd cardinality =no.of subsets with even cardinality=2^n/2=2^(n-1).