8 different items into 5 different boxes

Danijel

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:
Related Precalculus Mathematics Homework News on Phys.org

SammyS

Staff Emeritus
Homework Helper
Gold Member
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

Homework Helper
Gold Member
2018 Award
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

Homework Helper
Gold Member
2018 Award
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

Homework Helper
Gold Member

"8 different items into 5 different boxes"

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