Is there an equation to calculate the number of instances of a series of characters exist in a given key space?

Question

If I'm using 16-18 character-length passwords with 94 different possible values-per-character (lower alphas, upper alphas, numbers, and special characters), is there an equation I can use to calculate how many times a series of the same value will be presented?

What I'm trying to find out is with granular password complexity programs, you can specify the max number of characters that can be seen adjacent to each other before they are discarded. What I want to know is, if a low value (e.g. 2) is used, how severly does this impact the key space for resistence against brute force attacks.

As in, in a 16 character password's keyspace of 94^16, if the number of same-values can't be 2 or more, how many possible passwords are removed from the available passwords an attacker has to use?

e.g. in the case of 2 same-value characters, the following passwords would be rejected:

1. 12345667890abcdefgWW - because of the 66 and WW
2. sadfl;jkxz089--qwer - because of the --
3. a;lksdjf%%;slkdaj;;zlc - because of the %% and ;;
4. 2134@!#$SAf;ljkasdf$$$$cQ - because of the $$$$

...is there an equation to perform this type of calculation?

Answer 1

For n-character passwords without two identical adjacent characters, @Stephen gives the solution: that's 94*93^n-1 passwords. Reasoning is simple: you are free to use any of the 94 characters for the first character, then for each subsequent character you may use any of the 94 except the one which you just used, so 93.

For n = 16, you may see that you keep about 85.2% of the complete space of 94¹⁶ possible 16-character passwords. You lose less than 15%, so the security reduction is not huge.

If you want to avoid sequences of three identical characters, then the computation is more complex, but the involved space reduction will necessarily be lower, because any password with three consecutive identical characters is also a password with two consecutive identical characters. Therefore you will always keep at least your 85.2% of the original space. Moreover, the number of passwords with three identical consecutive characters is no more than (n-2)*94^n-2 (this is a gross overestimate); for n = 16 this figure is about 0.16% of the total space, so ruling out passwords with three identical consecutive characters will leave you more than 99.84% of your original space.

For the formula above, I just "choose" the position for the first character in the three-character sequence, and I get to choose n-2 characters freely. This is an overestimate because I am counting twice the passwords with two sequences, thrice the passwords with three sequences, and so on. But an overestimate is sufficient to show that the space reduction effect is negligible.

Reduction of user patience, however, might not be so negligible. Remember that every single "password complexity" rule will be considered as a burden by the user, and antagonizing the user is the last thing you really want in practice.