Thread: permutation/combination problem

I'm really stuck on this problem.

It says,how many numbers between 1 and 999,999 contains each of the digit 1,2 and 3 at least once.(Hint : for each i = 1,2,3 A_i be the set of all integers from 1 to 999,999 that do not contain the digit i)

I really need help with this one.

We have six digit-number* and we need to place in it digits 1, 2 and 3 in free order. We can do it in 6*5*4 ways, the remaining 3 places may include any digit, so it gives us 6*5*4*10*10*10 different numbers.

We want to calculate .
The minus 1 accounts for the 000000.

Now .

.

Can you put it all together?

Thanks for your help Plato.I only understand parts of it.Like,

A(1) = the number of integers that contain a 1 as one of it's digit.

A(2) = the number of integers that contain a as one of it's digit.
and so is A(3).

now A(1) = _ _ _ _ _ _

and each of these blanks cna be filled with a any of the digits between 0 to 9
i.e we have 10 choices

so if it's 0 0 0 0 0 1
0 1 9 9 4 5

and so on
so,A(1) has to have a digit 1 in it.

_ _ _ _ _ _ = 1 * 10 * 10 * 10 * 10 * 10



isn't it? how do u say it's 10 ^6 -1 then?

I was using the hint given in the problem.
is the number of numbers from 1 to 999999 that have no 1’s.
That is : you can use any of the other nine digits, subtract 1 to account for 000000.
is the number of numbers from 1 to 999999 that have no 1’s nor 2’s.
That is so forth.
The total number of numbers from 1 to 999999 is .

Now use inclusion/exclusion to get what you want.

Try shorter way: number xxxxxx has to include each of 1, 2 and 3 digits, they can be placed in different ways:
xxx321
xx3x21
x3xx21
3xxx21
xxx231
xx32x1
x3x2x1
3xx2x1
xx2x31
xx23x1
...
1x32xx
13x2xx
1x2xx3
1x2x3x
1x23xx
132xxx
12xxx3
12xx3x
12x3xx
123xxx
Each x may be replaced by any other digit, so each of 120 different cases represent 10 different numbers, that's why we get

Originally Posted by Arch_Stanton

Try shorter way: number xxxxxx has to include each of 1, 2 and 3 digits, they can be placed in different ways:
Each x may be replaced by any other digit, so each of 120 different cases represent 10 different numbers, that's why we get

That happens to be a great overcount.
The correct answer is 74,460.
In the reply above, the overcount comes by allowing any other digit to be used in each case.

You're right, some numbers appear more than once.