# How many odd numbers with distinct digits between 1000 and 9999

How many numbers with distinct digits are there between 1000 and 9999. [1]

I came up with a solution like this.

Since we can't know what numbers have been used, in the tens, hundreds and thousands we start counting at the ones.

1s:     { 1, 3, 5, 7, 9 }, so 5 initial possibilities
10s:    { 0, 1, ... , 9 }, so 10 initial possibilities, 1 taken: 9 left
100s:   { 0, 1, ... , 9 }, so 10 initial possibilities, 2 taken: 8 left
1000s:  { 1, 2, ... , 9 }, so 9 initial possibilites, 3 taken: 6 left


So then we arrive at the following: 5 * 9 * 8 * 6 = 2160 possibilities. I thought this was pretty straight forward.

Than I had a glimpse at the solution sheet... And lo an answer which really doesn't make much sense at its first glimpse.

Calculate the sum of those odd numbers with distinct digits with no 0’s, a 0 in the tens place, or a 0 in the hundreds place. No 0’s: 5 choices for the ones place, then 8 · 7 · 6 choices for the other three places; 0 in the tens place: 5 choices for the ones place and 1 choice for the tens place, then 8 · 7 choices for the other two places; 0 in the hundreds place: 5 choices for the ones place and 1 choice for the hundreds place, then 8 · 7 choices for the other two places;

(5 · 8 · 7 · 6) + (5 · 1 · 8 · 7) + (5 · 1 · 8 · 7) = 2240;

Why are the 0's treated special? The exercise states it should be an odd number, with distinct digits. I thought I adhered to that proposition....

[1] Exercise 2.7.15 from Applied Combinatorics 2nd edition by Fred S. Roberts and Barry Tesman

-
That 6 left implies that the 0 is not taken as if it is then there are 7 possible values for the first digit which you are missing. – JB King Feb 12 '13 at 18:03

Your problem comes when you assume that there were $3$ taken from your last set. It's quite possible that the second or third choice was a $0$, so that you in fact have only eliminated $2$ options from the last set.

Instead, choose the last digit first ($5$ choices), then the first digit ($8$ choices, since we can't have picked $0$ for the last digit), then deal with the second and third digit ($8$ and $7$ choices, in some order). That will get you $5\cdot 8\cdot 8\cdot 7=2240$, as desired.

-
Of course! Very clear now. Just like I had treated the odd numbers at first! Thank you! – DiligoDiligentia Feb 12 '13 at 18:08

If a $0$ is taken for one of the "middle" digits, that gives a different number of possibilities for the $1000$'s digit than if $0$ is not used as a middle digit.

One could deal with that by dividing into cases, but the following is more efficient:

There are $5$ choices for the last digit. For each of these choices there are $8$ choices for the lead digit. Then for the middle digits we have $8\cdot 7$ choices.

-

Consider picking 4 digits out of a bucket of 10 $\begin{pmatrix} 0, 1, 2,3, ...\end{pmatrix}$ and arranging them.

There are $${10 P_4 = 5040}$$ ways to pick these digits & arrange them $(210\times 24)$ to be exact because there are 24 permutations per selection.

Of these, you reject $${9 P_3 = 504}$$ of these digits because you do not want $0$ as the first digit...so consider picking 3 digits out of a bucket of 9 and arranging them.

All you need to do is simple subtraction to get $5040 - 504 = 4536$

-
Okay, this is just a small hint because it is only for all numbers...you need to pick a subset for only odd numbers...but the idea is about the same. – bryansis2010 Feb 12 '13 at 18:06