2
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ It will probably help to phrase the problem in terms of permutations $\sigma \in S_n$, which makes us count (if I've understood) how many times $\sigma(k) \lt k$ for some $k=1,\ldots,n$. Perhaps I've overlooked some subtle aspect of how you wanted to count things, so give that "notational" approach a trial to see if it faithfully agrees with what you wanted. $\endgroup$
    – hardmath
    Jan 18, 2020 at 15:24
  • $\begingroup$ I have actually never seen this notation before. Would you mind elaborating on how this might be useful for me (perhaps as an answer of its own)? I can’t seem to find and useful information within the context of this problem. Anything would be greatly appreciated! $\endgroup$
    – nak17
    Jan 18, 2020 at 18:38
  • $\begingroup$ Looking at the Question in terms of permutations actually connects it with a topic called permutation statistics that is of classical and current research interest. I'll try to put together an Answer with some references for you. $\endgroup$
    – hardmath
    Jan 21, 2020 at 5:54
  • $\begingroup$ Thank you, I would greatly appreciate whatever work you might do! $\endgroup$
    – nak17
    Jan 22, 2020 at 2:02
  • $\begingroup$ I get that the number of arrangements is given by the coefficients of (x-1)(x-2)(x-3)...(x-(n-1)). So for example the second coefficient gives the number of ways 1 number is left of its normal position. This means that for n=5 we get 35 permutations, and for n=4 we get 11 permutations $\endgroup$
    – nak17
    Feb 7, 2020 at 22:58

1 Answer 1

3
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ Unless I’m mistaken, I don’t think this is right. For example, if we have {1, 2, 3, 4} and we wish to find the number of ways we can move two numbers to the left of their “normal” position, then it is relatively easy to count and get 11 ways, and this is out of a total of 4!=24 arrangements of this set. However, when I divide your formula by a total of n! Possibilities and do some algebra, I get (3n-1)/(12(n-3)!), however letting n=4 I get that 11/12=22/24 of the total rearrangements of this set have two numbers left of their normal position, when it’s actually 11/24 of them. Any suggestions? $\endgroup$
    – nak17
    Jan 18, 2020 at 18:35
  • 1
    $\begingroup$ Thank you for pointing out the mistake ${(a+b+c)}^2 - a^2-b^2-c^2=2(ab+bc+ca)$ $\endgroup$ Jan 19, 2020 at 3:59
  • $\begingroup$ Thank you for responding! I understand what you’ve done here with 2 numbers left of their “normal” position, but I am still not seeing how you could generalize this to say 3,4,5,.. numbers left of their normal positions. Is there something I’m missing or any help you might be able to give? $\endgroup$
    – nak17
    Jan 19, 2020 at 7:25
  • $\begingroup$ It will be difficult actually $\endgroup$ Jan 19, 2020 at 10:36
  • $\begingroup$ Why when choosing $2$ and $3$, for example, are there $1 \times 2$ possibilities? It seems to me that there is $1$ choice for where the $2$ goes, and then only $1$ choice for where the $3$ goes because it can't occupy the same spot as the $2$. We'd then get $$\sum_{1 \leq a < b \leq n} (a - 1)(b - 2) = \sum_{1 \leq a < b \leq n - 1} a(b - 1) = \sum{1 \leq a < b \leq n - 1} ab - \sum{1 \leq a \leq n - 2} a(n - 1 - a) = \frac{n^2(n - 1)^2}{8} - \frac{n(n - 1)(2n - 1){12} - \frac{(n - 1)^2 (n - 2)}{2} + \frac{(n - 1)(n - 2)(2n - 3)}{6}$$ possibilities in total. $\endgroup$
    – Dylan
    Feb 8, 2020 at 7:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .