A Question on distribution numbers

Question

This is a question from the book Combinatorics -a problem oriented approach which states:

Q.1 Find the no. of distributions of a set of distinct balls into a set of distinct boxes, if no boxes can be empty.

Q.2 Find the number of words of a given length from a given set of letters, if each letter must occur at least once in each word.

The answer to both is the sum of all of the distribution numbers in which

$m$ = number of balls = length of each word

$n$ = number of boxes = number of letters in the set

and the numbers $m_1$,. . . , $m_n$ run through all possible sequences of n positive integers adding up to m:
$\sum_{m_1,m_2,\ldots ,m_n \geq 1}$ $m\choose m_1,m_2\ldots ,m_n$

I still can't understand why is no. of boxes is equivalent to no. of letters in set.Please help...

Answer 1

@Markus-Scheuer already gave a fairly detailed explanation of one way to understand this problem, but I think I have some simpler and more general tips. This is a matter of understanding the mappings in each problem.

Different balls are distinct and can each go to exactly one box. Boxes are distinct and can have many balls. Balls in a given box are unordered and there must be at least one in each.

Different positions in a string are distinct and can each contain exactly one letter. Letters are distinct and can appear in many positions. Positions containing identical letters are unordered (they can be rearranged without affecting the word) and each letter must appear in at least one position.

From that it's obvious that boxes are letters and positions are strings. And in general, if you write down all of the properties of the mapping that you can think of, it will usually be obvious if and how the problems are equivalent. If the properties match up but you're still not convinced, brute force it for some small numbers and verify that the answers are the same.

Answer 2

Here's a rather detailed explanation how to find the bijection between balls/boxes and words/letters:

Note: If the answer for the general case is not quite clear it's often helpful to reduce the complexity of the problem. So let's have a look at a small example in order to gain some more insight. In fact we will see, that one small example is sufficient to derive the answer for the general case.

First we look at the balls and the boxes:

Step 1: Small example with balls and boxes

Since the balls are distinguishable, we label them with $1,2,3,\dots$. Since the boxes are also distinguishable we label them with, lets say $X_1,X_2,\dots$. Now according to the problem no box can be empty. So we will choose for our example at least as many balls as boxes.

We start with an:

Example consisting of three balls and two boxes

\begin{align*} \text{balls:}&\qquad\qquad1,2,3\\ \text{boxes:}&\qquad\qquad X_1,X_2 \end{align*}

We write down all possibilities to assign $3$ balls into $2$ boxes, so that no box is empty:

\begin{array}{lrcrc} \text{boxes:}&&X_1&&X_2\\ \hline &&1,2&&3\\ &&1,3&&2\\ &&2,3&&1\\ &&1&&2,3\tag{1}\\ &&2&&1,3\\ &&3&&1,2\\ \end{array}

We observe: There are $6$ possibilities to distribute three distinguishable balls into two distinguishable boxes, so that no box is empty.

Next we check the connection of balls/boxes with words/letters

Step 2: Bijection of balls/boxes with words/letters

Now we want to show that this situation corresponds to counting the number of different (distinguishable) letters in words of a certain length. Let's check the exact wording:

\begin{array}{lcccc} \text{Q.1}&\text{ Find the no.}&\text{ a set of distinct balls}&\text{into a set of distinct boxes,}\\ &\text{of distributions of}&&\text{if no boxes can be empty.}\\ \hline \\ \text{Q.2 }&\text{Find the}&\text{words of a given length}&\text{from a given set of letters,}\\ &\text{number of}&&\text{if each letter must occur }\\ &&&\text{at least once in each word}\\ \hline \\ &&\text{distinct balls}\longleftrightarrow\text{words/length ?!?}&\text{boxes}\longleftrightarrow\text{letters} \end{array}

It's obvious from the comparison of Q.1 with Q.2 that boxes and letters can easily be identified by taking two letters, say $A$ and $B$ and define following bijection: \begin{align*} X_1 \longleftrightarrow A\\ X_2 \longleftrightarrow B \end{align*} But it's not so clear how to map distinct balls and the length of words.

Let's consider our example:

• We need a bijective mapping between distinct balls and length of words.

Since we use three balls in our example, we look at words of length three.

• How could we associate the labels $1,2,3$ of the balls with words of length three?

We identify the number of the ball with the position in the word. This means: If $X_1$ contains the balls $1$ and $2$, than since we have the correspondence $X_1 \longleftrightarrow A$, that the corresponding word has the letter A at the positions $1$ and $2$. This is the crucial correspondence.

So, the bijection between boxes/balls and letters/words is

Example: \begin{align*} \text{balls:}&\qquad1,2,3&\longleftrightarrow&\qquad\text{word position:}&\qquad1,2,3\\ \text{boxes:}&\qquad X_1,X_2&\longleftrightarrow&\qquad\text{letters:}&\qquad A,B\\ \end{align*}

and the table corresponding to (1) is

\begin{array}{lrcrccccccc} \text{boxes:}&&X_1&&X_2&&\text{letters:}&&A,B\\ \hline &&1,2&&3&&&&AAB\\ &&1,3&&2&&&&ABA\\ &&2,3&&1&&&&BAA\\ &&1&&2,3&&&&ABB\\ &&2&&1,3&&&&BAB\\ &&3&&1,2&&&&BBA\\ \end{array}

Interpretation: We observe that there is according to our construction a bijection between the words and balls in boxes. E.g. the word ABA means, that

• the letter $A$ corresponds to box $X_1$

• the letter $B$ corresponds to box $X_2$

• since $A$ occurs twice in ABA, there are two balls in box $X_1$

• since $B$ occurs once in ABA, there is one ball in box $X_2$

• since $A$ is in position $1$ and $3$ in ABA, the balls in box $X_1$ are labelled with $1$ and $3$

• since $B$ is in position $2$ in ABA, the ball in box $X_2$ is labelled with $2$.

Based upon the analysis of this example it should be possible to formulate the answer for the general solution.