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.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems. Bookmark the permalink.

2 Responses to A couple of problems

  1. ahwingsecretagent says:

    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.

    • 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s