# number of possible subsets formed with odd count of odd numbers = $2^{n_{odd}-1} \cdot 2^{ n_{even}}$

Let $n_{odd}$ represents the number of odd numbers in the set $S$ and $n_{even}$ denote the number of even numbers. The total number of possible subsets formed with odd count of odd numbers $=2^{n_{odd}-1} \cdot 2^{n_{even}}$. How do we prove this ?

• Let $O$ be the set of odd numbers in $S$. Half the subsets of $O$ have an odd number of odds. – André Nicolas Mar 30 '16 at 21:52

Let $E$ be the set of even numbers in $S$, and $O$ the set of odd numbers in $S$. We assume (this is not stated explicitly in the post) that $O$ is non-empty.

Any subset of $S$ with an odd number of odds can be uniquely expressed as $A\cup B$, where $A$ is a subset of $O$ with an odd number of odds, and $B$ is any subset of $E$.

For any choice of $A$, there are $2^{n_{\text{even}}}$ ways to choose $B$. It remains to show that there are $2^{n_{\text{odd}}-1}$ ways to choose $A$.

So we want to count the number of odd subsets of $O$. Arrange the $n_{\text{odd}}$ elements of $O$ in order. Call them $x_1$ to $x_k$. Any subset of $O$ with an odd number of elements can be uniquely constructed as follows. Choose any subset of $\{x_1,\dots, x_{k-1}\}$. If this subset has an odd number of elements, keep the subset. If if has an even number of elements, append $x_k$ to the set, to make the count of odds odd.

So there are just as many subsets of $\{x_1,\dots,x_k\}$ with an odd number of elements as there are subsets of $\{x_1,\dots, x_{k-1}\}$, that is, $2^{k-1}$. In our case $k=n_{\text{odd}}$, so we are finished.

Another way: We sketch a much simpler approach based on the same idea. Suppose $a$ is a fixed odd number in $S$. Call a subset of $S$ good if it has an odd number of odd numbers. We count the good subsets of $S$.

There are just as many good subsets of $S$ as there are subsets of $S\setminus \{a\}$. For a subset $K$ of $S\setminus\{a\}$ is either good or not good. But if $K$ is not good, then $K\cup\{a\}$ is good. And every good subset of $S$ can be produced in this way.

Thus the number of good subsets of $S$ is $2^{m-1}$, where $m$ is the number of elements of $S$. Finally, note that $m=n_{\text{odd}}+n_{\text{even}}$, and therefore $2^{n_{\text{odd}}-1}\cdot 2^{n_{\text{even}}}=2^{m-1}$.

• Nicolas can you please elaborate this line more in your second approach "There are just as many good subsets of SS as there are subsets of S∖{a}S∖{a}. For a subset KK of S∖{a}S∖{a}, is either good, or appending aa to it makes it good." – satyajeet jha Mar 31 '16 at 0:34
• Let $S_a=S\setminus\{a\}$ (everybody but $a$), and take any subset $K$ of $S_a$. Maybe $K$ has an odd number of odds (is good). Or maybe it has an even number of odds, in which case $K\cup \{a\}$ is good. So given any subset of $S_a$, we can produce a good subset of $S$ using this procedure. Conversely, any good subset of $S$ can be produced in this way, for a good subset either does not contain $a$, so must be a good subset of $S_a$, or does contain $a$, so must have been produced by adding $a$ to a bad subset of $S_a$. – André Nicolas Mar 31 '16 at 0:47