Number of subgroups of order $2^n$ in the powerset equipped with symmetric difference

Solution 1:

The group $P(X)$ is the vector space of dimension $m=|X|$ over $\Bbb Z/2\Bbb Z$. You want to find the number of subspaces of dimension $n$, that is the number of linearly independent subsets of $n$ vectors divided by the order of $GL_n(\Bbb Z/2\Bbb Z)$ (we need to take into account that several sets of l.i. vectors may span the same subspace, $|GL_n(\Bbb Z/2\Bbb Z)|$ is the number of bases of the $n$-dim space over $\Bbb Z/2\Bbb Z$).

To build a linearly independent subset $e_1,...,e_n$ we can pick non-zero $e_1$ arbitrarily - $2^m-1$ options, then pick $e_2$ arbitrarily, except it should not belong to $span\{e_1\}$, $2^m-2$ options, then pick $e_3$ only making sure it is not in $span\{e_1,e_2\}$, $2^m-4$ options, and so on. Altogether the number of choices is $(2^m-1)(2^m-2)\cdot ...\cdot (2^m-2^{n-1})$. Denote it by $u_{m,n}$.

Every matrix in $GL_n(\Bbb Z/2\Bbb Z)$ has $n$ linearly independent row-vectors. So the number $|GL_n(\Bbb Z/2\Bbb Z)|$ can be computed the same way as $u_{m,n}$, it is equal to $v_n=(2^n-1)(2^n-2)\cdot...\cdot (2^n-2^{n-1})$.

So the number you are interested in is $u_{m,n}/v_n$.