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 :)