Rearrangements of the monotonically increasing integer numbers $1, 2, 3, \dots, n$

Question

My question requires some background explanation: Imagine, for simplicity sake, I start with the increasing sequence 1, 2, 3, 4, 5, and I call the current position of these numbers in this sequence their “normal” positions. Now imagine if I move one number to the left of its “normal” position (for example, 4) and keep every other number at the “normal” position, then I could get the sequence 1, 2, 4, 3, 5 or 1, 4, 2, 3, 5. If I were to consider the number of ways to rearrange a more general sequence of increasing numbers (namely the sequence 1, 2, ..., n) such that only one number is moved to the left of its “normal” position, then this calculation is relatively trivial; there are n-1 slots for the nth number to go, n-2 slots for the n-1th number to go,...,1 slot for the second number to go, giving a total of (n-1)(n)/2 possible ways. My question, then, is how do I generalize this method of counting to find, say, the number of ways to rearrange the sequence 1,..,n such that exactly two of the numbers are moved to left of their “normal” position? Or, really, in most general terms exactly k numbers are moved to left of their “normal” position, for some arbitrary k less than or equal to n-1. Any input is greatly appreciated, thank you!

Answer 1

if you let us say we pick 2 and 3 then 2 have 1 place to go and 3 have 2 places to giving a total of 2 ways.If we select n and 4 then we have 3(n-1) ways.

So firstly write all ways of choosing 2 integers from 1 to n-1 , multiply them with each other and then add all of them.

that is equal to $\frac{{(1 + 2 + 3....... (n-1))}^2\ -\ 1^2\ -\ 2^2\ - \ ........... ({n-1})^2}{2}$

=

$\frac{n^2(n-1)^2}{8}\ -\ \frac{n(n-1)(2n-1)}{12}$

---

I can't do it for all n, but i am doing for n=3

in (a+b+c+d............)³ contains terms like a³ ,b³.... , 3a²b,3a²c,3b²c...... And 6 abc ,6acd.... Of which we want abc , acd.....

We know that summation of first n-1 consecutive cubes.

The summation of 3a²b+3b²c...likewise = 3(1+2+3+4.....(n-1)²)(1²+2²+3²+4²......(n-1)²).

So our answer is $\frac{1}{6}\left[(1+2+3+4........(n-1))³\ -\ (1³+2³+3³..........(n-1)³) \ -\ 3(1+2+3.....(n-1))(1²+2²+3².....(n-1)²)\right]$

$= \frac{\frac{n³(n-1)³}{8}\ -\ \frac{n²(n-1)²}{4}\ -\ \frac{n²(n-1)²(2n-1)}{4}}{6}$

$= \frac{1}{48}n²(n-1)²\ [ n(n-1) - 2 - 4n-2]$

$= \frac{1}{48}n²(n-1)²\ [ n²-5n-4]$

$= \frac{1}{48}n²(n-1)²(n²-5n-4)$.