Dearrangement

[Saumyojit]

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be place in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same number and moreover the card numbered 1 is always placed in envelope numbered 2. Then the number of ways it can be done is?

My approach: Suppose '1' is fixed at 2nd position then there will be 120 arrangements all total including all the bad permutations and dearrangments.

Now, i need to count only bad permutations which are not dearrangements.

Suppose set A3 contains arrangements which have third letter at 3rd envelope , A4= 4th letter at 4th envelope ...
then,
Cardinality of |A3 Union A4 union A5 union A6|= the formula is summation of ((-1)^(k+1) )* (n!/k!) where k starts from 1 and ends at n where n is the no of sets right?. or n represents the last set i.e 6 ?
which one

If former, 4! [ 1/1! -1/2! + 1/3! - 1/4!] = 15 coming as n=4 there are 4 sets considered .

if Latter, then 6! * [ 1/3! -1/4! + 1/5! - 1/6!] = 95. ( no of bad permutations )

My idea is to find the no of bad permutations and subtract it from 120 to get answer. Where am i wrong?

 

[pka]

Here is a basic article on derangements. As you can see the number of derangements is:
\(\mathcal{D}(n) = n!\displaystyle\sum\limits_{k = 0}^n {\frac{{{{( - 1)}^k}}}{{k!}}}=\left\lfloor {\dfrac{{n!}}{e} + \dfrac{1}{2}} \right\rfloor \) It is interesting to explore how \(e\) becomes involved here.
In this question because the #1 is assigned to envelope 2 then the other five are deranged in \(\mathcal{D}(5)\) ways.

 

[Saumyojit]

PLease ready my thought process

i don't want another point of view as i have the solution and i can see it anytime when i will get to know where my approach is wrong.

This is a conditional dearrangement

1: that's why I have taken all the 120 permutations (5p5) where 1 is at fixed at second position but not 6!

2: if there was no condition , then bad permutations of six envelopes and six letters would represent like this
|A1 Union A2 Union A3 Union A4 union A5 union A6| = summation of ((-1)^(k+1) )* (n!/k!) where k starts from 1 and ends at n

But as there is a condition i have excluded A1 and A2 and started from A3 covering bad permutation of 3 at orignal postion , 4 at original position and pre assuming that 1 is at second envelope and then subtracting it from 120 .

@Dr.Peterson @Jomo @pka

 

[Dr.Peterson]

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be place in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same number and moreover the card numbered 1 is always placed in envelope numbered 2. Then the number of ways it can be done is?

My approach: Suppose '1' is fixed at 2nd position then there will be 120 arrangements all total including all the bad permutations and dearrangments.

Now, i need to count only bad permutations which are not dearrangements.

Suppose set A3 contains arrangements which have third letter at 3rd envelope , A4= 4th letter at 4th envelope ...
then,
Cardinality of |A3 Union A4 union A5 union A6|= the formula is summation of ((-1)^(k+1) )* (n!/k!) where k starts from 1 and ends at n where n is the no of sets right?. or n represents the last set i.e 6 ?
which one

If former, 4! [ 1/1! -1/2! + 1/3! - 1/4!] = 15 coming as n=4 there are 4 sets considered .

if Latter, then 6! * [ 1/3! -1/4! + 1/5! - 1/6!] = 95. ( no of bad permutations )

My idea is to find the no of bad permutations and subtract it from 120 to get answer. Where am i wrong?

While I agree that you are asking for an analysis of your wrong method (though you failed to tell us that you knew it was wrong because you knew the answer -- what is it?), you will also benefit from thinking about why pka's last sentence is appropriate.

As for your method, let's first clarify. If card 1 is required to be in envelope 2, then we are arranging the numbers 2, 3, 4, 5, 6 in the blanks of _ 1 _ _ _ _, so any card can be in the first, and cards 3, 4, 5, 6 can't be in the 2nd, 3rd, 4th, 5th blanks respectively. Your set A3 is all arrangements of cards 2, 4, 5, 6 in _ 1 3 _ _ _; set A4 is all arrangements of cards 2, 3, 5, 6 in _ 1 _ 4 _ _, and so on. The union of these consists of all "bad" arrangements, but they are not mutually exclusive. So you are presumably using inclusion-exclusion to find the cardinality. Am I right? Please explain the details of your thinking: That is how you decide whether a formula is right!

 

[JeffM]

PLease ready my thought process

i don't want another point of view as i have the solution and i can see it anytime when i will get to know where my approach is wrong.

This is a conditional dearrangement

1: that's why I have taken all the 120 permutations (5p5) where 1 is at fixed at second position but not 6!

2: if there was no condition , then bad permutations of six envelopes and six letters would represent like this
|A1 Union A2 Union A3 Union A4 union A5 union A6| = summation of ((-1)^(k+1) )* (n!/k!) where k starts from 1 and ends at n

