# A Combinatorics Problem

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. CG says:

wow, interesting! 🙂

2. Mita says:

let me count it first

3. Mita says:

I got it 🙂
the answer is (n^2-n)/2 isn’t it??

1. Hafiz Khusyairi says:

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. Mita says:

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??