• ms@ms.lt
• +370 607 27 665
• My work is in the Public Domain for all to share freely.

Introduction E9F5FC

Understandable FFFFFF

Questions FFFFC0

Notes EEEEEE

Software

See: Binomial theorem

Find and compare q-analogues of the binomial theorem.

• Write out examples, inductions, bijections.
• Interpret each of the choice frameworks in terms of a q-analogue.
• Analyze the recurrence relation. What can possibly be counted by it?
• What other recurrence relations can there be?

Q-analogues of the binomial theorem:

• Each cell or inversion has weight {$q$}.
• Subspaces of a vector space over a finite field.
• Simplexes - the {$k$} vertices have weights from {$1,q,q^2,\dots\,q^n$} and each edge has weight {$q^{-1}$}.

The sum of the weights of the vertices of an n-simplex is given by:

{$$\left [ n \right ]_q = 1 + q + q^2 + \dots + q^{n-1} = \frac{q^n-1}{q-1}$$}

Gaussian binomial coefficients are given by the induction:

{$$\begin{bmatrix}n\\k\end{bmatrix}_q = \begin{bmatrix}n-1\\k\end{bmatrix}_q + q^{n-k}\begin{bmatrix}n-1\\k-1\end{bmatrix}_q$$}

{$$\begin{bmatrix}n\\k\end{bmatrix}_q = \frac{\left [ n \right ]_q!}{\left [ k \right ]_q! \left [ n-k \right ]_q!}$$}

Given a prime {$q$}, the number of {$k$}-dimensional subspaces of {$\mathbb{F}^n_q$} is {$\begin{bmatrix}n\\k\end{bmatrix}_q$}.

{$\mathbb{F}^n_q$} consists of {$q^n$} vectors of which {$q^n-1$} are nonzero vectors. The number of k-tuples of linear independent vectors is given by the product of {$q^n-1$} possibilities for the first choice, {$q^n-q$} for the second choice, {$q^n-q^2$} for the third choice, and so on, up to {$q^n-q^2$} possiblities for the {$k$}th choice. This gives the product:

{$$(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{k-1})$$}

Then we have overcounted because some of these k-tuples generate the same vector subspace. By the same argument we find that any {$k$}-dimensional vector space is spanned by the following number of k-tuples of linear independent vectors:

{$$(q^k-1)(q^k-q)(q^k-q^2)\cdots(q^k-q^{k-1})$$}

Thus we divide, yielding the answer.

Challenge: I want to reconstruct an argument that I had. It went something as follows. Given a basis {$x_1, x_2, \dots, x_n$} there is only one choice for the first element, but then there are q choices for {$qx_1 + x_2$} and {$q^2$} choices for {$qx_1 + qx_2 + x_3$} and so on. But when q=1, then there is no real choice because we are choosing out of one. And that is the essence of {$F_1$}.

Peter Cameron: Every k-dimensional subspace has a unique basis consisting of k vectors in reduced echelon form. The number of matrices in reduced echelon form satisfies the recurrence, which adds the numbers of matrices where the leading 1 in the last row is:

• in the last position (so deleting the last row and column gives a reduced echelon matrix) or
• in an earlier position (so the last column is arbitrary, and deleting it gives a reduced echelon matrix).

Henry Cohn: Given a prime {$q$}, the number of {$k$}-dimensional subspaces of {$\mathbb{P}^n(\mathbb{F}^n_q)$} is {$\begin{bmatrix}n+1\\k+1\end{bmatrix}_q$}.

The weights of the Gaussian binomial coefficients count the number of cells to the left of the paths in Pascal's triangle.

Bruce Sagan via Peter Cameron: The binomial coefficient Bin(n,k) counts the k-element subsets of an n-element set. Now suppose we have a cyclic permutation σ of the set, and we wish to count its orbits on k-subsets. By the Orbit-counting Lemma, we have to count the subsets fixed by any power of σ. Now it turns out that the number of sets fixed by a power of σ of order d is the result of substituting a primitive dth root of unity for q in Gauss(n,k)q.

See Bruce Sagan: Words

inversions {$\sum_{w\in W_{n,k}}q^{\textrm{Inv} \; w}$} where {$\textrm{Inv} \; w = \left | \left \{ (i,j):i<j \; \mathrm{and} \; a_i>a_j \right \} \right |$}

major index {$\sum_{w\in W_{n,k}}q^{\textrm{Maj} \; w}$} where {$\textrm{Maj} \; w = \sum_{a_i>a_{i+1}}i$}

In what sense are the major index and the inversions duals of each other?