Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Imagine a 2-dimensional vector space in $\mathbb{Z} /2 \mathbb{Z}$. The only possible basis' are $$ \left(\begin{array}{c} 1\\ 0 \end{array}\right), \left(\begin{array}{c} 0\\ 1 \end{array}\right); \left(\begin{array}{c} 1\\ 1 \end{array}\right), \left(\begin{array}{c} 0\\ 1 \end{array}\right);\left(\begin{array}{c} 1\\ 0 \end{array}\right), \left(\begin{array}{c} 1\\ 1 \end{array}\right)$$

This means for n = 2 would 3 be the correct answer. For n = 1 the answer is 1.

What is the correct answer for a variable n?

share|cite|improve this question
I think this is related to – Srivatsan Sep 30 '11 at 21:21
up vote 6 down vote accepted

We can do the more general case for $F = \mathbb{F}_q$ for $q$ a power of a prime. The first vector can be chosen from $q^n - 1$ possible choices. The subspace generated by it has $q$ points, since each vector is determined by $q$ possible coefficients. Continuing we get the formula $(q^n - 1)(q^n - q)\cdots (q^n - q^{n-1})$. This is the number of ordered bases though, but we can just divide by $n!$ to get the number of unordered bases.

For instance in your case $q = 2^1 = 2$ and $n = 2$, so we get $(2^2-1)(2^2-2) = 3\times 2 = 6$ possibilities. To get your $3$ we just divide by $2!$. You could write the general formula to be

$(q^n - 1)(q^n - q)\cdots (q^n - q^{n-1})/n!$

share|cite|improve this answer
So your answer is $f(n,q) = \frac{1}{n!} \cdot \prod_{i=0}^{n-1} (q^n - q^i)$. Thanks. – Martin Thoma Oct 5 '11 at 8:15
Is this equal to $g(n,q) = \frac{1}{2} \cdot \binom {n^q}{n}$? – Martin Thoma Oct 5 '11 at 8:57
No. It just happens to work for $n=2,q=2$. Try $n=3,q=8$, and then $g(n,q)$ is much larger. You can see that these expressions don't have much hope of being equal because the second expression has a $n^q$ in it. – Jason Polak Oct 6 '11 at 18:11
guess there is no simpler way to write f(n,q) ... Wolfram|Alpha gave me some alternate forms, but they are by far more complex:^%28n-1%29+%282^‌​n+-+2^i%29%29 e.g. $$f(n,2) = \frac{2^{n^2} e^{2 i n π \lfloor \frac{1}{2}-\frac{Im(n) log(2)}{2 π} \rfloor} (2^{-n}, 2)_n}{n!}$$ – Martin Thoma Oct 8 '11 at 3:58
It seems that the expression as a product of terms of the form (q^n-q^i) is already pretty elegant and simple, especially as it only involves the basic operations of arithmetic. – Jason Polak Oct 13 '11 at 20:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.