Consider $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the subset $\mathrm{S}^n = \{(x_1,\ldots,x_n) \in \mathbb{R}^n | x_i = 0 \; \mathrm{or} \; 1\;\forall i = 1,\ldots,n\}$. How many bases of $\mathbb{R}^n$ does $\mathrm{S}^n$ contain? e.g. for n = 2, $\mathrm{S}^2 = \{(0,0),(0,1),(1,0),(1,1)\}$ and it contains three bases namely $\{(0,1),(1,0)\},\;\{(0,1),(1,1)\},\textrm{ and }\{(1,0),(1,1)\}$. I want a general expression for n.
Count the number of bases in a subset
18
$\begingroup$
linear-algebra
combinatorics
vector-spaces
-
0As noted in Fly by Night's answer, this is $\frac{1}{n!} a_n$, where $a_n$ is the number of invertible $(0,1)$ matrices. $a_n$ is discussed further at http://math.stackexchange.com/questions/54246/probability-that-a-random-binary-matrix-is-invertible and on Math Overflow at http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices . – 2012-10-12
-
0But this is not a proof. This is just a guess about the n-th term based on the first few terms of the sequence. – 2012-10-13
-
3But, deb, the vectors form a basis if and only if the matrix whose columns are those vectors is invertible --- no guessing here, the answer to your questions is absolutely certainly $(n!)^{-1}a_n$. – 2012-10-13