Cards and envelopes permutation problem

[Raghav Gupta]

Homework Statement

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be placed 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
264
265
53
67

Homework Equations

There are many permutations formulas. Some say to learn it not telling the reason behind it.

The Attempt at a Solution

I think here some formula is applicable of degenerate theorem of permutation but what is the intuition behind it?
It is better to analyse a formula before applying it anywhere.

 

[BvU]

Hello Raghav.

No general formulas here.

But your part so far has only been to reproduce the problem statement.
No equations, no effort. Just some musing. Not good enough by PF standards ! And I know you can do better !

You'll have to do some thinking !

 

[Raghav Gupta]

Okay,
So since card 1 is placed in envelope number 2. It is fixed,
so we have 5 envelopes and 5 cards left in which we can do some arrangements.
Envelopes are 1, 3,4,5,6
And cards 2,3,4,5,6.
Now same card can't go in same envelope and one envelope must contain one card.
Suppose we put 2 card in 1 envelope, then 3rd in 4 etc. so many cases!
Also n_Cr = n!/(n-r)!r!

 

[BvU]

Very good. Card 1 into envelope 1 can only be done 1 way.

You have an equation that tells you the number n_Cr of ways to make a group of size r from n items.
You can learn it by heart or you can understand it:

For the first member of the group you have n choices
For the 2nd member of the group you have n-1 choices
For the 3rd member of the group you have n-2 choices
...
For the r th member of the group you have n-r + 1 choices

Product is n!/(n-r)!
But you have overcounted by the number of ways to order r items, so a factor 1/r!​

But in this exercise you only put one card in one envelope, so not much use for your formula ?

Number of ways to order your five remaining cards is only 5! Which already eliminates half of your answer options!
There are more conditions to fulfil, so 120 isn't one of the answers (but 67 + 53 = 120 !).

For the rest of the cards, card #2 can go in five places, but the others can't go into their own envelope, only in four places.

So there's a distinction between #2 in envelope 1 and #2 in one of the other envelopes. Those last four should each give the same number of possibilities, so you only have to find that number for e.g. #2 in envelope 3. Still work, but not that much any more. And who knows, you discover a smarter way !

(I cheated, so I know the answer now...)

 

[Raghav Gupta]

Yeah, there was a pattern.
When I place #2 in 1st envelope I get 9 ways.
When I place #2 in other envelopes for example in 3 , I get 11 ways. Now placing that in 4 we will get same ways, till 6th envelope. So 4*11 = 44.
Total ways = 44 + 9 = 53.
Thanks BvU. ( You have been helpful to me in many threads ).
Now how we can apply it to larger number of cards?
And what was your cheating?

 

[BvU]

Well done !
I think a larger number of cards would be just as messy.
My cheating was that I simply made the list of 120 numbers (in Excel ) and checked which ones qualified and which ones didn't ...
There's even a name for that method: it's called brute force

 

[haruspex]

This is an example of a derangement. You can apply the principle of inclusion and exclusion.
Forget the '1 goes in 2' constraint for the moment.
The total permutations are n! From that, we need to subtract those where 1 goes in 1, (n-1)!, and similiarly for 2 in 2 etc., giving n!-(n-1)!n. But we've subtracted the 1 in 1 and 2 in 2 twice, so we need to add those back in, and similarly the other pairs: +(n-2)!*n(n-1)/2. Continuing this process we get n!-n!+n!/2!-n!/3!... = n!(1/0!-1/1!+1/2!-1/3!...1/n!). In the limit, that tends to n!/e. Note that if we take it to be exactly n!/e then the error is O(1/n), so we can cheat by simply rounding n!/e to the nearest integer. For n=6, 264.8 or so rounds to 265.

Now to bring in the 1 goes in 2 constraint. I'll pose that as an exercise: what does that constraint do to the 265?

 

[Raghav Gupta]

The total permutations are n! From that, we need to subtract those where 1 goes in 1, (n-1)!, and similiarly for 2 in 2 etc., giving n!-(n-1)!n. But we've subtracted the 1 in 1 and 2 in 2 twice, so we need to add those back in, and similarly the other pairs: +(n-2)!*n(n-1)/2. Continuing this process we get n!-n!+n!/2!-n!/3!... = n!(1/0!-1/1!+1/2!-1/3!...1/n!). In the limit, that tends to n!/e. Note that if we take it to be exactly n!/e then the error is O(1/n), so we can cheat by simply rounding n!/e to the nearest integer. For n=6, 264.8 or so rounds to 265.

Now to bring in the 1 goes in 2 constraint. I'll pose that as an exercise: what does that constraint do to the 265?

I'm not understanding this proof correctly.In that bold part how we have subtracted 1 in 1 and 2 in 2 twice?

 

[haruspex]

I'm not understanding this proof correctly.In that bold part how we have subtracted 1 in 1 and 2 in 2 twice?

I subtracted all perms in which card 1 ends up in envelope 1, and all perms in which card 2 ends up in envelope 2. So any perm in which both of those happen has been subtracted twice.
Google principle of inclusion and exclusion.

 

[Raghav Gupta]

I subtracted all perms in which card 1 ends up in envelope 1, and all perms in which card 2 ends up in envelope 2. So any perm in which both of those happen has been subtracted twice.
Google principle of inclusion and exclusion.

Okay.

Now to bring in the 1 goes in 2 constraint. I'll pose that as an exercise: what does that constraint do to the 265?

Now when we have put 1 in 2 constraint, the 5 more cases are gone.
So total ways = 265/5 = 53.
Thanks.

 

[BvU]

Bravo Haru ! Very elegant and much more scalable than a brute force approach. I fell for the attractive reduction by a factor of 6 far too early and it became messy. Much better to postpone as you did. Awesome.