Count number of m-subsets with xor = 0

456 Views Asked by At

Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let $[k]=\{1,2,\ldots,k\}$.

For example, for $n = 2$, $m = 3$ the answer is $1$: $\{1, 2, 3\}$ is the only set that meets the restrictions.

It seems that it could be done faster than using brute force, perhaps with dynamic programming.

There is a question in which $S$ is allowed to range over all subsets of $[2^n-1]$ irrespective of their cardinalities, but I couldn't figure out how to generalize it in order to have the fixed size of subset: Count subsets with zero sum of xors

I also tried to reduct the problem to the system of linear equations, but our sets are not multisets, so this approach doesn't work.