ISI 2004 MIII

Question

The number of permutation of $\{1,2,3,4,5\}$ that keep at least one integer fixed is.

• A. $81$
• B. $76$
• C. $120$
• D. $60$

Comments

I think C is answer

---

Total possible permutation - No element is fixed( De-arrangement) = Atleast one is fixed.

5! - $120\times \left [ \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} \right ]$

120 - 44 = 76

---

Another way to calculate Dearrangement floor(5!/e)=44

ans 120-44=76

---

Hii akshat, in this formula, we need to take closest value to any integer, not nacessarily floor or ceil.

Answer 1

It is based on inclusion exclusion principle:

Total arrangements - derangements 

$\begin{align}&=5!-[5!-^5C_1(4!)+^5C_2(3!)-^5C_3(2!)+^5C_4(1!)-^5C_5(0!)]\\&=^5C_1(4!) - ^5C_2(3!) + ^5C_3(2!) -^5C_4(1!) +^5C_5(0!)\\&=120 - 60 + 20 - 5 + 1\\ &= 76.\end{align}$ 

Correct Answer: $B$

Comments

@Arjun Sir can you plz explain the concept of derangement in detail and why did we applied it here?

---

There is no need to bring the concept of derrangments here. 
 

Total arrangements - derangements  (Not Required).

No need to extra Minus, Simple Inclusion-Exclusion should be used.

"At least" means ->{Any one element is  Fixed, Any two elements are fixed,...........All n elements are fixed}.

5C₁(4!) - 5C₂(3!) + 5C₃(2!) - 5C₄(1!) + 5C₅(0!)= 120 - 60 + 20 - 5 + 1 = 76 

 Choose Any One of The Five Element and arrange rest in 4! ways(first term)+.........

This Equation is enough for the explanation.

---

Why there is alternate addition-subtraction ?

---

you can find here why.
https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

Answer 2

Here many people is mis understand this question so that they get 120 as answer which is wrong. So we first understand the question.

Given that ATLEAST ONE INTEGER FIXED, which means you can take any permutation and in that permutation atleast one integer is on its actual place and others are not.

EG:  12345 is given so possible permutation with one integer(1) is fixed 13245, 14523, 15432 etc... now one integer(2) is fixed 32154, 42153, 52134 etc...likewise only one integer is fixed

Now two integer(12) is fixed 12534, 12453 etc... likewise we have to fix 3 and 5 integer also, Here keep in mind that we can't make any permutation with fixing 4 integers coz in that case last integer has to fit in actual place coz no dearrangement is possible.   

Here all the permutations in which every integer is dearrange is not included in our answer.

so our answer is 5!-D5=76        where D5 is dearrangement of 5 integer.                                                               

Answer 3

Correct Option: (B) 76

Let, $S = \left \{ 1, 2, 3, 4, 5 \right \}$,

$S_1, S_2, S_3, S_4, S_5$ be the the five integers,

$|S_i|$ where $i \in S$ mean that integer $S_i$ is fixed .

Now, we want to find the no. of permutations in which at least 1 integer is fixed.

In other words, we want to find $|S_1 \cup  S_2 \cup S_3 \cup S_4 \cup S_4 \cup S_5|$.

Now, according to the Principle of Arrangement and De-arrangement, we have

 

$|S_1 \cup  S_2 \cup S_3 \cup S_4 \cup S_4 \cup S_5| = \sum_{i \in S}|S_i| - \sum_{i, j \in S \ \land \  i \neq j}|S_i \cap S_j| + \\ \sum_{i, j, k \in S \ \land \ i \neq j \neq k}|S_i \cap S_j \cap S_k| - \sum_{i, j, k, l \in S \ \land \ i \neq j \neq k \neq l}|S_i \cap S_j \cap S_k \cap S_l| + \\ \sum_{(i, j, k, l, m \in S \ \land \ i \neq j \neq k \neq l \neq m}|S_i \cap S_j \cap S_k \cap S_l \cap S_m|$

 

Now,

$\sum_{i \in S}|S_i| = \binom{5}{1} \times 4! = 120$

$\sum_{i, j \in S \ \land \  i \neq j}|S_i \cap S_j| =  \binom{5}{2} \times 3! = 60$

$\sum_{i, j, k \in S \ \land \ i \neq j \neq k}|S_i \cap S_j \cap S_k| = \binom{5}{3} \times 2! = 20$

$\sum_{i, j, k, l \in S \ \land \ i \neq j \neq k \neq l}|S_i \cap S_j \cap S_k \cap S_l| = \binom{5}{4} \times 1! = 5$

$\sum_{(i, j, k, l, m \in S \ \land \ i \neq j \neq k \neq l \neq m}|S_i \cap S_j \cap S_k \cap S_l \cap S_m| = \binom{5}{5} = 1$

 

$\therefore$ We finally have,

$|S_1 \cup  S_2 \cup S_3 \cup S_4 \cup S_4 \cup S_5| = 120 - 60 + 20 - 5 +1 = 76$

 

 

Answer 4

Derangement means no elements should appear in its original position so derangement of 5 means all 5 elements do not appear on its original position.

So if we subtract D5 from total ways we shall get numbers in which at least one element is fixed because we already subtracted those elements where all 5 elements do not appear on same position hence only that elements are remaining where at least one element is fixed in its original position.

Total ways = 5!
D5(derangement of 5) = 44 (apply formula)
 Desired output:     5!-44 = 76

Hence correct answer is option B

 

 

Answer 5

Answer C

There are five places

                                         __  __  __  __  __ 

And we are given five integers {1, 2, 3, 4, 5}

And we are supposed to fix one integer

• Let me fix integer $1$ at position 1

                                        1  __  __  __  __ 

Now at other four places I can keep the any integers, other than the one already used i.e. 1

So, at second position {2, 3, 4, 5} any one can be kept. There are total $4$ possible options

• Let me keep $2$

Now, at third position {3, 4, 5} any one can be kept
There are total $3$ possible options

• Let me keep $3$

So, at fourth position {4, 5} any one can be kept
There are total $2$ possible options

• Let me keep $4$

Now can fifth position only {5} can be kept as that is the only one left
There is only $1$ possible option

So, overall, when I keep $1$ fixed on position 1 there are total $4*3*2*1$ which is $24$ possible options

Instead of keeping $1$, I can keep any of {1, 2, 3, 4, 5} integers. So there are total $5$ options when it comes to keeping a number on position 1

And with each number which I keep on position 1, there are $24$ possible options of placing other integers at other places

So, in all, there are $5*24$ which is $120$ possibilities

Comments

You can select 1 integer out of 5 this can be done in 5C1 way  remaining can be arranged in 4! Ways so total no of ways are 4!*5 equals 120 here