Count the number of bases in a subset 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.
 A: This is a really nice problem. It is easy to understand, but is not easy to solve. 
I've written a program in Maple to find out the first few terms of the sequence. Maple gets stuck after $n=5$ because the numbers involved grow exponentially. (My program is probably very inefficient too and uses too much RAM.) 
If $b_n$ denotes the number of sub-bases, then I get the sequence to be: $(b_n) = (1,3,29,940,104286,\ldots)$
A similar sequence appears on the on-line encyclopedia of integer sequences. In fact, the encyclopedia suggests that $b_6 = 40050850$, $b_7 = 53640013886$ and $b_8 =  251995529844792.$
The sequence $(b_n)$ seems to be given by $n! \cdot  b_n = a_n$, where more information about the sequence $(a_n)$ can be found here. In particular, the previous link talks about "Classification of small $(0,1)$ matrices", and supplies literature references.
In terms of trying to solve it for yourself, well, I think that an inductive argument could be very successful. Although, I haven't manage to construct one myself. A key fact is that if you remove an element of a basis for $\mathbb{R}^n$ then you're still left with a basis for $\mathbb{R}^{n-1}.$ Conversely, the bases for $\mathbb{R}^n$ can be built from the bases for $\mathbb{R}^{n-1}.$ If you the kind of vectors you need to add to a basis for $\mathbb{R}^{n-1}$ in order to get a basis for $\mathbb{R}^n$, and you know $b_{n-1}$, then you will know $b_n.$ I suspect that you will be able to prove, by induction, a recurrence relation, which you will then be able to solve.
For example, if you know the elements of $S^{n-1}$, then you need only add an extra number at the end of each element, one a $0$ and one a $1$, to get the elements of $S^n.$
