The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
834 views
The number of subsets $\left\{ 1,2, \dots, n\right\}$ with odd cardinality is ___________
asked in Set Theory & Algebra by Veteran (59.6k points)
retagged by | 834 views

4 Answers

+15 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$

answered by Boss (34.1k points)
edited by
0
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   }
+16 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)

answered by Loyal (5.9k points)
edited by
+11

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

+1
Thank you sir :) I misread the question
0

@ Praveen Saini sir  edited my answer 

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

https://gateoverflow.in/13290/set-theory#c13557
+2

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

0

sir .if A={1,2}

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

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

0

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

0

then when we will use {∅}.??

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

                                      or

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

+1

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. 

+1
k, i will do that
+13 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

answered by Veteran (101k points)
+1
@Srestha, Even the above argument would hold for even values??Isn't it??Am I correct Srestha??
0
yes ..
+1
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.

answered by Active (2k points)
edited by
+1
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).

Related questions



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

42,599 questions
48,598 answers
155,653 comments
63,721 users