Number of all subspaces of a vector space over a finite field

Question

Let $V$ be an $n$-dimensional vector space over a finite field $\mathbb{F}_q$. We know that the number of $k$-dimensional subspaces of $V$ is given by the $q$-binomial coefficient $$\binom{n}{k}_q = \frac{(q^n-1) \cdots (q^n-q^{k-1})}{(q^k-1) \cdots (q^k-q^{k-1})}.$$ What can we say about the number of all subspaces of $V$, which is thus given by $$s(n,q) := \sum_{k=0}^{n} \binom{n}{k}_q~?$$ This is a polynomial in $q$ with coefficients in $\mathbb{N}$. Is there are more concrete description? I already know that the coefficients count certain partitions, but I am not so much interested in the coefficients than in a closed or computable form. Can we write $s(n,q)$ as a sort of $q$-analog of a power of $2$? (In the limit case $q \to 1$, we will get $2^n$.) Is there a recurrence relation? Do these numbers have a name?

It is tempting to use the $q$-binomial theorem, which states $$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k}_q x^k y^{n-k}$$ in the ring $\mathbb{Z}\langle x,y : yx=q xy \rangle$. But we cannot simply plug in $x=y=1$ here, since this does not define a ring homomorphism.

Here are some examples:

$s(0,q)=1\\ s(1,q)=2\\ s(2,q)=q+3\\ s(3,q)=2 q^2+2 q+4\\ s(4,q)=q^4+3 q^3+4 q^2+3 q+5\\ s(5,q)=2 q^6+2 q^5+6 q^4+6 q^3+6 q^2+4 q+6\\ s(6,q)=q^9+3 q^8+4 q^7+7 q^6+9 q^5+11 q^4+9 q^3+8 q^2+5 q+7\\ s(7,q)=2 q^{12}{+}2 q^{11}{+}6 q^{10}{+}8 q^9{+}12 q^8{+}12 q^7{+}18 q^6{+}16 q^5{+}16 q^4{+}12 q^3{+}10 q^2{+}6 q{+}8$

Answer 1

I have found a recurrence relation.

For a subset $J \subseteq V$, let $S(J)$ denote the set of all subspaces of $V$ containing $J$. These correspond to subspaces of $V/\langle J\rangle$. It follows that $\# S(J) = s(n-\dim \langle J \rangle,q)$.

By inclusion-exclusion principle, we have

$$s(n,q) = 1 + \# \bigcup_{v \in V \setminus \{0\}} \# S(\{v\})\\=1+\sum_{J \subseteq V \setminus \{0\},\, J \neq \emptyset} (-1)^{1+\# J} \cdot \# S(J)\\=1+\sum_{J \subseteq V \setminus \{0\},\, J \neq \emptyset} (-1)^{1+\# J} \cdot s(n-\dim \langle J \rangle,q)\\ =1+\sum_{k=1}^{n} \left(\sum_{J \subseteq V \setminus \{0\},\, \dim \langle J \rangle =k} (-1)^{1+\# J}\right) \cdot s(n-k,q).$$

So it suffices to describe these coefficients here.

Answer 2

Hint: The coefficients $T(n,k)$ of $s(n,q)$

\begin{align*} s(n,q)&=\sum_{k=0}^n \binom{n}{k}_q=\sum_{k\geq 0}T(n,k)q^k \end{align*}

are archived as A083906 in OEIS. The information there is rather small indicating there is not much further information available.