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

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$

edited
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   }

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)

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

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

+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.

edited
+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).

1
2