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 ⁿ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 ⁿ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.

About these ads

About Peter Cameron

I count all the things that need to be counted.

View all posts by Peter Cameron →

This entry was posted in open problems. Bookmark the permalink.

2 Responses to A couple of problems

ahwingsecretagent says:

07/12/2009 at 17:21

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.

- Peter Cameron says:
  
  07/12/2009 at 17:34
  
  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!