Skip to main content

Chapter 24 Balls in Boxes Part 2

Exercises Practice Problems

1.

Last class, we filled in the following table:

\(n\) distinct boxes, \(k\) balls, boxes CAN be empty

balls identical balls distinct conditions?
no repetition \(\displaystyle{{ n \choose k}}\) \((n)_k\) \(k \leq n\)
with repetition \(\displaystyle{{n+k-1 \choose k}}\) \(n^k\) none

We consider another variation on this problem: now the boxes cannot be empty. Try to fill in the following table. You will be able to determine 3 out of 4 of the answers. We will talk about the last one as a group.

\(n\) distinct boxes, \(k\) balls, boxes CANNOT be empty

balls identical balls distinct conditions?
no repetition \(\phantom{\displaystyle{{a+b+c \choose d}}}\) \(\phantom{\displaystyle{{a+b+c \choose d}}}\) \(\phantom{\displaystyle{{a+b+c \choose d}}}\)
with repetition \(\phantom{\displaystyle{{a+b+c \choose d}}}\) \(\phantom{\displaystyle{{a+b+c \choose d}}}\) \(\phantom{\displaystyle{{a+b+c \choose d}}}\)

2.

In this problem, you will count sets of functions from \([r]\) to \([s]\text{.}\) You will map each one to a balls-in-boxes problem. Decide each of the following questions (and write down your answers):

  • Are the balls distinct?

  • Are the boxes distinct?

  • Can boxes be empty?

  • Is repetition allowed?

  • What is the constraint on \(r\) and \(s\text{?}\)

Then write down the formula for the size of the set of functions.

  1. \(\mathcal{A} = \{ \) all possible functions from \([r]\) to \([s] \}\text{.}\)

  2. \(\mathcal{B} = \{ \) all injective functions from \([r]\) to \([s] \}\text{.}\)

  3. \(\mathcal{C} = \{ \) all surjective functions from \([r]\) to \([s] \}\text{.}\)

  4. \(\mathcal{D} = \{ \) all bijective functions from \([r]\) to \([s] \}\text{.}\)