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$
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$
  • $\begingroup$ I like this answer more than mine, it is much clearer. Thank you! $\endgroup$ – Student Nov 5 '18 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.