3
$\begingroup$

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?

  • 0
    I think this is related to http://en.wikipedia.org/wiki/Gaussian_binomial_coefficient2011-09-30

1 Answers 1

6

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

  • 0
    So your answer is $f(n,q) = \frac{1}{n!} \cdot \prod_{i=0}^{n-1} (q^n - q^i)$. Thanks.2011-10-05
  • 0
    Is this equal to $g(n,q) = \frac{1}{2} \cdot \binom {n^q}{n}$?2011-10-05
  • 0
    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.2011-10-06
  • 0
    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: http://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!}$$2011-10-08
  • 0
    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.2011-10-13