Passwords for a certain computer system are strings of uppercase letters. A vali
ID: 2974976 • Letter: P
Question
Passwords for a certain computer system are strings of uppercase letters. A valid password must contain an even number of X's. Determine a recurrence relation for the number of valid passwords of length n. Note: 0 is an even number, so ABBC is a valid password. This counting problem is pretty tricky. Here's a good way to think about it: to make a good password of length n you can either (a) add any non-X to the end of a good password of length n - 1, or (b) add an X to the end of a bad password of length n - 1. For (b) you can use the Good = Total-Bad trick to count the number of bad passwords of length n - 1. Please present answer with clear explanation or will not get a good rating.Explanation / Answer
From quick working out from what I can tell is if the length is n then the possible number of allowed passwords is:
(n choose 2) + 1, which is (n!/[(n-2)! * 2!]) + 1, we add the one for all of them as there can be 0 X's for all.