How many ways are there to distribute eight different toys among four children if the first child gets at least two toys?

Question

My work:

$e_1 + e_2 + e_3 + e_4 = 8$

let $e_1\geq2$

with no constraint on the other $e_i$'s

we want to find coefficient of $\cfrac{x^8}{8!}$

with this I've found the exponential generating function to be

$g(x) = (\cfrac{x^2}{2!} + \cfrac{x^3}{3!}+...)(1 +x+\cfrac{x^2}{2!}+...)^3 = (e^{x}-1-x)(e^x)^3 = e^{4x}-e^{3x}-xe^{3x}$

so first series would be $ \sum_{r=0}^{\infty} 4^r\cfrac{x^r}{r!}$ for $e^{4x}$

Second series would be -$ \sum_{r=0}^{\infty} 3^r\cfrac{x^r}{r!}$ for $-e^{3x}$

But I get stuck here

What would the third series be for $-xe^{3x}$?

I need to figure this third series out to figure out the coefficient

Any help would be appreciated here.

Also is my logic and methodology right for this question?

If it helps, I just need help with the $-x$ in front of $-xe^{3x}$

It's really throwing me off as I'm not sure how it would turn into a series.

Answer 1

To find the coefficient of $\frac{x^k}{k!}$ in $x e^{3x}$, I find it easier to find the coefficient of $x^k$ and then multiply by $k!$.

The coefficient of $x^k$ in $x e^{3x}$ is the coefficient of $x^{k-1}$ in $e^{3x}$, which is $\frac{3^{k-1}}{(k-1)!}$. So the coefficient of $\frac{x^k}{k!}$ is $k! \cdot \frac{3^{k-1}}{(k-1)!} = k 3^{k-1}$.

Therefore our final answer should be $4^k - 3^k - k 3^{k-1}$, where $k=8$ in your case. That's $4^8 - 3^8 - 8 \cdot 3^7 = 41\,479$, which I also checked by brute force:

Length@Select[Tuples[Range[4], 8], Count[#, 1] >= 2 &]

gives $41\,479$ in Mathematica.

Answer 2

kludginess says hello

I don't know enough about generating functions to specifically examine your work. However, I do know that there is a strong relationship between generating functions and stars and bars analysis. Stars and bars is discussed at https://brilliant.org/wiki/integer-equations-star-and-bars/.

I also know that stars and bars analysis, at least in its simplified form, is inappropriate here, specifically because the toys are deemed to be different.

The problem is actually ambiguous, depending on whether the second, third, and fourth child must each get at least one toy.

$\underline{\textbf{Interpretation 1: Some children may get no toys}}$

This is easy.

$$4^8 - \left(8 \times 3^7\right) - 3^8.$$

$\underline{\textbf{Interpretation 2: Each child gets at least 1 toy}}$

There may be an elegant approach here that I am unaware of. My kludgy approach is to identify all of the possible satisfying toy distribution patterns and then enumerate each pattern.

Patterns:

P-1 : 5 - 1 - 1 - 1 : # ways $= S_1$.

P-2 : 4 - 2 - 1 - 1 : # ways $= S_2$.

P-3 : 3 - 3 - 1 - 1 : # ways $= S_3$.

P-4 : 3 - 2 - 2 - 1 : # ways $= S_4$.

P-5 : 2 - 2 - 2 - 2 : # ways $= S_5$.

The final tally will be $S_1 + S_2 + S_3 + S_4 + S_5.$

P-1
1st child gets 5 toys, other 3 toys are permuted.
$$S_1 = \binom{8}{5} \times 3!.$$

P-2
Three ways of selecting which other child gets more than one toy.
Then, you examine the # of ways that 1st child gets 4 toys, and other child gets 2 toys.
Then, you multiply by 2, since the first child can switch roles with the other child here.

$$S_2 = 2 \times 3 \times \binom{8}{4} \times \binom{4}{2} \times 2!.$$

P-3
Analysis very similar to analysis of P-2.
However, since the first child and the odd man out child will each get 3 toys, you must not apply the factor of 2, which would correspond to their switching places.

$$S_3 = 3 \times \binom{8}{3} \times \binom{5}{3} \times 2!.$$

P-4
If the first child is to get three toys, with one of the children the odd man out, then the first tally is

$$ S_{4a} = 3 \times \binom{8}{3} \times 5 \times \binom{4}{2}.$$

If the first child is to get two toys, then there are 3! ways of deciding which of the other children get 3 toys, 2 toys, 1 toy.

With this decided:

$$ S_{4b} = 3! \times \binom{8}{2} \times \binom{6}{3} \times 3.$$

$$ S_4 = S_{4a} + S_{4b}.$$

P-5
The # of ways of first giving 2 toys to 1st child, then giving 2 toys to 2nd child, ...

$$ S_5 = \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2}.$$