## A couple of problems

I’m sorry there has been so much bureaucracy here lately. Those things are important but I would rather talk about mathematics.

So here is a simple test. I will set it just for binomial coefficients, but really the setting for it is multinomial coefficients.

The binomial coefficient nCk is the number of ways in which you can colour the elements of an n-element set red and blue so that there are k red and n-k blue.

It also has the following interpretation. Suppose that the elements have been coloured red and blue as above, and suppose that both the red elements and the blue elements have been ordered. Then the number of ways of ordering the whole set consistent with the two orderings is also nCk.

Your job is to find a bijective proof of this fact; that is, to match up the colourings with the orderings.

If you want something harder to think about, here is the problem that led me to this little observation.

Let V be a finite vector space, of dimension n over a field with q elements. Find a formula for the number of orderings of V which have the property that the unique order-preserving mapping between any two subspaces of V of the same dimension is linear (that is, also preserves the vector space structure).

I have a formula only in the cases n=1 and n=2.

I think the first part is pretty easy. For a colouring of the set $\{1,2,...,n\}$ let’s call the $k$ red numbers $r_1,r_2,...,r_k$ and the blue ones $b_1,b_2,...,b_{n-k}$. Then the $k$ red numbers that were ordered are placed on the $r_1,r_2,...,r_k$ in their order, and the blue ordered numbers placed on the ones left in their order. It is easy to check this is a bijection.