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
  • 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, 2017 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, 2017 at 22:07
  • $\begingroup$ @celtschk Would that be the same as $5! - 2!$? $\endgroup$ Dec 30, 2017 at 22:32
  • $\begingroup$ @OmariCelestine: Yes. $\endgroup$
    – celtschk
    Dec 31, 2017 at 7:01

2 Answers 2

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$
3
  • $\begingroup$ Why subtract the $2!$? $\endgroup$ Dec 30, 2017 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, 2017 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, 2017 at 7:10
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$
1
  • $\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, 2018 at 10:35

You must log in to answer this question.

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