But as there is a condition i have excluded A1 and A2 and started from A3 covering bad permutation of 3 at orignal postion , 4 at original position and pre assuming that 1 is at second envelope and then subtracting it from 120 .

@Dr.Peterson @Jomo @pka

As I told you in response to your private message to me, I never even took a course in combinatorics whereas pka has taught such a course. I doubt anyone at this site is better qualified to answer questions on that topic than pka. Certainly I am not.

It is true that many problems can be solved in multiple ways, but it is not true that every problem can be solved in multiple ways. If you are preparing for a test in which derangement problems will come up for the only time in your life, just memorize the formula and forget it after the test. No one person can comprehend the entire contents of mathematics. You must be selective in what you cram into your mind.

I would bet a large amount of money that if you think about valid logic trees applicable to this kind of problem, they will necessarily be equivalent and all reduce to pka’s formula. It is foolish to ignore studying a correct method because you hope to find an alternative method when there may not even be an alternaative. PKA provided a citation: use it.

EDIT: I looked at the citation. It is not for beginners. But I did notice that the first person to address this class of problem took a number of years to do so. That suggests to me that it is not a trivial problem. Learn how and when to use the formula

 

[Saumyojit]

though you failed to tell us that you knew it was wrong because you knew the answer -- what is it?

yes

they are not mutually exclusive.

set A3 is all arrangements of cards 2, 4, 5, 6 in _ 1 3 _ _ _; set A4 is all arrangements of cards 2, 3, 5, 6 in _ 1 _ 4 _ _, and so on. yes I plan to find how many permutations are there of A3 ,4 ,5,6 and then subtract it from 120.

If two events have no elements in common (Their intersection is the empty set.), the events are called mutually exclusive.

On, A3 intersect A4 ; suppose one of bad permu of A4 (4 is at 4th postition and 1 at 2nd) is 213465 and one of bad permu of A3(3 is at 3rd positition and 1 at 2nd) is 213465 so they are not mutually exclusive .

So whats wrong?

Am I right?

Yes always .

Dave Peterson – The Math Doctors

www.themathdoctors.org

are you this person? right?

You worked in google?

 

[Dr.Peterson]

yes

That's not the answer to that question ("what is it?")!! What is the solution to the problem that you know? Give a number, if not a method.

set A3 is all arrangements of cards 2, 4, 5, 6 in _ 1 3 _ _ _; set A4 is all arrangements of cards 2, 3, 5, 6 in _ 1 _ 4 _ _, and so on. yes I plan to find how many permutations are there of A3 ,4 ,5,6 and then subtract it from 120.

If two events have no elements in common (Their intersection is the empty set.), the events are called mutually exclusive.

On, A3 intersect A4 ; suppose one of bad permu of A4 (4 is at 4th postition and 1 at 2nd) is 213465 and one of bad permu of A3(3 is at 3rd positition and 1 at 2nd) is 213465 so they are not mutually exclusive .

So whats wrong?

Why don't you answer my actual questions??

I asked, "So you are presumably using inclusion-exclusion to find the cardinality. Am I right? Please explain the details of your thinking." Showing me what I already told you, that your sets are not mutually exclusive, doesn't tell me what I am not sure of, which is whether your formula comes from a thoughtful application of inclusion-exclusion, or from something else.

 

[Saumyojit]

What is the solution to the problem that you know?

I don't care about the solution . I want to know where my Approach is wrong . The answer is 53.

your formula comes from a thoughtful application of inclusion-exclusion,

Dearrangement formula when i learned few days ago I derived using inclusion and exclusion. Yes I am finding the cardinality of union of 4 sets .

So you are presumably using inclusion-exclusion to find the cardinality. Am I right?

yes , please tell me where am i wrong. PLEASE GO THROUGH POST3

 

[pka]

I don't care about the solution . I want to know where my Approach is wrong . The answer is 53.
Dearrangement formula when i learned few days ago I derived using inclusion and exclusion. Yes I am finding the cardinality of union of 4 sets .
yes , please tell me where am i wrong. PLEASE GO THROUGH POST3

The answer is not 53, it is \(\mathcal{D}(5)=44\) see here. This is the solution: Card #1 is is always in envelope #2.
So one is fixed and the remaining five must go into an envelope of a different number than itself: \(\mathcal{D}(5)=44\).

 

[Cubist]

The answer is not 53, it is \(\mathcal{D}(5)=44\) see here. This is the solution: Card #1 is is always in envelope #2.
So one is fixed and the remaining five must go into an envelope of a different number than itself: \(\mathcal{D}(5)=44\).

This isn't a standard derangement. The answer does seem to be 53 (via computer)

card   envelope  
1        2  ALWAYS

remaining...
card   envelope  
2        1   <- this card can go into ANY of the remaining envelopes, since no remaining envelope has a "2", see *
3        3
4        4
5        5
6        6

* and also any card can go into envelope 1

 

[Cubist]

