# $4$ digit integers such that none of the digits appear more than twice

How many $4$ digit integers can be chosen such that none of the digits appear more than twice?

$4$-digit integers with distinct digits= $9\times9\times8\times7 = 4536$

$4$-digit integers with two alike digits $(XXYY) = 9\times9\times2\times1\times \cfrac{4!}{2!\times2!} = 972$

Total = $5508$

Is the solution correct?

• Are you allowing leading zeros? ETA: It seems like you're not, but it's worth checking. – Brian Tung Aug 28 '16 at 5:01
• You're also not counting the number of numbers with one pair of digits. – Brian Tung Aug 28 '16 at 5:04
• 4-digit integers with distinct digits= 9∗9∗8∗7=45369∗9∗8∗7=4536 4-digit integers with alike two pair digits (XXYY) = 9∗9∗2∗1∗(4!/2! ∗2!)=9729∗9∗2∗1∗(4!/2!∗2!)=972 4-digit integers with two alike one pair digits (XXYZ) = 9∗9∗8∗1∗(4!/2!)= 3888 Total = 9396? – Mahmudul Hasan Aug 28 '16 at 5:11
• In my thought, I have counted leading zeros, can't find my mistake here? – Mahmudul Hasan Aug 28 '16 at 5:12
• In your two alike digits, you have insisted that the first two digits be distinct, then that the third match one of the previous two, then that the fourth match the third, so you are close to counting those with three matching digits. Your order count is off. You won't count 1123 at all. – Ross Millikan Aug 28 '16 at 5:24

Direct approach. There are three possibilities. The first is ABCD, where all four digits are distinct. There are $9 \times 9 \times 8 \times 7 = 4536$ of these.

The second is AABC/ABAC/ABCA/BAAC/BACA/BCAA. Each of these has $9$ choices for the first position, and then $9 \times 8$ choices for the other two distinct digits. There are thus $6 \times 9 \times 9 \times 8 = 3888$ of these.

Finally, we have AABB/ABAB/ABBA. Each of these has $9$ choices for A and $9$ choices for B, so there are $3 \times 9 \times 9 = 243$ of these.

The total is $4536+3888+243 = 8667$.

If we allow leading zeros, the totals are $5040+4320+270 = 9630$.

Alternative approach. Count up the number of numbers that don't qualify, and then subtract from $9000$ (the number of numbers from $1000$ through $9999$, inclusive).

There are just $9$ numbers that have four of a kind: $1111, 2222, \ldots, 9999$.

There are also $9$ numbers that have three of a kind with three $0$'s: $1000, 2000, \ldots, 9000$.

For numbers that have three of a kind with three of a digit other than $0$: There are $9$ choices. If the other digit is in the first position, it can be anything other than the chosen digit or $0$, so there are $8$ choices. Otherwise, there are $9$ choices, for a total of $8+9+9+9 = 35$ possibilities for the other digit and its placement. This therefore accounts for $9 \times 35 = 315$ further disallowed numbers.

The total number of disallowed numbers is $9+9+315 = 333$, so the number of qualifying numbers must be $8667$.

If we allow leading zeros, the total number of possibilities increases to $10000$, and the number of disallowed numbers is $10+10 \times 4 \times 9 = 370$, so the number of permitted numbers is $9630$.

Take the total amount of numbers: $9\cdot10\cdot10\cdot10=9000$.

Subtract the amount of numbers with a digit which occurs exactly $4$ times: $9$.

Subtract the amount of numbers with a digit which occurs exactly $3$ times:

• With $0$ occurrences of $0$, there are $9\cdot8\cdot4=288$ such numbers
• With $1$ occurrences of $0$, there are $9\cdot3=27$ such numbers
• With $3$ occurrences of $0$, there are $9$ such numbers

The answer is therefore $9000-9-288-27-9=8667$.