Question

How many ways are there to distribute five balls into seven boxes if each box must have at least one ball in it if

a) Both the balls and boxes are labelled?

b) The balls are labelled, but the boxes are unlabelled?

c) The balls are unlabelled, but the boxes are labelled?

d) Both the balls and boxes are unlabelled?

Short answer

a) Both the balls and boxes are labelled in 2520 ways.

(b) The balls are labelled, but the boxes are unlabelled in 1 way.

(c) The balls are unlabelled, but the boxes are labelled in 21 ways.

(d) Both the balls and boxes are unlabelled in 1 way.

Step-by-step solution

Concept Introduction

Counting is the act of determining the quantity or total number of objects in a set or a group in mathematics. To put it another way, to count is to say numbers in sequence while giving a value to an item in a group on a one-to-one basis. Objects are counted using counting numbers.

How many ways are there to distribute five balls into seven boxes 

Permutation (order is important) is defined as:

No repetition allowed:\({\rm{P(n,r) = }}\frac{{{\rm{n!}}}}{{{\rm{(n - r)!}}}}\)

Repetition allowed:\({{\rm{n}}^{\rm{r}}}\)

The following is a definition of a combination (the order is irrelevant):

No repetition allowed:\({\rm{C(n,r) = }}\left( {\begin{array}{*{20}{c}}{\rm{n}}\\{\rm{r}}\end{array}} \right){\rm{ = }}\frac{{{\rm{n!}}}}{{{\rm{r!(n - r)!}}}}\)

Repetition allowed:\({\rm{C(n + r - 1,r) = }}\frac{{{\rm{(n + r - 1)!}}}}{{{\rm{r!(n - 1)!}}}}\)

with\({\rm{n! = n \times (n - 1) \times \ldots \times 2 \times 1}}\).

Stirling numbers of the second kind

\({\rm{S(n,j) = }}\frac{{\rm{1}}}{{{\rm{j!}}}}\sum\limits_{{\rm{i = 0}}}^{{\rm{j - 1}}} {{{{\rm{( - 1)}}}^{\rm{i}}}} \left( {\begin{array}{*{20}{l}}{\rm{j}}\\{\rm{i}}\end{array}} \right){{\rm{(j - i)}}^{\rm{n}}}\)

The number of ways to distribute\({\rm{n}}\)distinguishable objects into\({\rm{k}}\)indistinguishable boxes is then:

\(\sum\limits_{{\rm{j = 1}}}^{\rm{k}} {\rm{S}} {\rm{(n,j) = }}\sum\limits_{{\rm{j = 1}}}^{\rm{k}} {\frac{{\rm{1}}}{{{\rm{j!}}}}} \sum\limits_{{\rm{i = 0}}}^{{\rm{j - 1}}} {{{{\rm{( - 1)}}}^{\rm{i}}}} \left( {\begin{array}{*{20}{l}}{\rm{j}}\\{\rm{i}}\end{array}} \right){{\rm{(j - i)}}^{\rm{n}}}\)

SOLUTION

Labelled\( \Rightarrow \)Distinguishable

Unlabelled \( \Rightarrow \)Indistinguishable

Both the balls and boxes are labelled?

(a)

We wish to know how many different ways there are to distribute five distinct things (balls) into seven distinct boxes.

\(\begin{array}{l}{\rm{n = 7}}\\{\rm{r = 5}}\end{array}\)

Because the order of the balls is crucial (because they are labelled), we must employ a permutation.

It is not permitted to repeat the process (as a box cannot contain more than one ball).

\({\rm{P(7,5) = }}\frac{{{\rm{7!}}}}{{{\rm{(7 - 5)!}}}}{\rm{ = }}\frac{{{\rm{7!}}}}{{{\rm{2!}}}}{\rm{ = 7 \times 6 \times 5 \times 4 \times 3 = 2520}}\).

Hence, both the balls and boxes are labelled in 2520 ways.

Step 4: The balls are labelled, but the boxes are unlabelled?

(b)

We want to know how many different ways there are to distribute five distinct objects (balls) into seven indistinguishable boxes.

\(\begin{array}{l}{\rm{n = 7}}\\{\rm{r = 5}}\end{array}\)

Because all boxes must have at least one ball, there is only one method to distribute the five balls among the seven boxes: place one ball in each of the five boxes.

Therefore, the balls are labelled, but the boxes are unlabelled in 1 way.

The balls are unlabelled, but the boxes are labelled?

(c)

We want to know how many different methods there are to arrange five indistinguishable objects (balls) into seven distinct compartments.

\(\begin{array}{l}{\rm{n = 7}}\\{\rm{r = 5}}\end{array}\)

Because the sequence of the balls is irrelevant (due to the fact that they are unlabelled), we must employ a combination.

It is not permitted to repeat the process (as a box cannot contain more than one ball).

\({\rm{C(7,5) = }}\frac{{{\rm{7!}}}}{{{\rm{5!(7 - 5)!}}}}{\rm{ = }}\frac{{{\rm{7!}}}}{{{\rm{5!2!}}}}{\rm{ = 21}}\)

Thus, the balls are unlabelled, but the boxes are labelled in 21 ways

Both the balls and boxes are unlabelled?

(d)

We're trying to figure out how many different methods there are to distribute five indistinguishable objects (balls) into seven indistinguishable boxes.

\(\begin{array}{l}{\rm{n = 7}}\\{\rm{r = 5}}\end{array}\)

Because all boxes must have at least one ball, there is only one method to distribute the five balls among the seven boxes: place one ball in each of the five boxes.