-2

Find the number of permutation of 6 digits from the set $\{1,2,3,4,5,6\}$ where each digit is to be used exactly once, so that the chosen permutation changes from increasing to decreasing or decreasing to increasing at most once e.g. the strings like $1\ 2\ 3\ 4\ 5\ 6$, $6\ 5\ 4\ 3\ 2\ 1$, $1\ 2\ 6\ 5\ 4\ 3$ and $6\ 3\ 2\ 1\ 4 \ 5$ are acceptable but strings like $1\ 3\ 2\ 4\ 5\ 6$ or $6\ 5\ 3\ 2\ 4\ 1$ are not.

Maverick
  • 9,172
  • 2
  • 30
  • 61
  • 3
    This is not a 'do my homework for free'.service! Please show what you've tried. – barak manos Dec 29 '16 at 16:30
  • 1
    whoa, we could have said it in a nice manner. @barakmanos – Vidyanshu Mishra Dec 29 '16 at 16:32
  • 1
    @THELONEWOLF.: I did use please, didn't I? And it seems that this user has been here long enough to know this... BTW, I chose to give that comment instead of giving an arbitrary down-vote, which I think is a nicer manner by definition. – barak manos Dec 29 '16 at 16:35
  • 1
    Yes I know @barakmanos, but the problem is that people search here for sarcasm, and I know that this guy has been here for long enough, but you have been here for long long long enough, and a newbie on MSE link me, expect a nice, so nice behaviour from you. – Vidyanshu Mishra Dec 29 '16 at 16:39
  • By the way, i was also one of the voters on your comment, :) :) :) – Vidyanshu Mishra Dec 29 '16 at 16:40

1 Answers1

2

Obviously, all increasing means $1,2,3,4,5,6$ and all decreasing means $6,5,4,3,2,1$.

Now, if it's increasing then decreasing, then $1$ has to be at the beginning and we increase from there or at the end so we decrease back to $1$. It can not be in the middle because that would mean either there is a number before $1$ that increases to $1$, which is impossible because $1$ is the smallest number, or there is a number after $1$ that decreases to $1$, which is also impossible because $1$ is the smallest number. Then, if you take $1$ away, $2$ is the smallest number, so $2$ becomes either at the beginning or the end. Then, if you take $2$ away, $3$ becomes the smallest number. This continues until we get to just $6$, where there is only one possibility because there is only one number. Now, let's work backwards. Starting from $6$, $5$ can either go on the left end or right end, then $4$ can either go on the left end or right end, and et cetera for $3,2,1$. This gives us two choices for $5,4,3,2,1$, so we have $2^5=32$ possibilities here.

A similar thought process gives us $32$ possibilities for decreasing then increasing, but all increasing/decreasing sequences are repeated in both counts, so they need to be subtracted, giving us, in total, there are $32+32-(1+1)=62$ possibilities.

Noble Mushtak
  • 18,402
  • 28
  • 44