A Combinatorics Problem

Deep down inside we all love math T-shirt
Image by Network Osaka via Flickr

Let 1,2,3,...,n be an ascending sequence of number. If swapping the i^{th} and {i+1}^{th} position is considered as one step for i \in \{1,...,n-1\}, then determine the least number of steps needed to reorder the sequence to be a descending one (n,n-1,...,1).Β  How can you be sure that your number is indeed the least number of steps?

P.S. Even though this problem looks like a toy problem, it definitely isn’t. This is a dumbing down version of a real problem I’ve solved in using a computer program before. I really saved a lot of time by solving this problem πŸ˜€


5 thoughts on “A Combinatorics Problem

    1. Ahaha.. you are indeed correct
      CMIIW, you are Marisa’s sister aren’t you?

      Have you thought of an argument of why it is indeed the answer? That’s the real challenge πŸ˜‰

      1. I used “ordinary generating function” coz as I know it is one way to solve that kind of problem…
        btw how did you know that I’m Marisa’s sister??

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