find the number of subspaces $W$ such that $U\subseteq W$ Let $V$ be a vector space of dimension $n$ over a finite field $F$ with $q$ elements, and let $U\subseteq V$ be a subspace of dimension $k$. How many subspaces $W\subseteq V$ of dimension $m$ such that $U\subseteq W $ do we have $(k\leq m\leq n)$?
Hint: look at the set:
$$
\{ (U,W) \mid U \subseteq W \subseteq V; 
\, \dim(U)=k, \, \dim(W)=m \}
$$
I have no idea how to use the hint. I know that the number of subspaces of dimension $k$ is:
$$
\frac{\prod_{i=0}^{k-1} (q^{n-1}-1)}{\prod_{i=0}^{k-1} (q^{k-1}-1)}
$$
and I don't know how to proceed from here.
 A: Given a basis $\{v_1,v_2,\dots, v_k\}$ for $U$, how many ways can you extend the basis to a larger linearly independent set?
So, the next vector can't be a linear combination of the $v_1,\dots, v_k$.  How many linear combinations are there?  There are $q^k$.  So since the vector space has $q^n$ elements,  we get $q^n-q^k$ ways of adding one more linearly independent vector.
Similarly,  for the next one there are $q^n-q^{k+1}$.
So, we get $$\prod_{j=0}^{n-k-1}(q^n-q^{k+j})$$.
Now we need to remember that there are $l_m=(q^n-1)(q^n-q)\dots (q^n-q^{m-1})$ different bases for each $m$-dimensional subspace (by similar reasoning) .  So we divide.
Get $$\prod_{j=0}^{n-k-1}(q^n-q^{k+j})/l_{k+j+1}$$
A: Cpc's answer is fantastic, but here is a more high-level presentation. Noether's fourth isomorphism says that the subspaces of $V$ which contain $U$ are in bijection with subspaces of $V/U$. Therefore, the number of $W$ with $U\subseteq W\subseteq V$ and $\dim W=m$ is the same as the number of subspaces of $V/U$ with dimension $m-k$, which is just the $q$-binomial coefficient $\binom{n-k}{m-k}_q$.
A: The point of the hint is to count the elements of that set: given what you already know, it is easy to do it by first choosing $W$ then choosing $U$.  Doing it the other way is easy in terms of the number you're trying to compute.  And the two enumerations must be the same.  This avoids repeating the argument that you used to establish the subspace counting formula in the first place.
