How Many Ways to Misplace Letters and Form Specific Subsets?

[doktorwho]

Homework Statement

Using the common logic and known combinatorics properties solve the following problems:

a) If you have 6 letters and 6 envelopes, each having it's corresponding envelope in how many ways can you place every letter in the wrong envelope? (1 letter goes into 1 envelope)

b)You have been given a set $A={1,2...50}$. Determine the number of subsets of A that have 5 elements, which don't include 45 and which don't include two succesive numbers.

Homework Equations

3. The Attempt at a Solution [/B]
The first one should be relativly simple and i just wanted to check my result with you.
Lets say you have the first envelope. Number of wrong letters that you can put into it is 5 and so on for the every envelope and the result is $5^6$. Do you agree?

The second one is what I am really curious about. I thought of it the similar way i did with the upper problem.
Lets say i want to create that subset. I have 5 empty places for the elements. I can't have 49 and that leaves me with 49 possibilities. For the second place i can have 48 possibilities because i can't have 49 and the successor of the one in the first place.
That leaves me with the result $49*48^4$. What do you think?

 

[scottdave]

You sort of started off on the right track. Indeed, for the first envelope: you have 1 letter which is correct, and 5 incorrect. But on the second envelope, we have 2 situations. One is that the 2nd letter was put into the first envelope. Since that is no longer available, any of the 5 remaining can be put in the 2nd envelope. The other possibility is that something other than the 2nd letter was put into the first envelope, so there are 4 possible can go in the 2nd envelope.

 

[doktorwho]

The mistake on part a) is foolish and i counted more envelopes than there are. Now i thin i need to go this way. The number os combinations that i put at least one envelope correctly is 5!. So my solution should be 6!-5! i presume. Don't have the solution so i don't know

 

[haruspex]

should be 6!-5!

This is the well-known derangements problem. The solution is not trivial. Are you familiar with the principal of inclusion-exclusion?
That method also applies to the second problem.

 

[scottdave]

Yes derangement is the term for this type of problem. I remember it now, that haruspex mentioned it.
To test whether your method may yield the correct solution, try it out on smaller sets: 3 envelopes, and 3 letters. In the first envelope, you need to have either #2 or #3. Look at each of these individually (like a flowchart). If #2 is in the first envelope, then you must put #3 in the second envelope, because #3 cannot go in the 3rd envelope. That leaves #1 in the 3rd. If #3 is in the first envelope, then #1 must go in the 2nd envelope, and #2 will be in the last. So there are only 2 ways to do for 3 envelopes. Can you expand this out with 4 or more?
So if your 6! - 5! is the correct solution, then 3! - 2! should be the correct solution for 3 envelopes. 3! is 6, and 2! is 2 so that yields 4, but the correct answer for 3 envelopes is 2.
If you look at 4 envelopes, there are only 3 choices to put in envelope 1, then it turns out for each of those 3, there are 3 possible sets for the rest of the envelopes. 3 x 3 is 9. So it may be that figuring out how many possible sets after the first one is chosen may be the way to expand this out for more complex problems (without having to go through every combination). You may find it worthwhile to watch this video on derangements as it applies to Secret Santa.

 

[doktorwho]

This is the well-known derangements problem. The solution is not trivial. Are you familiar with the principal of inclusion-exclusion?
That method also applies to the second problem.

This is the well-

Yes derangement is the term for this type of problem. I remember it now, that haruspex mentioned it.
To test whether your method may yield the correct solution, try it out on smaller sets: 3 envelopes, and 3 letters. In the first envelope, you need to have either #2 or #3. Look at each of these individually (like a flowchart). If #2 is in the first envelope, then you must put #3 in the second envelope, because #3 cannot go in the 3rd envelope. That leaves #1 in the 3rd. If #3 is in the first envelope, then #1 must go in the 2nd envelope, and #2 will be in the last. So there are only 2 ways to do for 3 envelopes. Can you expand this out with 4 or more?
So if your 6! - 5! is the correct solution, then 3! - 2! should be the correct solution for 3 envelopes. 3! is 6, and 2! is 2 so that yields 4, but the correct answer for 3 envelopes is 2.
If you look at 4 envelopes, there are only 3 choices to put in envelope 1, then it turns out for each of those 3, there are 3 possible sets for the rest of the envelopes. 3 x 3 is 9. So it may be that figuring out how many possible sets after the first one is chosen may be the way to expand this out for more complex problems (without having to go through every combination). You may find it worthwhile to watch this video on derangements as it applies to Secret Santa.

I am not familiar with the topic but i will look into it. Also I am about to watch the video so hopefully i shall be posting my work in a while.

 

[haruspex]

I am not familiar with the topic but i will look into it. Also I am about to watch the video so hopefully i shall be posting my work in a while.

Ok, but I would expect your coursework to have covered the inclusion-exclusion principle before posing these problems. If not, look it up.

 

[StoneTemplePython]

My favorite solution for a Derangements problem comes in problems 45 and 46 of Mosteller's Fifty Challenging Problems in Probability. It helps if you do problem 30 first (or have prior familiarity with Poisson distributions) as the analogy between sampling with and without replacement is worth spending time thinking on when you're done.

Note that he actually derives the distribution for r matches given n envelopes, so inclusion exclusion just falls out in the end for the special case of r = 0. The book is like $6 on Amazon with delightful explanations for many problems, though I've heard "free" copies can be found on the Internet.

Technically OP's post is about combinatorics, not probabilities -- but if the probability is found, the denominator (total permutations) is easy to find, and from there probability * denominator = numerator (i.e. answer).

 

[Ken Miller]

I think the first problem actually has a simple solution. Can't one calculate the total number of ways to put 6 letters into 6 envelopes? Then how many ways get it right? Then simple subtraction...?

 

[haruspex]

how many ways get it right?

It depends what you mean. For your method to work, that would be the number of ways of getting at least one right. How will you calculate that?

 

[Ken Miller]

Oh, right. I misunderstood, and was thinking of a much simpler problem.