7
$\begingroup$

Problem:

Among all the possible permutations of the set $\{1, 2, 3, 4, 5\}$, in how many fulfills that:

  1. the element $1$ is in the first position?
  2. the element $2$ is in the second position?
  3. the first three elements occupy the first three positions?
  4. Any of first three elements is not in their correct position?

What have I tried?

#1:

If the element $1$ remains in first position I see it as a permutation of the other elements which is:

$$ 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 $$

#2:

I see this problem as the same as the first question but just for another element so I believe it to be the same answer which is:

$$ 4! = 24 $$

#3:

If the first three elements remained in their original positions, I see that as a permutations of the remaining 2 elements which appears to be:

$$ 2! = 2 \cdot 1 = 2 $$

#4:

$\color{red}{\text{I am not sure how to correctly proceed with this question. }}$

But from my understanding, it would be a situation where:

  • The first element remains in it's original position with permutations of the other element then the same for the second then the third element.

  • Also, when the first two elements remain, then the second two and finally the first and third.

And would it be correct that it is the same as:

$$ 3(4!) + 3(3!) = 3\cdot24 + 3\cdot6 + 2 = 72 + 18 = 80 $$

Would these be correct and if not where did I go wrong and how do I correct it?

$\endgroup$
  • 4
    $\begingroup$ Concerning #3, it doesn't say that the first three must occupy their original positions, it says that the first three must be in the first three positions. $3!$ ways for three elements to be in three positions. Then $2!$ for the other two. Thus the answer is $3! \cdot 2!$. $\endgroup$ – Joel Dec 30 '17 at 22:03
  • 2
    $\begingroup$ For #4, just observe that the opposite of "any of the first three is not in its position" is "all of the first three are in their position", $\endgroup$ – celtschk Dec 30 '17 at 22:07
  • $\begingroup$ @celtschk Would that be the same as $5! - 2!$? $\endgroup$ – Omari Celestine Dec 30 '17 at 22:32
  • $\begingroup$ @OmariCelestine: Yes. $\endgroup$ – celtschk Dec 31 '17 at 7:01
1
$\begingroup$

No. 3

It is said that the first 3 occupy first three places so 1, 2 and 3 can be arranged among themselves in 3! ways. So total number of ways these can be arranged = 2! x 3! = 12

No. 4

enter image description here

$\endgroup$
  • $\begingroup$ I've read number 4 as "at least one of the first three is not in the correct position", while you apparently read it as "none of the first three is in the correct position". $\endgroup$ – celtschk Jan 16 '18 at 10:35
3
$\begingroup$

For #4, you can use Inclusion-Exclusion principle -

$|U| = 5!$ (The general case, "universe")

$|\bigcup \limits_{i=1}^n A_i|$ = $3\cdot4! - 3\cdot3! + 2!$ (we use it to avoid double counting)

By combining them we get,

$|U| - |\bigcup \limits_{i=1}^n A_i| = 5! - 3\cdot4! + 3\cdot3! - 2! = 64$

$\endgroup$
  • $\begingroup$ Why subtract the $2!$? $\endgroup$ – Omari Celestine Dec 30 '17 at 23:11
  • 1
    $\begingroup$ That's the Inclusion-Exclusion principle, we define $|\bigcup \limits_{i=1}^n A_i|$ as - $|M \cup P \cup C|=|M|+|P|+|C| -|M\cap P|-|M \cap C|-|P \cap C|+ |M \cap P \cap C|$ (M,C,P would be ball 1,2,3 not in their correct position) Thus, subtracting From the general case, $|U|$ we get - $|U| -(|M|+|P|+|C|) +|M\cap P|+|M \cap C|+|P \cap C|- |M \cap P \cap C|$ (the last one is 2!, hence we subtract it) I guess it would be better if you read the usage in Wikipedia, it's really simple. $\endgroup$ – Yariv Levy Dec 30 '17 at 23:14
  • $\begingroup$ Given that there are already $4\cdot 4!=96>64$ permutations where the first element is not $1$, and those are a subset of those where any of the first three elements is not in its place, it is obvious that your calculation cannot be correct. $\endgroup$ – celtschk Dec 31 '17 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.