How many k-dimensional subspaces there are in n-dimensional vector space over $\mathbb F_p$?

I am asked to find how many there are $k$-dimensional subspaces in vector space $V$ over $\mathbb F_p$, $\dim V = n$.

My attempt: 1) Let's find a total number of elements in $V$: assume that $\{v_1, v_2, \cdots, v_n\}$ is a basis in $V$. Then, for every $v \in V$ we can write down $$ v = a_1 v_1 + a_2 v_2 + \cdots + a_n v_n $$ and since the coordinates ($a_1, \cdots, a_n$) are from $\mathbb F_p$ there are $p^n$ vectors in $V$; $p-1$ without the zero vector.

2) Let's look at a situation where $k=1$. Let's call this 1-dimensional space $V'$. $$\forall v' \in V'. v' = a_1 v_1$$ where $v_1$ is a basis in $V'$. We know that if there are two non-zero vectors $u \in V'_1$ and $v \in V'_2$, they are not linear dependant. So, every 1-dimensional subspace has $(p-1)$ basises. Therefore, there are $\frac{p^n - 1}{p-1}$ possible 1-dimensional subspaces in $V$

3) k-dimensional subspace is defined by the set of it's basises. Since basis can not contain zero vectors we can write down the formula for selecting $k$ linear independent vectors: $C^k_m (p-1)^k$, where $m = \frac{p^n - 1}{p-1}$. Here we first choose $k$ 1-dimentioanl subspaces and then we choose one of $(p-1)$ non-zero vectors from each of the subspaces.

4) .. unfortunately, this is where I am stuck. My intuition says that the answer may be $\frac{p^n - 1}{(p-1)^k}$, but this might be completely wrong and I don't know how to go about finishing the problem.

Thanks in advance.

Solution 1:

Here is a hint: Find a formula for the number of possibilities to choose $k$ linearly indepenent vectors in $\mathbb{F}_p ^n$ (where order matters). Each of these choices serves as a basis for a $k$-dimensional subspace, but for each subspace there are several bases, so you have to divide by the number of bases for each subspace - and computing this number involves essentially the same formula as above.

Solution 2:

Just for the record, the number asked for here is the Gaussian binomial coefficient $\binom nk_q$ evaluated at $q=p$. The indeterminate of the Gaussian binomial coefficient is traditionally called $q$, and I guess this is in particular because of the usefulness of setting it equal to the order of a finite field.

Solution 3:

Let $n=\dim V$, where $V$ is a vector space over any finite field $\mathbb{F}$ with $|\mathbb{F}|=r$ and $W$ is a $k$-dimensional subspace of $V$. First of all we count the number of basis of $W$. There are $r^k-1$ non zero vectors in $W$, so to select a base for $W$, first member could be selected in $r^k-1$ way. Second member in $r^k-r$ way and so on. Hence the total number is $s=(r^k-1)(r^k-r)\cdots (r^k-r^{k-1})$.

How many $k$-element subsets are there in $V$, each of which generates a $k$-dimensional subspace of $V$? The answer is as follows: to construct such a subset $A=\{v_1,\cdots , v_k\}$, obviously $v_1$ could be selected in $r^n-1$ way, the vector $v_2$ in $r^n-r$ way, $\cdots$, and $v_k$ in $r^n-r^{k-1}$ way. So there are $t=(r^n-1)( r^n-r)(r^n-r^{k-1})$ of such subsets. Let us to call this family of subsets of $V$ with $\mathcal{B}$ and the family of basis of $W$ with $\mathcal{A}$. The size of $\mathcal{A}$ is $s$ and the size of $\mathcal{B}$ is $t$. A member $A$ in $\mathcal{B}$ generates $W$ if and only if $A$ lies in $\mathcal{A}$, on the other hand any $k$-dimensional subspace of $V$ corresponds to a member of $\mathcal{B}$ and as $W$ was typical, in $\mathcal{B}$ there are $s$ elements which all of them generate same subspace. Therefore the number of different $k$-dimensional subspaces of $V$ is $t/s$.