Number of password number-letter combinations given constraints

Question

A password is constructed from the numbers 1-9 and the uppercase letters A,B,C,D,E,F,G,H. How many passwords can be constructed which consist of four numbers and 3 letters, if

(a) repetition is allowed?

(b) repetition is not allowed?

(c) no two digits can be next to each other, and no repetition allowed?

Attempt

(a) Number of placements of the three letters $={ 7 \choose 3} = 35$, number of combinations of the letters $=8^3 = 512$, number of combinations of the numbers $=9^4 = 6561$, total combinations = $35\times 512 \times 6561 = 117573120$

(b) Number of placements of the three letters $={ 7 \choose 3} = 35$, number of combinations of the letters $={}^8\mathrm P_6 = 336$, number of combinations of the numbers $=9\times 8\times7\times 6 = 3024$, total combinations = $35\times 336 \times 3024 = 35562240$

Are my approaches for parts (a) and (b) correct? I am not sure how to approach part (c) - any suggestions would be greatly appreciated.

Answer 1

Yes, your approach is correct. For c), note that the only way to have four digits with no two adjacent is if the password looks like #@#@#@#, where # represents a digit and @ a letter.

If you instead had three digits, there would be more possibilities. The number of valid arrangements of 3 #s and 4 @s is the same as the number of arrangements of 3 #s and 2 @s with no restrictions. To get from a short sequence like ##@#@ to the corresponding long sequence add an @ between the first and second #, and another between the second and third, to get #@#@@#@. (This will ensure that there can't be two adjacent #s in the long sequence.)

There are $\binom 52$ short sequences, so there are the same number of valid long sequences. Doing this trick, if you have $\ell$ letters and $d$ digits in a long sequence you get $\ell-d+1$ letters and $d$ digits in a short sequence, so the number of patterns is always $\binom{\ell+1}d$. (If $\ell+1<d$ then there aren't enough letters to have no two digits adjacent.)

[edit] Actually you can get the same result rather more simply - there are $\ell+1$ spaces between the letters (including the space at the beginning and the space at the end), and you need to choose $d$ different spaces to put the digits in.

Answer 2

If repetition is allowed first place numbers in $7 \choose 4$ ways, then just place the letters in the left over places. Then you have $9^4 \cdot 8^3$ options for the letters.

For $(b)$ first place numbers in $7 \choose 4$ ways, then just place the letters in the left over places. Repetition is not allowed so we have $9 \cdot 8 \cdot 7 \cdot6$ options for the numbers, while for the letters we have $8 \cdot 7 \cdot 6$. Just multiply everything. So I guess you were correct about these two.

For $(c)$ since you have $7$ spaces to put the letters and numbers, fix the alternating spaces for numbers like $* x * x * x* $ where $*$ represent the numbers, and $x$ represent the letters. This is the only way for the numbers not to stick together. Repetition is not allowed so we have $9 \cdot 8 \cdot 7 \cdot6$ options for the numbers, while for the letters we have $8 \cdot 7 \cdot 6$. Altogether $9\cdot(8\cdot7\cdot6)^2$.