# 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.

-
As 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 math.stackexchange.com/questions/54246/… and on Math Overflow at mathoverflow.net/questions/18636/… . – Kevin Costello Oct 12 '12 at 19:16
But this is not a proof. This is just a guess about the n-th term based on the first few terms of the sequence. – deb Oct 13 '12 at 8:38
But, 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$. – Gerry Myerson Oct 13 '12 at 12:09

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.$

-