• Support PF! Buy your school textbooks, materials and every day products Here!

Fundamental counting principle

  • Thread starter paulmdrdo
  • Start date
  • #1
66
2

Homework Statement


How many 3 digit numbers can be formed from 0 to 3 without repition



Homework Equations




The Attempt at a Solution



What I did first is

H = number of choices for the hundreds place
T = number of choices for the tens place
U = number of choices for the units digit

H = 3 possible choices (excluding zero)
T = 3 possible choices ( including zero but excluding whatever is in the hundreds place)
U = 2 possibe choises (including zero but excluding whatever are in the hundreds place tens place)

Therefore 3x3x2 = 18 numbers can be formed

But I noticed something. When do the selection in reverese that is selecting the choices for units digit first then the tens place then hundreds place I get a different answer

U = number of choices for the units digit
T = number of choices for the tens place
H = number of choices for the hundreds place

U = 4
T= 3
H = 1

Therefore 4x3x1 = 12 numbers

Can you guys explain why this happens? Thanks!
 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,249
968

Homework Statement


How many 3 digit numbers can be formed from 0 to 3 without repition



Homework Equations




The Attempt at a Solution



What I did first is

H = number of choices for the hundreds place
T = number of choices for the tens place
U = number of choices for the units digit

H = 3 possible choices (excluding zero)
T = 3 possible choices ( including zero but excluding whatever is in the hundreds place)
U = 2 possibe choises (including zero but excluding whatever are in the hundreds place tens place)

Therefore 3x3x2 = 18 numbers can be formed

But I noticed something. When do the selection in reverese that is selecting the choices for units digit first then the tens place then hundreds place I get a different answer

U = number of choices for the units digit
T = number of choices for the tens place
H = number of choices for the hundreds place

U = 4
T= 3
H = 1

Therefore 4x3x1 = 12 numbers

Can you guys explain why this happens? Thanks!
It's more difficult to do it if you don't do the hundred's place first.

What to use for H depends upon whether or not a zero has been chosen for the unit's place or ten's place. You could find the total number of 3 digit numbers if you allow a zero in the hundred's place. Then subtract the number of three digit numbers in that list which have a zero in the offending position.
 
  • #3
If you use 0 for U or T you do have
U = 4
T = 3
H = 1
4x3x1 = 12 possibilities

But, you also may not use 0 at all. Then
U = 3
T = 2
H = 1
3x2x1 = 6 possibilities

The total is 12+6 = 18 possibilities
 
  • #4
66
2
It's more difficult to do it if you don't do the hundred's place first.

What to use for H depends upon whether or not a zero has been chosen for the unit's place or ten's place. You could find the total number of 3 digit numbers if you allow a zero in the hundred's place. Then subtract the number of three digit numbers in that list which have a zero in the offending position.
If you use 0 for U or T you do have
U = 4
T = 3
H = 1
4x3x1 = 12 possibilities

But, you also may not use 0 at all. Then
U = 3
T = 2
H = 1
3x2x1 = 6 possibilities

The total is 12+6 = 18 possibilities
Hello thank you for this reply.

What if we are aksed
How many 3 digit even numbers can be formed from 0, 1, 2, 3, 4, 5 and 6 with no repetition?
My attempt:
For U=0, T=6 choices, H = 5 choices
30 numbers ending with zero not including two digit numbers starting with zero
For U=2, T=6 choices, H = 4choices
24 Numbers ending with two not including two digit numbers starting with zero
For U=4, T=6 choices, H = 4 choices
24 numbers ending with four not including two digit numbers starting with zero
For U=6, T=6 choices, H = 4 choices
24 numbers ending with 6 not including two digit numbers starting with zero
∴ 30+72=102 three-digit even numbers.

The correct answer is 105 if we do the selection in reverse that is Tens place first the the hundreds

How do we reconcile this to what you posted above? Thanks.
 
  • #5
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,249
968
A couple comments are in order here.

I really liked Irene Kaminkowa's method. And by the way: Welcome to PF, Irene.

To avoid confusion we should make a distinction as to whether we are referring to a particular digit being used in some position, or the referring to the number of choices for that position. Thus I suggest using Upper Case for the latter as has been in the OP, and using lower case to refer to the value being considered for a particular position. E.g.: If u = 0, then there are 6 choices for t, and thus T = 6.
 
  • #6
Let's generalize:
Given digits 0 to n, how many 3-digit numbers can we get without digit repetitions?

From the search above we see that it's better to start from H. Anyway, the answer is the same. So
H = n
T = n
U = n-1
The number of possibilities
NP(n) = n2 (n-1) - general formula

Test for n = 3
NP(3) = 9*2 = 18 - works!

For n = 6
NP(6) = 36*5 = 210 - all numbers, both even and odd
So
NP(6) / 2 = 105 - even 3-digit numbers containing digits from 0 to 6
 
Last edited:
  • #7
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,249
968
Let's generalize:
Given digits 0 to n, how many 3-digit numbers can we get without digit repetitions?

From the search above we see that it's better to start from H. Anyway, the answer is the same. So
H = n
T = n
U = n-1
The number of possibilities
NP(n) = n2 (n-1) - general formula

Test for n = 3
NP(3) = 9*2 = 18 - works!

