Permutation & Combination

Saumyojit

Senior Member
Joined
Jan 21, 2020
Messages
1,032
In how many ways can we put 4 different letters into 4 different envelopes so that all the letters go into the wrong envelopes?

Don't have to tell the solution . Just give a hint how to approach and check where my logic is going wrong .

My approach:

In how many ways can we put 4 different letters into 4 different envelopes?

then this would be 24 ways.

But the question asks letters into wrong envelopes.

RIGHT envelope means Letter 1 is assigned to E1 envelope, Letter 2 is assigned to Envelope 2 etc particularly

E1E2E3E4
L2L1L3L4
L2L1L4L3
L1L2L4L3
L1L3L2L4
L1L3L4L2
L1L4L2L3
L1L4L3L2
L2L3L1L4
L2L3L4L1

L3L2L1L4
L3L2L4L1
L3L4L2L1
L4L3L2L1
L3L4L1L2
L4L3L1L2

HERE in many Combinations all the letters at the same time are not going into wrong envelopes.
These are the combinations of letters in worst envelope.
Where am i wrong?
 
Last edited:
okay ANSWER 9 has come . This is right.

All the letters are in the wrong envelope means all the letters should be in the wrong envelopes at each one particular event.

But
it has come by the above table method which is not the proper way of solving .
what if there were 8 letters 8 envelopes . Then by breaking down it would take long time .

@JeffM but we need to find a formula/ Method through which I dont need to break down just like above in the table.

L3 L2 L4 L1
This is wrong as L2 is in the right envelope .
 
Last edited:
This is a well studied area of counting theory. It is know as the problem of Derangements
Arrangements in which on item is in its correct position. The general formula is: \(\mathcal{D}(n) = n!\,\displaystyle{\sum\limits_{k = 0}^n {\frac{{( - 1)^k}}{{k!}}} }\)
In the case that \(n=4\) we have \(4!\left[ 1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right]=9\).
There are nine ways to place four letters into four envelops none in the correct envelope.
 
This is a well studied area of counting theory. It is know as the problem of Derangements
Arrangements in which on item is in its correct position. The general formula is: \(\mathcal{D}(n) = n!\,\displaystyle{\sum\limits_{k = 0}^n {\frac{{( - 1)^k}}{{k!}}} }\)
In the case that \(n=4\) we have \(4!\left[ 1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right]=9\).
There are nine ways to place four letters into four envelops none in the correct envelope.
Yes I got the logic.
All the permutations - permutations which are not dearrangement

But we can do this without the formula , without knowing what is dearrangement also .
Please think on it.

Actually one friend told me that if u think deeply we can avoid dearrangement formual and can do it using combination formula .



I thought but nothing came to my mind please help
 
Yes I got the logic.
All the permutations - permutations which are not dearrangement

But we can do this without the formula , without knowing what is dearrangement also .
Please think on it.

Actually one friend told me that if u think deeply we can avoid dearrangement formual and can do it using combination formula .



I thought but nothing came to my mind please help
@Saumyojit

This is a silly post. You ASKED for a formula and now complain that that is all you got.

Your friend is obviously correct that you can solve the problem without knowing pka’s formula. You can solve it with a logic tree. Now, as you yourself pointed out in your first post, that method might become a tad impractical if we were talking about 100 letters and 100 envelopes.

I suspect that your friend is correct that you can do this kind of problem using permutations and combinations. I further suspect that the formula you get using permutations and combinations can be reduced algebraically to pka’s formula. Moreover, the presence of minus 1 in pka’s formula suggests to me the inclusion-exclusion principle at is work in the derivation of pka’s formula.
 
Last edited:
Top