- 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?

Readings

- Projective geometry over {$F_1$} and the Gaussian binomial coefficients, Henry Cohn, his research
- Peter Cameron: The field with one element
- Bruce Sagan: Two binomial coefficient analogues
- Bruce Sagan: The cyclic sieving phenomenon - an introduction
- Bruce Sagan: The cyclic sieving phenomenon: a survey
- J. Konvalina, Generalized binomial coefficients and the subset-subspace problem, Adv. in Appl. Math.21(1998) 228–240.
- J. Wang, Quotient sets and subset-subspace analogy,Adv. in Appl.Math.23 (1999) 333–339.
- J.R.Goldman and G.-C.Rota, On the foundations of combinatorial theory IV: Finite vector spaces and Eulerian generating functions, Stud. Appl. Math.49 (1970) 239–258; reprinted in Gian-Carlo Rota onCombinatorics, J. P. S. Kung, ed., Birkh ̈auser, Boston, 1995, pp. 226–245.

Parsiųstas iš http://www.ms.lt/sodas/Book/BinomialTheoremQAnalogues

Puslapis paskutinį kartą pakeistas 2019 vasario 05 d., 13:25