Take the 2-minute tour ×
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.

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|improve this question
    
I think this is related to en.wikipedia.org/wiki/Gaussian_binomial_coefficient –  Srivatsan Sep 30 '11 at 21:21

1 Answer 1

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|improve this answer
    
So your answer is $f(n,q) = \frac{1}{n!} \cdot \prod_{i=0}^{n-1} (q^n - q^i)$. Thanks. –  moose Oct 5 '11 at 8:15
    
Is this equal to $g(n,q) = \frac{1}{2} \cdot \binom {n^q}{n}$? –  moose 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: wolframalpha.com/input/?i=1%2Fn%21+%28product_%28i%3D0%29^%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!}$$ –  moose 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

 
discard

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.