Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
2  
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
add comment

4 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
@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
add comment

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

share|improve this answer
add comment

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.

Remark: The techniques used here do not really belong to Number Theory; the proper subject name is Combinatorics.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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