to find total number of subsets

Question

I was working out some problem where I needed permutation and combination. I took the cartesian product of $n$ sets where number of elements in each set is even. Further the elements of this cartesian product is divided into subsets as follow:

$G_0 = \{(x_1,\ldots,x_n)~ |~ each~ x_i~ is~ an ~odd ~number ~or ~ each~ x_i~ is~ an ~even ~number\}$ for $1\leq i \leq n$. $G_{k_1} = \{(x_1,\ldots,x_n)~ |~x_{k_1} ~is~even(odd) ~and ~x_i~ is~ an ~odd(even) ~number~ for ~i\neq k_1\}$. $~~~~~~~~~~~~\textrm{where}\,\,1\leq k_1\leq n$. $G_{{k_1}{k_2}} = \{(x_1,\ldots,x_n)~ |~x_{k_1},x_{k_2} ~is~even(odd) ~and ~x_i~ is~ an ~odd(even) ~number~ for ~i\neq k_1,k_2\}$. $~~~~~~~~~~~~~~\textrm{where}\,\,1\leq k_1\leq n-1$. $~~~~~~~~~~~~~\,\,k_1 +1\leq k_2\leq n$.

$\vdots$

$G_{{k_1}{k_2}{\ldots}{k_\lfloor n/2 \rfloor}} = \{(x_1,\ldots,x_n)~ |~x_{k_1},x_{k_2}\ldots,x_{k_\lfloor n/2 \rfloor} ~is~even(odd) ~and ~x_i~ is~ an ~odd(even) ~number~ \\~~~~~~~~~~~~~~~~~~~~~~~~~~~for ~i\neq k_1,k_2\ldots,{k_\lfloor n/2 \rfloor}\}$. $~~~~~~~~~~~~\textrm{where}~~~~~~~~~~~\,\,1\leq k_1\leq n-(\lfloor n/2 \rfloor - 1)$

$~~~~~~~~~~~~~~~~~~~~~~~~~\,\, k_1 +1\leq k_2\leq n-(\lfloor n/2 \rfloor - 2)$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\vdots$

$~~~~~~~~~~~~~~~~\,\, k_{{\lfloor n/2 \rfloor}-1} +1\leq k_{\lfloor n/2 \rfloor} \leq n$

How to prove that total number of these subsets will be $2^{n-1}$? For small values of $n$ I checked manually but as $n$ increases its a tedious job. Please help or suggest any way to prove this. Thanks for giving your attention.

The following answer is true for odd numbers. Kindly help in the case of even numbers

NOTE: n sets with even number of elements means that if $A_1$ is a set with even number of elements, ex 6 elements, then $A_1$ is like $A_1 = \{1,2,3,4,5,6\}$.

Answer 1

Here we set $k=\{k_1,...,k_i\}$ for some $i\leq \lfloor n/2 \rfloor$. Then we have $G_k$ as in you definition. So your question is in how many ways can we choose $k$ such that $G_k$ is a set as in your definition.

This can be calculated by how many different $k$ we can pick, lets call this number $x$. This number equals $$ \sum_{i=0}^{\lfloor n/2\rfloor}{n \choose i}=x $$ If we now multiple this number by $2$ and realise that ${n \choose i}={n \choose n-i}$. Then we get \begin{align*} 2x &= 2\sum_{i=0}^{\lfloor n/2\rfloor}{n \choose i}\\ &= \sum_{i=0}^{\lfloor n/2\rfloor}{n \choose i}+\sum_{i=0}^{\lfloor n/2\rfloor}{n \choose n-i}\\ &= \sum_{i=0}^{n}{n \choose i} \end{align*}

Then with newton's binomial we have that $\sum_{i=0}^{n}{n \choose i}=2^n$. Thus we get that $$2x=2^n\Rightarrow x=2^{n-1}.$$

Answer 2

Consider a single element of the Cartesian product: $$(x_1,x_2,x_3,\ldots,x_n)$$ Each $x_i$ is an integer, and thus even or odd. Now consider applying $f(x)=x\operatorname{mod}2$ to each term. The result will be a binary string of length $n$. For example, $(1,2,3,4,2,7,3)$ would become $(1,0,1,0,0,1,1)$.

Notice that each of your $G$-subsets contains all the elements of the Cartesian product which fit a particular binary profile, or its inverse. For example, $G_{3,5}$ contains elements fitting the profiles $(0,0,1,0,1,0,0,0,\ldots,0)$ or $(1,1,0,1,0,1,1,1,\ldots,1)$, in which the dots represent just zeros and just ones respectively.

Furthermore, the list of $G$-subsets is a disjoint cover of the Cartesian product. By applying the function $f$ to the terms $x_1,x_2,\ldots,x_n$, we get a binary profile which immediately fits exactly one of the subsets.

There are $2^n$ possible binary profiles. Each of the $G$-subsets deals with two such profiles. They are disjoint and cover the Cartesian product. Therefore there must be $2^n\div2=2^{n-1}$ of them.