Are combinatorics the most elegant way to determining the search space of a password's character set?

Question

I know how to find the total number of possibilities of a password, given a character set, and a length (or range of lengths), but where I'm getting hung up is on restricting the password, as banks and other sites do.

To keep things simple, lets limit the characters to
26: A-Z,
26: a-z,
10: 0-9,
10:!@#$%^&*()

So, given we are working with an 8 character password,

ALL possible: (26 + 26 + 10 + 10)^8

But, with some constraints (where I don't know what the cleanest way to go about calculating this is)

• must have 2 uppercase
• must have 2 lowercase
• must have 1 number
• must have 1 symbol
• must not contain any character twice in a row

This leaves two characters to be whatever the person wants.

I know that I need to subtract the ways to get each of those constraints from the all possible result, but I don't know the best way to do that.

i.e.: there are 10 possible symbols, and I need to choose 1, but it could go anywhere in the string? 10 choose 1... times something? idk.

And how does this change if a couple of the constraints are 'at least' or 'at most'?

It's been quite a few years since I've studied combinatorics, so any guidance would be much appreciated.

Answer 1

Let $a_n$ be the number of sequences of length $n$, made from the characters you mentioned, that have no two adjacent characters. Obviously $a_1 = 26 + 26 + 10 + 10$; we can say that $a_n = (26 + 26 + 10 + 10 - 1)a_{n-1}$ because, if a sequence in $a_{n-1}$ ends in a given character, we can append any of the other characters to form a new sequence in $a_n$. This will generate all possible sequences of $a_n$.

Thus $a_n = (26 + 26 + 10 + 10)\cdot(26 + 26 + 10 + 10 - 1)^{n-1}$. We can calculate $a_8 = (26 + 26 + 10 + 10)\cdot(26 + 26 + 10 + 10 - 1)^7$. Out of these, how many sequences:

• have only 1 uppercase character?
• have only 1 lowercase character?
• have no digits?
• or have no special characters?

We can count them with the same method, by reducing our choices accordingly whenever a character is chosen. We must use the inclusion-exclusion principle to count them since two or three of these events can occur together (never all four). Then, we subtract this number from $a_8$.

This is the interpretation for 'at least 2 $x$ characters'. If it is 'exactly 2', the counting is much simpler by elementary methods; if it is 'at most 2', then we can still use the method above with a little modification.