For n = 6
NP(6) = 36*5 = 210 - all numbers, both even and odd
So
NP(6) / 2 = 105 - even 3-digit numbers containing digits from 0 to 6
(6)(6)(5) = 180, not 210 .

Beyond that, why can we simply divide by 2 to get the number of even numbers. There are 7 possible digits here, 4 of which are even.
 
  • #8
Thank you, SammyS
Let me correct my calculations.

So, we have
NP(6) = 36*5 = 180 numbers
These numbers end with {0,1,2,3,4,5,6}

Let's find, how many of them end with 1
H = 5 {2,3,4,5,6}
T = 5 {0 and the rest of {0,2,3,4,5,6} without digit taken for H}
U = 1 {1}
So, 5*5 = 25 numbers end with 1
25*3 = 75 numbers end with {1,3,5}

Among our NP(6) there are
180 - 75 = 105 even numbers
 
  • #9
To generalize again
In the general case there are (n-1)2 numbers that end with the chosen digit from {1...n} and n(n-1) numbers that end with 0.
The total sum
(n-1)2n + n(n-1) = n2(n-1)
that confirms the formula above.
 
  • #10
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
If you use 0 for U or T you do have
U = 4
T = 3
H = 1
4x3x1 = 12 possibilities

But, you also may not use 0 at all. Then
U = 3
T = 2
H = 1
3x2x1 = 6 possibilities

The total is 12+6 = 18 possibilities
It seems like you are doing some double counting. Some of the possibilities when you are allowed to use 0 do not actually use 0, so it does not look right to just add the 12 and the 6 possibilities.

Better, I think, is to enumerate (1) all the possibilities that do not use 0 anywhere; and (2) the possibilities that specifically do use 0 in one of the two allowed places.
 
  • #11
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,249
968
I did a little editing of the following to reflect and earlier suggestion I made regarding notation. Consider three digit numbers of the form "h t u" where h is the hundred's digit, t is the ten's digit, and u is the unit's digit . And as previously H is the number of possible choices for the hundred's digit, similarly for T and U .
Hello thank you for this reply.

What if we are asked
How many 3 digit even numbers can be formed from 0, 1, 2, 3, 4, 5 and 6 with no digit repetitions?

My attempt:
For u=0, T=6 choices, H = 5 choices
30 numbers ending with zero not including two digit numbers starting with zero
For u=2, T=6 choices, H = 4choices
24 Numbers ending with two not including two digit numbers starting with zero
For u=4, T=6 choices, H = 4 choices
24 numbers ending with four not including two digit numbers starting with zero
For u=6, T=6 choices, H = 4 choices
24 numbers ending with 6 not including two digit numbers starting with zero
∴ 30+72=102 three-digit even numbers.

The correct answer is 105 if we do the selection in reverse that is Tens place first the the hundreds

How do we reconcile this to what you posted above? Thanks.
You have the same difficulty that you ran into in the OP.

If you proceed from the right (What you do here with the unit's digit is fine.), Then for u = 2, 4, or 6, yes, T = 6, but you can't say that H = 4. For those cases (three of them altogether) in which t = 0, you have H = 5 .

You can do the following for each of u = 2, 4, or 6: First choose h. There are 5 choices (can't have zero), i.e. H = 5. Then for t (now we can have t = 0), we also get T = 5.. Each gives 25 possibilities.

Yes, we have 30 + 3×25 = 105.

@ Ray ,
Dr. Kaminkowa has accounted for all relevant possibilities and no more.
 
  • #12
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
I did a little editing of the following to reflect and earlier suggestion I made regarding notation. Consider three digit numbers of the form "h t u" where h is the hundred's digit, t is the ten's digit, and u is the unit's digit . And as previously H is the number of possible choices for the hundred's digit, similarly for T and U .


You have the same difficulty that you ran into in the OP.

If you proceed from the right (What you do here with the unit's digit is fine.), Then for u = 2, 4, or 6, yes, T = 6, but you can't say that H = 4. For those cases (three of them altogether) in which t = 0, you have H = 5 .

You can do the following for each of u = 2, 4, or 6: First choose h. There are 5 choices (can't have zero), i.e. H = 5. Then for t (now we can have t = 0), we also get T = 5.. Each gives 25 possibilities.

Yes, we have 30 + 3×25 = 105.

@ Ray ,
Dr. Kaminkowa has accounted for all relevant possibilities and no more.
I was responding to post #3; basically, the final answer was OK but the arguments to get there seemed suspect to me, or at least, were incomplete.
 
  • #13
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,249
968
I was responding to post #3; basically, the final answer was OK but the arguments to get there seemed suspect to me, or at least, were incomplete.
Oh, yes. I do see a problem with that counting scheme.

However, the total number of possibilities is correct.
 
Last edited:
  • #14
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
Oh, yes. I do see a problem with that counting scheme.

However, the total number of possibilities is correct.
Exactly: the difference is between writing 12 as 4x3 or as 3x2 + 3x2 and interpreting accordingly.
 

Related Threads on Fundamental counting principle

  • Last Post
Replies
1
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
398
  • Last Post
Replies
21
Views
3K
  • Last Post
Replies
1
Views
3K
Replies
4
Views
2K
  • Last Post
Replies
3
Views
706
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
8
Views
3K
Top