The Gateway to Computer Science Excellence
+17 votes
The number of subsets $\left\{ 1,2, \dots, n\right\}$ with odd cardinality is ___________
in Set Theory & Algebra by Veteran (52.1k points)
retagged by | 1.1k views

4 Answers

+16 votes
Best answer

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$

by Boss (33.8k points)
edited by
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   }
+22 votes

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)

by Loyal (5.7k points)
edited by

question is about odd cardinality, that makes it half of 2n = 2n/2 = 2n-1

Thank you sir :) I misread the question

@ Praveen Saini sir  edited my answer 

sir,{∅} is also subset of any SET.?? and sir its cardinality is one .?? am i right..??

∅ is a subset of every set, not {∅}. 


sir .if A={1,2}

than for subset we have to use {∅}. or ∅.

 I think we should use {∅}.⊆{1,2} ?? am i right.???sir.?


No. ∅ or {}. Not {∅}.


then when we will use {∅}.??

can we say    {∅}.∈{1,2}??? 


                            ∅∈{1,2} ??? which one true.??


Make a set and put the empty set inside it- Now we have {∅}. 

You should surely read about set, membership and subset definitions from a standard source and apply those definitions. 

k, i will do that
+16 votes

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 2n

Among which exactly half is odd

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

by Veteran (117k points)
@Srestha, Even the above argument would hold for even values??Isn't it??Am I correct Srestha??
yes ..
Thank you Srestha. :)
+1 vote

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.

by Active (2.1k points)
edited by
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).
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,651 questions
56,214 answers
95,437 users