Number of $ 6 $ Digit Numbers with Alphabet $ \left\{ 1, 2, 3, 4 \right\} $ with Each Digit of the Alphabet Appearing at Least Once

Question

Find the number of 6 digit numbers that can be made with the digits 1,2,3,4 if all the digits are to appear in the number at least once.

This is what I did -

I fixed four of the digits to be 1,2,3,4 . Now remaining 2 places can be filled with 4 digits each. Number of 6 digit numbers if two places are filled with same digit are 4 * 6!/3! and if filled by different digits are 12 * 6!/(2!*2!). Therefore, total such numbers are 2880.

But the correct answer is 1560.

Any hint would be appreciated.

Answer 1

Instead of dividing into cases, we use the Principle of Inclusion/Exclusion.

There are $4^6$ strings of length $6$ over our $4$-letter alphabet. Now we count the bad strings, in which one or more digits are missing.

There are $3^6$ strings with the digit $1$ mising, and also $3^6$ with $2$ missing, with $3$ missing, with $4$ missing.

So our first estimate for the number of bad strings is $4\cdot 3^6$.

However, when we added, we multiply counted the bad strings that have more than one missing digit. For example, there are $2^6$ strings with $1$ and $2$ missing, and the same for all $6$ ways to choose $2$ digits from $4$.

So our next estimate for the number of bad strings is $4\cdot 3^6-6\cdot 2^6$.

However, we have subtracted too much, for we have subtracted one too many times the $4$ strings with $3$ digits missing. So the number of bads is $4\cdot 3^6-6\cdot 2^6+4$.

More neatly, we can write the number of good strings as $$\binom{4}{0}4^6-\binom{4}{1}3^6+\binom{4}{2}2^6-\binom{4}{3}1^6.$$

The method readily generalizes.

Answer 2

A good way (not necessarily the best way) of doing such a problem as advised by my high school teacher is to first determine the number of combinations, then follow by permuting their arrangements. For your question, there are two cases, one of the four digits repeating three times, and two of the digits repeating twice each.

For the first case, the number of ways to choose a digit repeating three times is $4C1$. The possible arrangements for this case is $\frac{6!}{3!}$. Then the number of six-digit numerals associated to this case will be the product of these two numbers.

For the second case, repeating the previous argument, we have the number of combinations as $4C2$ and the number of arrangements as $\frac{6!}{2!2!}$ Again, the product of these two numbers will be the number of six-digit numerals associated to this case.

Adding the two cases together, you will obtain the answer.

Answer 3

Really easy using generating functions. The generating function is:

$$G(x)=\left(x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}\right)^4$$

We need the coefficient of x^6 in that and we make use of the fact that $x^4 = x^2 \cdot x^2$

$\left(x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}\right) \left(x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}\right)=x^2+x^3+\frac{7 x^4}{12}...$

We only need to calculate the first 3 terms of that because other terms do not contribute to $x^6$

$\left(x^2+x^3+\frac{7 x^4}{12}\right) \left(x^2+x^3+\frac{7 x^4}{12}\right)=\frac{7 x^6}{12}+x^6+\frac{7 x^6}{12}=\frac{13 x^6}{6}$

Now we have the required coefficient, we just multiply by $6!$

$$6! \cdot \frac{13}{6}= 1560 $$

That is the answer.