Is the sum of permutations of disjointed sets larger than the count of permutations in their union?

My wife and I are having a bit of a disagreement.

Concerning eight-digit passwords like the kind most secure websites require, she believes you could generate more unique password combinations by using only one of the following sets: one lowercase or one uppercase or one symbol or one numeral. In other words, if you created a password using only lowercase letters with no other conventions. e.g.: jtpdlrkc or JTPDLRKC or 29456014 or #^@%#&(%.

I have asserted that, by using at least one each of the aforementioned sets, a person can generate FAR, FAR more unique password combinations, thereby making the password much more difficult for someone to hack. e.g. gy7HU*j9 or $F6ms38@.

She thinks I'm making this up. I need numbers to prove my point. Anyone interested in running with this one?

There are $26^8=208,827,064,576$ lower-case passwords, the same number of upper-case passwords, $10^8=100,000,000$ digit-only passwords and (if we assume there are about ten symbols) about $10^8$ symbol-only passwords as well. That gives your wife about $418,000,000,000$ possible passwords.

We get a simple lower bound for the number of passwords having all kinds of characters: We can use any character for the first five places, that's $(26+26+10+10)^5=1,934,917,632$. If no upper-case was used so far, add an upper-case. If no lower-case was used so far, add one lower case. If no digit was used so far, add one digit. If no special was used so far, add one special. (At most three of these conditions can be true). As long as we still have less than eight characters add one of the 72 allowed characters. This method will not generate all valid passwords, but there will be at least $10\cdot 10\cdot 26$ possible choices in the last three places. Multiply with the above to arrive at $5,030,785,843,200$, more than ten times the other count.

Here's an attempt to compute not just a lower bound, but exactly how many passwords the OP's criteria allow.

We have $26$ upper-case letters, $26$ lower-case letters, $10$ digits, and an unknown number of "symbols". The number of "symbols" is unknown because many websites accept only a restricted subset of the non-alphabetic, non-numeric characters that are generally available. I'll assume all password characters must be among the $94$ non-whitespace printable ASCII characters (excluding "delete") and that the symbols must be some subset of the characters that remain after we remove the $62$ letters and digits. Hence there are $n$ symbols, where $n \leq 32$.

Let $U$ be the set of upper-case letters, $L$ the set of lower-case letters, $D$ the set of digits, and $S$ the set of symbols. The total number of eight-character passwords using all characters from $U\cup L\cup D\cup S$ without restriction is $(62+n)^8.$ Exclude those that use only three of the classes of characters:

• $U\cup L\cup D$ only: $62^8$ passwords

• $U\cup L\cup S$ only: $(52+n)^8$ passwords

• $U\cup D\cup S$ only: $(36+n)^8$ passwords

• $L\cup D\cup S$ only: $(36+n)^8$ passwords

By the Inclusion-Exclusion principle, we now add back the following numbers of passwords using only two classes of characters:

• $U\cup L$ only: $52^8$ passwords

• $U\cup D$ only: $36^8$ passwords

• $L\cup D$ only: $36^8$ passwords

• $U\cup S$ only: $(26+n)^8$ passwords

• $L\cup S$ only: $(26+n)^8$ passwords

• $D\cup S$ only: $(10+n)^8$ passwords

Finally, by the Inclusion-Exclusion principle, once again exclude the passwords generated by only one class of character:

• $U$ only: $26^8$ passwords

• $L$ only: $26^8$ passwords

• $D$ only: $10^8$ passwords

• $S$ only: $n^8$ passwords

So the grand total as a function of the number of symbols, $n,$ is \begin{align} P(n) &= (62+n)^8 - 62^8 - (52+n)^8 - 2(36+n)^8 \\ &\qquad + 36^8 + 2(26+n)^8 + (10+n)^8 - 2\left(26^8\right) - 10^8 - n^8 \\ &= 2271360 n (n^4 + 155 n^3 + 10820 n^2 + 410440 n + 8287152) \end{align} (expanded and simplified by Wolfram Alpha).

Assuming the wife's password rules allow the choice of any one of the classes of characters, but then the password must be made only from characters in that set, these rules allow the user to make any of $Q(n) = 2\left(26^8\right) - 10^8 - n^8$ passwords.

The values of $P(n)$ and $Q(n)$ for some values of $n$ are:

\begin{array}{rrr} \hfill n\hfill & \hfill P(n)\hfill & \hfill Q(n)\hfill \\ \hline 1 & 19\,780\,293\,012\,480 \approx 1.98\times10^{13} & 417\,754\,129\,153 \approx 4.18\times10^{11} \\ 10 & 309\,780\,614\,707\,200 \approx 3.10\times10^{14} & 417\,854\,129\,152 \approx 4.18\times10^{11} \\ 25 & 1\,596\,945\,063\,168\,000 \approx 1.60\times10^{15} & 570\,342\,019\,777 \approx 5.70\times10^{11} \\ 32 & 2\,807\,657\,387\,458\,560 \approx 2.81\times10^{15} & 1\,517\,265\,756\,928 \approx 1.52\times10^{12}\\ \end{array}

For a reasonable number of symbols (about 25), we see that the OP's rules allow thousands of times as many passwords as the wife's. Even if there is just one symbol, $P(n)$ is more than $40$ times $Q(n).$ Of course, when $n=0$, $P(n)=0,$ since it is impossible to include a symbol in the password when no symbols are allowed.

Note, however, that the OP's relative advantage (the ratio $P(n)/Q(n)$) peaks at $n = 25$ symbols, when $P(n)/Q(n) \approx 2800.$ As $n$ increases above $25,$ the ratio rapidly falls off. If there were a much larger number of symbols available, specifically, if $n\geq 175$, the wife's rules would allow for more passwords. The extremely large number of passwords that could then be generated with symbols alone would then overwhelm the number of passwords that could be generated by replacing some of the symbols by other characters.

I'll let the binomials and the factorials, and the jokes on who's right between husbands and wives, to the other responders. They are useful and fun, but let's take another viewpoint.

The rules that restrict the choice of passwords have two aims:

• Make sure that there is a large enough pool of passwords to choose from.

• Make sure passwords people choose are reasonably spread out in that pool.

To increase the number of possible passwords, you'd increase the maximum length of the password and you'd allow more symbols in each position.

But this is not what you see in the rules: your password must be at least eight characters long, and must contain at least one character from each of these groups.

The reason is that, without those constraints, too many would choose "fido" or "1984" as their passwords. This would make the task of those who want to break into accounts way too easy, because they could focus their efforts on the (few) commonly used passwords.

So, those "distribution requirements" actually decrease the number of available passwords, but greatly improve the way they are spread out.

Now, you don't see any site requesting that your password be all lowercase or all uppercase or all digits, or all symbols for two reasons: the important one is that almost all users would go for alphabetic passwords. The other is that in fact, there would be fewer passwords to choose from (for long enough passwords).