• Support PF! Buy your school textbooks, materials and every day products via PF Here!

8 different items into 5 different boxes

Problem Statement
How many ways are there to arrange 8 different items into 5 different boxes, each containing at least 1 item.
Relevant Equations
Number of injections, surjections, and inclusion-exclusion formulas
My teacher solved this using inclusion-exclusion formulas to count the number of surjections from a set of 8 elemets (containing items) to a set of 5 elements (containing boxes). However, I thought of a different solution. But I have a hunch it's wrong.
What I thought is to first make sure every box gets and item, so we are basically counting number of injections from a set of 5 elements(num. of boxes) to the set of 8 elements (number of items). Then we have to arrange the remaining 3 items into 5 boxes. Here we are counting the number of injections from a set of 3 elemets to the set of 5 elemets. In the end, we multiply these two results to obtain the final one.
Please, let me know what you think.

Edit: I have found a mistake in my reasoning. This only makes sure that every box gets at most 2 items. Which doesn't have to be true. One box can contain up to 4 items, respecting the problem setttings.
 
Last edited:

SammyS

Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,125
895
Problem Statement: How many ways are there to arrange 8 different items into 5 different boxes, each containing at least 1 item.
Relevant Equations: Number of injections, surjections, and inclusion-exclusion formulas

My teacher solved this using inclusion-exclusion formulas to count the number of surjections from a set of 8 elements (containing items) to a set of 5 elements (containing boxes). However, I thought of a different solution. But I have a hunch it's wrong.
What I thought is to first make sure every box gets and item, so we are basically counting number of injections from a set of 5 elements(num. of boxes) to the set of 8 elements (number of items). Then we have to arrange the remaining 3 items into 5 boxes. Here we are counting the number of injections from a set of 3 elements to the set of 5 elements. In the end, we multiply these two results to obtain the final one.
Please, let me know what you think.

Edit: I have found a mistake in my reasoning. This only makes sure that every box gets at most 2 items. Which doesn't have to be true. One box can contain up to 4 items, respecting the problem setttings.
Yes, you have found your mistake. That's good thinking !

Here's a idea.
For arranging the remaining 3 items into 5 boxes, would it work to simply find the number of functions from a set of 3 elements to a set of 5 elements? (I think you would have then account for some duplicate counting.)
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,388
3,412
Another approach is to count the possibilities for each pattern. There are only three:

4, 1, 1, 1, 1
3, 2, 1, 1, 1
2, 2, 2, 1, 1
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,388
3,412
Yet another approach is to generate the iterative sequence (which is actually on OEIS).

If we let ##X_n## be the number of ways of putting 8 different objects into ##n## non-empty boxes, then:

##X_1 = 1##
##X_2 = 2^8 - 2X_1##
##X_3 = 3^8 - 3X_2 - 3X_1##

Etc.
 

LCKurtz

Science Advisor
Homework Helper
Insights Author
Gold Member
9,468
715
@Danijel : So what did you get for your answer?
 

Want to reply to this thread?

"8 different items into 5 different boxes" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top