Given $7$ blank spaces and four letters $A,B,C,D$, what is the number of ways each space can be filled up so that all four letters are used up.

Question

Given $7$ blank spaces and four letters $A,B,C,D$, what is the number of ways each space can be filled up so that all four letters are used up.

The only way I can think of is: Fill up all the squares in any way possible, then remove the arrangements that use less than $4$ letters. This can be done in $4^7 - 4 \times3^7$.

Is this correct? Is there a way we can use PIE (Principle of Inclusion-Exclusion) to solve this?

Answer 1

Your solution overcounts the number of arrangements that use less than $4$ letters. As you guessed, one way to correct this is to use the Principle of Inclusion and Exclusion.

If we ignore the requirement that each letter be used at least once, there are $N=4^7$ possible arrangements.

Let's say an arrangement has "Property $i$" if it omits letter number $i$, for $i=1,2,3,4$, corresponding to $A,B,C,D$, and define $S_j$ as the number of arrangements with $j$ of the properties, for $j=1,2,3,4$. Then $$S_j = \binom{4}{j}(4-j)^7$$ By PIE, the number of arrangements with none of the properties, i.e. the number of arrangements in which each letter is used at least once, is $$N-S_1+S_2-S_3+S_4 = \boxed{8400}$$

(To see how your original solution overcounts, note that it corresponds to $N-S_1$, omitting the other terms of the PIE computation.)

Answer 2

This question is very good place to use exponential generating functions .

It is said that all letter will be used ,so

the generating function for $A$ is $$x + \frac{x^2}{2} +\frac{x^3}{6} + \frac{x^4}{24}$$

the generating function for $B$ is $$x + \frac{x^2}{2} +\frac{x^3}{6} + \frac{x^4}{24}$$

the generating function for $C$ is $$x + \frac{x^2}{2} +\frac{x^3}{6} + \frac{x^4}{24}$$

the generating function for $D$ is $$x + \frac{x^2}{2} +\frac{x^3}{6} + \frac{x^4}{24}$$

We wrote our exponential generating functions starting from $x$ because each letter must be used and if each letter will be used then a letter can be used at most $4$ times.

Now, we should find their product . Moreover , when we find their expansion , we should look for the term $[x^{7}]$ and multiply it by $7!$.

Such that https://www.wolframalpha.com/input/?i=expanded+form+of+%28x+%2B+x%5E2+%2F+2+%2B+x%5E3+%2F+6++%2B+x%5E4+%2F+24%29%5E4

We found that the coefficient of $[x^7]$ is $\frac{5}{3}$ ,so $7! \times \frac{5}{3}=8400$