In how many ways $n$ balls can be given to $k$ children so that no child gets more than $3$ balls when balls are distinct/identical?

Question

In how many ways $n$ balls can be given to $k$ children so that no child gets more than $3$ balls when balls are

a) balls are distinct

b) balls are identical

I am trying to solve this problem using the inclusion-exclusion principle. I have seen a lot of similar questions to this, however, I cannot figure out the answer and get very confused when there are no numbers and it's only letters.

Here's my work so far:

a) use the stars-bars method

I thought about using the same method in this example, but I'm not sure how to divide the letters into cases.

b) use the inclusion-exclusion principle

We want to satisfy the equation:

$x_1 + x_2 + \dots + x_k = n$, where $ 0 \leq x_i \leq 3$

Then, we can start off by saying:

$(n+k-1 \choose k-1)$ (base case)- $n-3+k-1 \choose k-1$ (exclude cases with children more than 3 balls) + ?

I am not sure if my work is correct, and I am not sure what to add to the ? part. I know I'm supposed to add something because we over-substracted the amount of "wrong" (?) cases, but I don't really get that part.

Answer 1

Let us take case (b) (identical balls) first and solve a concrete example for $15$ balls, $4$ children, $0-5$ balls per child.

Then using sticks-and-stones with inclusion-exclusion,
we get $\dbinom{15+4-1}{4-1} - \dbinom41\dbinom{12}3 + \dbinom42\dbinom63 = 56$

and if we want to generalise the formula for $n$ balls, $k$ children, $0-m$ balls/child, $$\sum_{j=0}^J(-1)^j\binom{k}{j}\binom{n+k-1-j(m+1)}{k-1},\; J = {\left\lfloor\frac{n}{m+1}\right\rfloor}$$

Now to come to case (a) (distinct balls), for each allowable pattern (written systematically in descending order,say),eg $5-5-5-0,\; 5-5-4-1,\;5-5-3-2\;$ etc you need to take the product of two multinomial coefficients for $[Lay\; Down\; Pattern]\times[Permute\;Pattern]$

eg if we distributed the balls in the pattern $5-5-3-2$,

$$\binom{15}{5,5,3,2}\binom{4}{2,1,1}$$

which you can write more conveniently in the permutation version of the multinomial coefficient as $$\frac{15!}{5!5!3!2!}\frac{4!}{2!1!1!}$$

And you would need to sum up the results for all allowable patterns