How many ways can $r$ distinct objects be distributed into $4$ distinct containers if there must be at most $1$ object in the first container?

I think I have done this problem correctly. Can someone confirm please?

Okay so we have:

\begin{align}e_1 + e_2 + e_3 + e_4 &= r\\ e1 &\leqslant1\\ e2, e3, e4 &\geqslant 0 \end{align}

This gives generating function:

$$h(x) = (1 + x)\left(1 + x +\frac{x^2}{2!} + \frac{x^3}{3!} + \cdots \right)^3$$

Now let

\begin{align} f(x) &= (1 + x)\\ g(x) &= (e^x)^3 = e^3x \end{align}

then $$g(x) = 1 + 3x + \frac{3^2x^2}{2!} + \cdots + \frac{3^rx^r}{r!}$$

We are looking for the coefficient of $\frac{x^r}{r!}$.

Now $f(x)$ only has two non-zero coefficients, $A_0 = 1$ and $A_1 = 1$. $g(x)$ has coefficients $B_0, B_1, B_2, \ldots, B_r$.

Then we are looking for $A_0B_r + A_1B_{r-1}$,

i.e. $$1\cdot(3^r) + 1\cdot(3^{r-1})r$$ ways to distribute.


Let $a_r$ be the number of ways of doing this with $r$ objects. There are two cases - either there is an object in box one, or there is not. The first case is counted by $r3^{r-1}$ and the second case by $3^r$. Hence $$a_r = r3^{r-1} + 3^r,$$ which is the same as what you had. No generating functions necessary :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.