# A Counting Question

Number Theory is one of the hardest disciplines I found in Mathematics. I am trying to learn it on my own but it is kind of cumbersome. For instance this problem is giving me a hard time. How many numbers between 1 and 999,999 contain exactly one of each of the digits: 1, 2 and 3?

First I need to understand the question. Does this mean I need to look for the numbers that contain 1 and 2 and 3 one time, or the numbers that will only contain 1 one time or 2 one time or 3 one time, or 1 and 2 one time, or...etc

-
Statistically, consider how many possibilities there might be for numbers having 1, 2 or 3 in their digits. There's a lot of them. Then consider reducing the count to only those numbers which have only one entry for the numbers 1, 2 or 3. How many of those might there be? Consider the statistics first, then the actual answer might occur to you. –  abiessu Aug 18 '13 at 2:49
It means that your number must contain a $1$, $2$, and a $3$, but cannot contain more than one of any of them. –  Andrew Salmon Aug 18 '13 at 2:49

We have a $6$-digit number, if it's less than $100,000$, then for the purposes of this problem, we'll write $000024$ for the number $24$, and so on.

We must have exactly one $1$, $2$, and $3$, in there, and they can be in any order. There are six place values to choose from, so there are $6$ ways of placing the $1$, $5$ ways of placing the $2$ that avoids the $1$, and $4$ ways of placing the $3$ that avoids both $1$ and $2$. This is $6 \cdot 5 \cdot 4 = 120$ ways total.

Now we have $7$ other digits ($0$ and $4$ through $9$) to choose from, and $3$ more decimal places to fill. We can choose any combination of these digits, so there are $7^3 = 343$ ways of doing this.

So in total, there are $343 \cdot 120 = 41160$ numbers total that meet the requirements.

-

You’re to look for the numbers that contain a single $1$ and a single $2$ and a single $3$, and three other digits that must not be $1$’s, $2$’s, or $3$’s.

You can think of all of these numbers as $6$-digit strings, padding them at the front with zeroes if necessary. The smallest ‘legal’ number is therefore $123$, which for this problem I prefer to think of as $000123$, and the largest is $321999$.

To count them, think of using the three digits that aren’t $1,2$, or $3$ to form a skeleton, $_x_y_z_$, where $x,y$, and $z$ represent those three digits, and the underlines show the four slots into which we can put the $1,2$, and $3$. Each of $x,y$, and $z$ can be any of the $7$ digits $0,4,5,6,7,8$, or $9$, so there are $7^3$ ways to form the skeleton $xyz$. To count the ways of putting $3$ objects into the $4$ slots in the skeleton, use the stars-and-bars method, which is reasonably well explained at the link. The formula that you’ll find there tells you that there are $$\binom{3+4-1}{4-1}=\binom63$$ ways to distribute $3$ identical objects amongst the $4$ possible slots. Our objects are not identical, however: we have a $1$, a $2$, and a $3$. Once we’ve chosen slots for $3$ objects, we can put the $1,2$, and $3$ into those slots in $3!$ different ways, one for each permutation of of $1,2$, and $3$.

You now have all of the pieces; can you combine them to get the final answer? I’ve left it spoiler-protected below; mouse-over to see it.

You need to multiply the numbers of ways to make the various independent choices, so you get $7^3\cdot\binom63\cdot 3!=343\cdot\frac{6!}{3!3!}\cdot3!=343\cdot\frac{6!}{3!}=343\cdot120=41160$.

By the way, you don’t actually need the stars-and-bars calculation for this small problem, since it’s easy enough to work out by hand the number of ways of placing the $1,2$, and $3$. However, it’s a very useful tool, so it’s not a bad idea to become familiar with it earlier rather than later.

-
@Andrew: Thanks; for some reason I forgot that I’d cancelled the second $3!$ in the denominator. –  Brian M. Scott Aug 18 '13 at 3:06

Hint: First figure out where the 1, 2, and 3 go. Then determine what the other numbers can be.

-
Hint: It is convenient to think of our numbers as $000000$ to $999999$.
We must choose where the $1$ will go, then choose where the $2$ will go, then choose where the $3$ will go.
Then we can fill the remaining $3$ places arbitrarily with any of the remaining $7$ digits.