3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I picked up my mistake. I double - counted some cases in filling up with different digits. The correct answer is 1560. $\endgroup$
    – Suyash
    Commented Dec 25, 2014 at 12:46

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Could you generalize to the case of $ n $ digit number over $ k $ - Letter Alphabet (Where $ n \geq k $)? $\endgroup$
    – Royi
    Commented Mar 23, 2018 at 5:57
2
$\begingroup$

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.😃

$\endgroup$
1
  • $\begingroup$ What does the second part of the question actually state? $\endgroup$
    – Kaushik
    Commented Aug 8, 2019 at 13:35
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can you explain how did you get that generating function?? $\endgroup$
    – Suyash
    Commented Jan 2, 2015 at 11:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .