Question

How many ways are there to distribute six distinguishable objects into four indistinguishable boxes so that each of the boxes contains at least one object?

Short answer

There are 65 ways to distribute six distinguishable objects into four indistinguishable boxes so that each of the boxes contains at least one object.

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.

Explanation

Consider the second-kind enthralling numbers,

\({\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}}}\)

We want to know how many different methods there are to distribute six distinct things into four indistinguishable boxes.

\(\begin{array}{l}{\rm{n = 6}}\\{\rm{k = 4}}\end{array}\)

Because none of the boxes can be empty, the Stirling number of the second kind \({\rm{S(6,4)}}\)is used to calculate the number of ways to distribute six identifiable objects into four indistinguishable boxes (by definition of the Stirling number of the second kind in the textbook).

Let's look at the second type of Stirling numbers:

\(\begin{array}{c}{\rm{S(6,4) = }}\frac{{\rm{1}}}{{{\rm{4!}}}}\sum\limits_{{\rm{i = 0}}}^{\rm{3}} {{{{\rm{( - 1)}}}^{\rm{i}}}} \left( {\begin{array}{*{20}{l}}{\rm{4}}\\{\rm{i}}\end{array}} \right){{\rm{(4 - i)}}^{\rm{6}}}\\{\rm{ = }}\frac{{\rm{1}}}{{{\rm{24}}}}{\rm{ \times }}\left( {{{{\rm{( - 1)}}}^{\rm{0}}}\left( {\begin{array}{*{20}{l}}{\rm{4}}\\{\rm{0}}\end{array}} \right){{{\rm{(4 - 0)}}}^{\rm{6}}}{\rm{ + ( - 1}}{{\rm{)}}^{\rm{1}}}\left( {\begin{array}{*{20}{l}}{\rm{4}}\\{\rm{1}}\end{array}} \right){{{\rm{(4 - 1)}}}^{\rm{6}}}{\rm{ + ( - 1}}{{\rm{)}}^{\rm{2}}}\left( {\begin{array}{*{20}{l}}{\rm{4}}\\{\rm{2}}\end{array}} \right){{{\rm{(4 - 2)}}}^{\rm{6}}}{\rm{ + ( - 1}}{{\rm{)}}^{\rm{3}}}\left( {\begin{array}{*{20}{l}}{\rm{4}}\\{\rm{3}}\end{array}} \right){{{\rm{(4 - 3)}}}^{\rm{6}}}} \right)\\{\rm{ = }}\frac{{\rm{1}}}{{{\rm{24}}}}{\rm{ \times }}\left( {{{\rm{4}}^{\rm{6}}}{\rm{ + ( - 4) \times }}{{\rm{3}}^{\rm{6}}}{\rm{ + 6 \times }}{{\rm{2}}^{\rm{6}}}{\rm{ + ( - 4)}}} \right)\\{\rm{ = }}\frac{{\rm{1}}}{{{\rm{24}}}}{\rm{ \times (4096 - 2916 + 384 - 4)}}\\{\rm{ = }}\frac{{\rm{1}}}{{{\rm{24}}}}{\rm{ \times (1560)}}\\{\rm{ = 65}}\end{array}\)

Hence, there are 65 ways to distribute six distinguishable objects into four indistinguishable boxes so that each of the boxes contains at least one object.