3
$\begingroup$

"Question: Find the number of permutations of 1, 2, 3, 4, 5, 6, 7 that do not have 1 in the first place, nor 4 in the fourth place, nor 7 in the seventh place.

Ans:We use the inclusion-exclusion principle with three properties of the permutations: 1 in the first place; 4 in the fourth place; 7 in the seventh place. Thus the answer is 7! - 6! - 6! - 6! + 5! + 5! + 5! - 4!"

Above is the Q&A from "Maths of Choice", I am not sure whether I got the intuition correct from the provided answer. Below is the inclusion/exclusion of each term which I think corresponds to the answer. Could somebody kindly advise whether I got the intuition right.

7! = permutations of 7 with no repetition
-6! = exclusion of 1 in the first place
-6! = exclusion of 4 in the fourth place
-6! = exclusion of 7 in the seventh place
+5! = inclusion of 2nd,3rd,4th,5th,6th,7th that were excluded when excluding 1 in the 1st place
+5! = inclusion of 1st,2nd,3rd,5th,6th,7th that was excluded when excluding 4 in the 4th place
+5! = inclusion of 1st,2nd,3rd,4th,5th,6th that was excluded when excluding 7 in the 7th place
-4! = exclusion of 2nd,3rd,5th,6th,7th that were included from the last 3 inclusions(+5!+5!+5!).

Update
According to @N. F. Taussig's answer, I should approach as such:

n = 7!
n(a) = -6!; exclusion of 1 in the first place
n(b) = -6!; exclusion of 4 in the fourth place
n(c) = -6!; exclusion of 7 in the seventh place

n(a,b) = +5!; inclusion of 1 and 4 from first & fourth place
n(a,c) = +5!; inclusion of 1 and 7 from first & seventh place
n(b,c) = +5!; inclusion of 4 and 7 from fourth & seventh place

n(a,b,c) = -4!; exclusion of 1,4,7 from first, fourth & seventh place

$\endgroup$
2
  • 2
    $\begingroup$ Yes, your analysis is spot on. For a formal elaboration of Inclusion-Exclusion, first see this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula. $\endgroup$ Commented May 24, 2022 at 7:24
  • $\begingroup$ Are you referring to the book Mathematics of Choice by Ivan Niven? $\endgroup$ Commented May 24, 2022 at 9:36

1 Answer 1

2
$\begingroup$

The term $7!$ is the number of permutations of $1, 2, 3, 4, 5, 6, 7$.

If there is a $k$ in the $k$th position, we call $k$ a fixed point. We wish to subtract those permutations which violate at least one of the three restrictions that $1, 4$ and $7$ may not be fixed points.

The first $-6!$ term subtracts those permutations with a $1$ in the first position.

The second $-6!$ term subtracts those permutations with a $4$ in the fourth position.

The third $-6!$ term subtracts those permutations with a $7$ in the seventh position.

However, we have subtracted too much. In subtracting those permutations which violate one of the three restrictions, we have subtracted each case which violates two of the restrictions twice, once for each way of designating one of the two fixed points as the fixed point. We only want to subtract such cases once. Hence, we need to add them to the total.

The first $+5!$ term adds those permutations with a $1$ in the first position and a $4$ in the fourth position.

The second $+5!$ term adds those permutations with a $1$ in the first position and a $7$ in the seventh position.

The third $+5!$ term adds those permutations with a $4$ in the fourth position and a $7$ in the seventh position.

Now, we have added too much. By first subtracting those cases in which a fixed point occurs and then adding those cases in which two fixed points occur, we have first subtracted those cases in which all three fixed points occur three times, once for each way of designating one of the three fixed points as the fixed point, then added those cases in which all three fixed points occur three times, one for each of the $\binom{3}{2}$ ways of designating two of those three fixed points as the two fixed points. Hence, we have not subtracted those cases in which $1$, $4$, and $7$ are all fixed points. We must subtract them from the total.

The $-4!$ term subtracts those cases in which there is a $1$ in the first position, a $4$ in the fourth position, and a $7$ in the seventh position.

$\endgroup$
2
  • $\begingroup$ yes, I'm referring to the book Mathematics of Choice by Ivan Niven. I've added an updated that uses your answer to interpret my understanding using set and subsets from what I've learnt from earlier chapters. Could you kindly advise whether it's correct? Thank you $\endgroup$ Commented May 24, 2022 at 10:18
  • 1
    $\begingroup$ Your update makes sense. Your original explanation for the last four terms did not make sense to me, which is why I wrote my answer. $\endgroup$ Commented May 24, 2022 at 10:43

You must log in to answer this question.

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