View source for 5. How many strings of 5 digits without repetitions contain 1 or 2 but not both? - Rhea

5. How many strings of 5 digits without repetitions contain 1 or 2 but not both?

The only way that I can currently think of to solve this problem is to use an algorithm (there is probably a much more efficient way of solving this problem).

Ultimately, we want to treat this problem like the problems we saw early in the semester, where we take:

(# Strings length 5 that contain 1) + (# strings length 5 that contain 2) - (# strings length 5 that contain 1 and 2)

So lets find each component:

'''# Strings length 5 that contain 1 ='''

1: choose 1 -----------------------------------------------------------------(1), 

2: choose a number that is not 1 --------------------------------------------(9), 

3: choose a number that is not 1 or the 2nd number --------------------------(8), 

4: choose a number that is not 1 or the 2nd number or the 3rd number --------(7), 

5: choose a number that is not 1 or the 2nd or 3rd or 4th number ------------(6).

= 1*9*8*7*6 = 3024

'''# Strings length 5 that contain 2 ='''

1: choose 2 -----------------------------------------------------------------(1), 

2: choose a number that is not 2 --------------------------------------------(9), 

3: choose a number that is not 2 or the 2nd number --------------------------(8), 

4: choose a number that is not 2 or the 2nd number or the 3rd number --------(7), 

5: choose a number that is not 2 or the 2nd or 3rd or 4th number ------------(6).

= 1*9*8*7*6 = 3024

'''# Strings length 5 that contain 1 and 2 ='''

1: Choose 1 -----------------------------------------------------------------(1),

2: Choose 2 -----------------------------------------------------------------(1),

3: Choose a number that is not 1 or 2 ---------------------------------------(8),

4: Choose a number that is not 1 or 2 or the 3rd number ---------------------(7),

5: Choose a number that is not 1 or 2 or the 3rd or 4th number --------------(6).

= 1*1*8*7*6 = 336

So the total number of strings that contain 1 or 2 but not both is:

3024+3024-336 = 6048-336 = 5712 --[[User:Msstaffo|Msstaffo]] 23:19, 9 March 2009 (UTC)

BUT (as I just realized), this is the case if order does not matter in the strings.  Since order DOES matter we need to multiply our answer by the number of ways to order 5 numbers in a string.  We know that this is 5! or 5*4*3*2*1.

'''So, the actual total number of strings that contain 1 or 2 but not both is:

5712*5! = 685440''' --[[User:Msstaffo|Msstaffo]] 23:19, 9 March 2009 (UTC)

In an abbreviated algorithm I'll show why we need to multiply by 5!:

'''# Strings length 5 that contain 1 (order is important)'''

''1: Choose 1 (1)

2: Place 1 (5)

3: Choose a non-1 number (9)

4: Place such number (4)

5: Choose a number not like the 1st or 2nd (8)

6: Place such number (3)

7: Choose a number not like the 1st, 2nd, or 3rd (7)

8: Place such number (2)

9: Choose a number not like the 1st, 2nd, 3rd, or 4th (6)

10: Place such number (1)''

As you can see it is in the placement that we pick up the 5*4*3*2*1 or 5!

This happens in each algorithm, so we can factor it out and multiply it back in at the end like I did in the above solution. --[[User:Msstaffo|Msstaffo]] 23:19, 9 March 2009 (UTC)

[[Midterm Practice Questions]]