I would bet a large amount of money that if you think about valid logic trees applicable to this kind of problem, they will necessarily be equivalent and all reduce to pka’s formula

DRAT - I should have taken that bet before I wrote post#10 ??

 

[Dr.Peterson]

You worked in google?

Why in the world would you think that???

By the way, I just got back from a vacation and am busy catching up with other things, so I'm not able to spend time digging deeply into the details of your work, and am too hot to trust my thinking if I did.

But it will help greatly if you would fill in the details as I've asked. Show us the formula you are applying (which includes the definitions of variables), and how you apply it to this problem in detail. The fact that you say

where k starts from 1 and ends at n where n is the no of sets right?. or n represents the last set i.e 6 ?
which one?

tells me that you are asking how to apply the formula, so we need to see your reasoning for each of the two possibilities you mention (or any others you omitted), and also what answer you get in each case. Post #3 is very hard to follow; slow down and show details. When math gets confusing, you slow down and take small steps -- and show them to your helpers!

 

[JeffM]

DRAT - I should have taken that bet before I wrote post#10 ??

I still suspect that the logic trees end up with the same formula.

 

[Cubist]

This isn't a standard derangement. The answer does seem to be 53 (via computer)

The simple way to calculate this result is [MATH] \frac{\mathcal{D}(6)}{5}=53 [/MATH]
This works because card 1 can ONLY go into envelope 2, not into envelopes 2,3,4,5 or 6 (5 possibilities) as \( \mathcal{D}(6) \) would imply.

I still suspect that the logic trees end up with the same formula.

But the derangement formula (on its own) isn't a correct solution for the post#1 question

 

[JeffM]

The simple way to calculate this result is [MATH] \frac{\mathcal{D}(6)}{5}=53 [/MATH]
This works because card 1 can ONLY go into envelope 2, not into envelopes 2,3,4,5 or 6 (5 possibilities) as \( \mathcal{D}(6) \) would imply.


But the derangement formula (on its own) isn't a correct solution for the post#1 question

Actually, I did not mean to imply that. Just that at the end of the branches you would find the formula being used.

 

[Saumyojit]

Using my approach 53 has come .
I did it using inclusion and exclusion of A3 to A6 union.

 

[Saumyojit]

@Dr.Peterson @pka

In how many permutations of 5different things taken 3 at a time will 2 particular thing always occur.
Now the question is 2 particular thing always occur means what ?

They will always be together in every arrangements or can be both seperate and together.
I feel the latter.


Keeping two particular people fixed then choosing 1 out of 3 people remaining then 3 ways .
After that three chosen people are rearranging themselves in 6 ways .
3*6=18
But 12 is answer

 

[pka]

@Dr.Peterson @pka
In how many permutations of 5different things taken 3 at a time will 2 particular thing always occur.
Now the question is 2 particular thing always occur means what ?
They will always be together in every arrangements or can be both seperate and together.
I feel the latter. Keeping two particular people fixed then choosing 1 out of 3 people remaining then 3 ways .
After that three chosen people are rearranging themselves in 6 ways . 3*6=18
But 12 is answer

If the group is \(A,~B,~X,~Y,~Z\) where \(A~\&~B\) are fixed.
If it means that \(A~\&~B\) are always together then
\(\{B,A,X\}\), \(\{A,B,X\}\), \(\{X,A,B\}\)\(\{X,B,A\}\) that is four ways.
If we replace \(X\) with \(Y\) or \(Z\) we get \(12\) total.
But \(18\) is correct given the way it is written.

 

[Dr.Peterson]

@Dr.Peterson @pka

In how many permutations of 5different things taken 3 at a time will 2 particular thing always occur.
Now the question is 2 particular thing always occur means what ?

They will always be together in every arrangements or can be both seperate and together.
I feel the latter.


Keeping two particular people fixed then choosing 1 out of 3 people remaining then 3 ways .
After that three chosen people are rearranging themselves in 6 ways .
3*6=18
But 12 is answer

The question as written is unclear. I doubt that I have ever seen that wording in a problem.

If, as pka propposes as an alternative, it was really "two particular things always occur together", which is a common idea in problems, then we can treat them as one item, so that we are always choosing that pair (which can be in either order), and choosing 1 of the 3 others (which can be done in 3 ways), and arranging the two items (a pair and an individual, which can be done in 2 ways), so the total number of ways is 2*3*2 = 12. So that is likely what the problem. If it said "together" and you omitted it, then the fault is yours for not quoting the problem exactly.

If it means (as it needs to be taken despite its oddness, in the way you worded it) merely that A and B must both be chosen, along with one other, then (as you say) there are 3 ways to choose the other, and 3! = 6 ways to arrange all three, for a total of 3*6 = 18 arrangements.

Now the question is "2 particular thing always occur" means what ?

It has no proper meaning, if you are expecting it to be a standard wording in such problems. To get 18, I would have said something like "Two specified items are required".