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 ^{n}C_{k} 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 ^{n}C_{k}.

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.

### Like this:

Like Loading...

*Related*

## About Peter Cameron

I count all the things that need to be counted.

I think the first part is pretty easy. For a colouring of the set let’s call the red numbers and the blue ones . Then the red numbers that were ordered are placed on the 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.

Yes, that’s it. You can do the multinomial version by simply using an arbitrary number of colours.

I don’t think the second part is so simple!