recategorized by
5,516 views
31 votes
31 votes
The number of subsets $\left\{ 1,2, \dots, n\right\}$ with odd cardinality is ___________
recategorized by

4 Answers

Best answer
26 votes
26 votes

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 by
36 votes
36 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)

edited by
29 votes
29 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

1 votes
1 votes

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 by

Related questions

17 votes
17 votes
4 answers
1
Kathleen asked Oct 4, 2014
4,382 views
The Hasse diagrams of all the lattices with up to four elements are ________ (write all the relevant Hasse diagrams)
23 votes
23 votes
3 answers
2
Kathleen asked Oct 4, 2014
5,036 views
Amongst the properties $\left\{\text{reflexivity, symmetry, anti-symmetry, transitivity}\right\}$ the relation $R=\{(x, y) \in N^2|x \neq y\}$ satisfies _________
39 votes
39 votes
4 answers
3
Kathleen asked Oct 4, 2014
5,726 views
On the set $N$ of non-negative integers, the binary operation ______ is associative and non-commutative.
33 votes
33 votes
5 answers
4
Kathleen asked Oct 4, 2014
8,668 views
The regular expression for the language recognized by the finite state automaton of figure is ________