Ways to put letters in postboxes

[fireflies]

Homework Statement

There are 7 different postbox, and 10 identical letters. How many ways can the letters put into the boxes so that there is at least one letter in a postbox?

Homework Equations

nCr=n!/(n-r)!r!

If M,N,O... things can be done in m,n,o... ways then ways of doing them together is m*n*o..

The Attempt at a Solution

First I tried to put 7 letters in 7 boxes. It can be done in 1 way only as all the letters are identical. Then I tried to put the rest three letters in the box. Let us mark the letters as A, B and C (just to describe easily). While putting A in a box, for every box there are two solutions, either yes you put or no you don't put. So ways are 2^7. But it also includes that you don't put it any boxes. So, actual ways are 2^7-1. Same for letter B and C. So total ways can be (2^7-1)^3 = 2048383 ways.

The problem solution was given a number something less than 100. I think the first step maybe a problem where I said ways to put 7 letters is 1. But then the answer is going to be bigger, not less than 100 anyways. I asked the one who gave this problem about my solution, he couldn't answer. It was on facebook and not on my id. And I don't remember how his solution was. Can anybody tell me where the problem is?

 

[Borg]

Since you have to have one letter in each box, the number of combinations is the same as the number of ways to arrange 3 idential letters in 10 different boxes. Does that make it easier for you?

 

[fireflies]

Yes, but how to put these three in 7 boxes (Maybe you mistook 10)? Is my second step to solve this a good approach?

 

[fireflies]

Maybe the solution given there was

1) All three letters in same box in 7C1

2) 2 letters in a box and rest in another box in 7C1*6C1

3) 3 letters in 3 different boxes in 7C3

Then sum of case 1, 2 and 3.

This makes sense to me. But what's wrong with my concept then?

 

[RUber]

Fireflies, in your original method, you not only are allowing for no box to get a letter from the leftover 3, but also for every box to get a letter (7>3). That is why your solution is so large.
--As you just posted--
You have the options to put:
1 additional letter into 3 boxes
2 additional letters into 1 box and 1 letter into another
3 additional letters into 1 box
This is a good way to look at the problem.

 

[Borg]

Yes, but how to put these three in 7 boxes (Maybe you mistook 10)? Is my second step to solve this a good approach?

Yes, I misread. With 3 letters spread across 7 boxes.

Then sum of case 1, 2 and 3.

The case that you have here is if all of the boxes are identical.
Yech, another misread.

 

[fireflies]

Yes, all the boxes are not identical. That's my point. Well, I subtracted that 1 to confirm no box is selected. But that includes all yes options too. Now I get what's the actual mistake hete

 

[fireflies]

Then if I say in this way, can this be right-
For letter A to select a box is 7C1. Same for letter B and letter C? So, finally (7C1)^3

Or it is wrong as the letters are identical?

 

[Borg]

Since the letters are identical, there are only 7 ways to fill a box with 3 letters. Does that make sense?

 

[RUber]

Then if I say in this way, can this be right-
For letter A to select a box is 7C1. Same for letter B and letter C? So, finally (7C1)^3

Or it is wrong as the letters are identical?

That would be wrong, since with identical letters AC = AB, so 7^3 includes combinations with AC, AB, BC in the same box counted as distinct outcomes.

 

[fireflies]

