1
$\begingroup$

This is an exercise from a book on combinatorics and I can't seem to wrap my head around it: How many numbers are there, made out of 5 distinct digits, which contain '4' and are even. The answer according to the book is 7686.

I distinguished some cases (not sure if I distinguished in a 'smart' way)

  • the last digit is 4. In that case, there are 8 possibilities for the first digit (not 0, not 4). The second digit has 8 possibilities (not the first, not 4), the third has 7, the fourth has 6. The total amount is $8\cdot 8\cdot 7\cdot 6 = 2688$.
  • the last digit isn't 4. Therefore, the last digit must be 0,2,6 or 8. We must pick 3 digits from the remaining 8 digits. This can be done in $8 \cdot 7 = 56$ ways. These 3 digits along with '4' have to be distributed over the first 4 places, giving a total of $56 \cdot 4 \cdot 4! = 5376$ ways. However, these include some invalid numbers: those starting with $0$. These have to be substracted. The first digit is fixed, the last digit can be $2,6,8$, so 3 possibilities. We have to pick 2 digits from the remaining 7 digits. This can be done in $7 \cdot 6/2 = 21$ ways. We then need to distribute these two digits and '4' over 3 spaces, so $3!$ possibilities, giving a total of $3 \cdot 21 \cdot 3! = 378$ invalid numbers.

The total therefore equals $2688 + 5376 - 378 = 7686$ ways.

This seems like a brute force solution. Anyone who can 'smoothen' this, for example by making a smarter choice of distinguished cases?

$\endgroup$

1 Answer 1

2
$\begingroup$

I would break the problem into three main cases instead of two. There are $5$ positions for the $4$: the first position, the middle three, or the last position.

  • If $4$ is in the first position, then the last position has $4$ possibilities to keep the number even ($0$, $2$, $6$, or $8$). In this case, you get the number of possibilities is: $$ 1\cdot 4\cdot 8\cdot 7\cdot 6=1344. $$ Here, the product order is "first, last, second, third fourth."

  • If $4$ is in the last position, then the count above works. In this case, you get the number of possibilities is: $$ 1\cdot 8\cdot 8\cdot 7\cdot 6=2688. $$ Here, the product order is "last, first, second, third, fourth."

  • If $4$ is in one of the middle positions, then the last position has $4$ possibilities. There are two possibilities here, either $0$ is the last position or it isn't.

    • If $0$ is in the last position, then the number of possibilities is: $$ 3\cdot 1\cdot 8\cdot 7\cdot 6=1008. $$ Here, the product order is "position of $4$, last, first, two remaining positions."

    • If $0$ is not in the last position, then the number of possibilities is: $$ 3\cdot 3\cdot 7\cdot 7\cdot 6=2646 $$ Here, the product order is "position of $4$, last, first, two remaining positions."

Adding all of these up gives $7686$, as desired.

$\endgroup$
1
  • $\begingroup$ I like this answer more than mine, it is much clearer. Thank you! $\endgroup$
    – Student
    Nov 5, 2018 at 17:47

You must log in to answer this question.

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