Password Combinatorics

Question

Suppose you're given a task to find the number of configurations for a password with the following stipulations;

1) there must be at least 8 characters (and let's assume a limit of 16 characters)

2) there must be at least 1 upper case character and at least 1 lower case

3) there must be at least 1 digit

4) there must be at least 1 special character (e.g., ., -, _, !, @, *, %)

With 26 letters both lower case and upper case (a-z), 10 digits (0-9), and 33 special characters, it seems we have a total combination of $95^8$ (of course, this is too simple because we don't want to neglect or re-use any of the above stipulations).

In the end, how many configurations may exist in an orderless, ≥8-character password such as this? Can you demonstrate how this is solved using summation notation?

Answer 1

The number of passwords of length 8 to 16 with those restrictions is $36430117984090740313099435877280 \approx 10^{31.56}$.

(Assuming my code is right :)

nLower = 26
nUpper = 26
nDigits = 10
nSpecial = 33

nTypes = (nLower, nUpper, nDigits, nSpecial)
minOfType = (1, 1, 1, 1)

def count(length, minRequired, nAvailable) :
  if sum(minRequired) > length:
    return 0
  if length == 0 :
    return 1

  s = 0L
  for i,n in enumerate(nAvailable):
    m = list(minRequired)
    m[i] = max(m[i]-1, 0)
    s += n * count(length-1, tuple(m), nAvailable)
  return s

print sum([count(k, minOfType, nTypes) for k in range(8, 17)])

Answer 2

Using the principle of inclusion exclusion, you can write it as a sum of $15$ exponential terms, where the exponent ranges from $8$ to $16$. If you like, this can be written without a summation using the finite geometric series formula.

\begin{align}\sum_{n=8}^{16}\begin{cases}95^n\\ -(95-26)^n-(95-26)^n-(95-10)^n-(95-33)^n \\+(95-52)^n+2(95-36)^n+2(95-59)^n+(95-43)^n \\-26^n-26^n-10^n-33^n\end{cases} \end{align}