So, you are saying that the way with three cases (in #4) is correct? What would be the case then if the post-boxes were identical?

 

[fireflies]

Since the letters are identical, there are only 7 ways to fill a box with 3 letters. Does that make sense?

No, how? The post boxes are not identical. 3 letters in each box itself is going to be 7 ways. 2 in one box rest in other can add more choices like box no 1,2; 2,1; 1,3 etc. 3rd case will give extra choices.

 

[Borg]

Post #5 gives you the 3 variations that you have to consider.
Post #9 gives you the answer to one of those variations.

 

[fireflies]

Since the letters are identical, there are only 7 ways to fill a box with 3 letters. Does that make sense?

Sorry, maybe I got it wrong. All three letters in a box and this can be done in 7 ways, that does make sense

 

[fireflies]

Post #5 gives you the 3 variations that you have to consider.
Post #9 gives you the answer to one of those variations.

Now I can actually get what you're trying to say :)

But I already did that in post#4 right?

 

[RUber]

What would be the case then if the post-boxes were identical?

If the boxes were identical and the letters were identical you would only have:
6 boxes with 1, 1 box with 4
5 boxes with 1, 1 box with 2, 1 box with 3
4 boxes with 1, 3 boxes with 2.
That is: 3 ways to split 10 letters into 7 boxes with at least one in each box.

This is almost certainly not what the original question was looking for.

 

[fireflies]

Since now it is more clear to me, let me try to answer post#11 by myself. Here post-boxes are identical. So, we can only do is
3 in a box in 3C3
2 in a box and rest in other in 3C2
1 in each box in 3C1,

Then add all. Am I correct?

 

[fireflies]

If the boxes were identical and the letters were identical you would only have:
6 boxes with 1, 1 box with 4
5 boxes with 1, 1 box with 2, 1 box with 3
4 boxes with 1, 3 boxes with 2.
That is: 3 ways to split 10 letters into 7 boxes with at least one in each box.

This is almost certainly not what the original question was looking for.

I read the post later than I posted my answer. It makes me confused again. Why not we put the 7 in their case and try to combine the rest three here?

Yes, it is not an answer to the original post, but since I am having problems to work out the conditions so I think these answers are more likely to help me how to solve these actually

 

[Borg]

Sorry, maybe I got it wrong. All three letters in a box and this can be done in 7 ways, that does make sense

3 additional letters into 1 box

You have the answer to this one. So let's look at the next one up:

2 additional letters into 1 box and 1 letter into another

Just answer this question first: How many ways can you put 2 additional letters into 1 box?

 

[RUber]

Since now it is more clear to me, let me try to answer post#11 by myself. Here post-boxes are identical. So, we can only do is
3 in a box in 3C3
2 in a box and rest in other in 3C2
1 in each box in 3C1,

Then add all. Am I correct?

Are you still assuming letters are identical too?

3 in a box means 3 in one box 0 in others. If boxes are identical, there is only one way to do it.
2 in one box, 1 in another, and 0 in others. This is still one case, all similar layouts are considered indistinct.
1 in each of 3 boxes and 4 empty boxes. Also, just one case.

If the letters are not identical, then you need to start from 10 letters again. I reiterate, this is not what the question was asking and would likely become complicated quickly.
( I could be wrong on these since I don't often deal with these sorts of questions)
Case 1: 4 in one box, one in each of the other 6-- 10C4 ways to choose the 4 letters that go in.
Case 2: 3 in one box, two in another, 1 in rest--10C5 ways to choose the ones going into two boxes times 5C3 ways to choose which ones go into the first.
Case 3: 2 in three boxes, 1 in the rest -- 10C6 * 6C4 * 4C2 ways

Then sum the 3 cases.

 

[fireflies]

Are you still assuming letters are identical too?

3 in a box means 3 in one box 0 in others. If boxes are identical, there is only one way to do it.
2 in one box, 1 in another, and 0 in others. This is still one case, all similar layouts are considered indistinct.
1 in each of 3 boxes and 4 empty boxes. Also, just one case.

If the letters are not identical, then you need to start from 10 letters again. I reiterate, this is not what the question was asking and would likely become complicated quickly.
( I could be wrong on these since I don't often deal with these sorts of questions)
Case 1: 4 in one box, one in each of the other 6-- 10C4 ways to choose the 4 letters that go in.
Case 2: 3 in one box, two in another, 1 in rest--10C5 ways to choose the ones going into two boxes times 5C3 ways to choose which ones go into the first.
Case 3: 2 in three boxes, 1 in the rest -- 10C6 * 6C4 * 4C2 ways

Then sum the 3 cases.

Yes, I was assuming the letters also identical.
Now its more clear to me.

 

[fireflies]

You have the answer to this one. So let's look at the next one up:

Just answer this question first: How many ways can you put 2 additional letters into 1 box?

7C2. Then multiply with 6C1.

 

[RUber]

7C2. Then multiply with 6C1.

Nope.

7C2 means you are choosing 2 mailboxes.
You next would need to choose between the 2 to figure out which one gets 2 letters.

 

[RUber]

If you were answering the question, "how many ways can you put 2 additional letters into 1 box?" You should have the same answer as you did when you answered
"how many ways can you put 3 additional letters into 1 box?".

 

[fireflies]

Oh, yes.

7C1*6C1

 

[RUber]

Note that 7C1 * 6C1 = 7C2 *2C1. So either way you attack it, you get the same answer.
7C1*6C1 is what you get if you first choose the mailbox to get 2 letters and then choose the mailbox to get 1. $7*6$
7C2*2C1 is what you get if you first choose the two mailboxes, then decide which one gets the second letter. $\frac{7*6}{2}*2$

 

[haruspex]

Note that 7C1 * 6C1 = 7C2 *2C1. So either way you attack it, you get the same answer.
7C1*6C1 is what you get if you first choose the mailbox to get 2 letters and then choose the mailbox to get 1. $7*6$
7C2*2C1 is what you get if you first choose the two mailboxes, then decide which one gets the second letter. $\frac{7*6}{2}*2$

There's a more generic way to solve this than breaking it into cases.
Having reduced it to placing 3 letters in 7 boxes, instead of thinking about the boxes think about the 6 gaps between them. This gives you 9 "things" in a line, 6 gaps and three letters. Pick six of them to be the gaps and that will tell you where the letters go.

 

[fireflies]

That means 9C6, and similarly 9C3 also?

 

[haruspex]

That means 9C6, and similarly 9C3 also?

Yes.