12
$\begingroup$

I am trying to determine all valid passwords (the password space) that fulfill this list of requirements.

  1. Password is exactly 15 characters long.
  2. Must contain at least 2 lowercase letters (26 in total).
  3. Must contain at least 2 uppercase letters (26 in total).
  4. Must contain at least 2 numbers 0-9 (10 in total).
  5. Must contain at least 2 special characters (like !, @, # ...) (35 in total).

I know that the unrestricted password space would be (26+26+10+35)^15 = 6.33*10^29 so the final answer must be less than that.

My first approach was to find all of the invalid passwords and subtract that from the unrestricted password space. However, even this step proved to be too complicated to for me. I broke down all invalid passwords into a matrix of how they fulfill the 4 "contain" requirements.

requirements fulfillment table

I thought that by finding the number of passwords that fit in each row excluding the first and last row, I'll have all invalid passwords and thus I can subtract that from the unrestricted password space. The first row is all valid passwords which what we are trying to find. The last row is impossible because it is impossible to fill 15 characters without using any lowercase, uppercase, numbers, and/or special characters at least twice. Order does matter, so permutations are used somewhere but I'm not sure how.

Any ideas on how to approach this is a simpler way? Thanks.

$\endgroup$
6
  • 1
    $\begingroup$ Probably want an inclusion-exclusion argument. It’s a little messy, but it will work. $\endgroup$ May 5, 2022 at 1:42
  • $\begingroup$ To follow Thomas comment inclusion exclusion principle with 4 subsets. $\endgroup$ May 5, 2022 at 2:02
  • $\begingroup$ @mathcounterexamples.net See the start of my answer, for an explanation of why I rejected Inclusion-Exclusion. $\endgroup$ May 5, 2022 at 4:04
  • 1
    $\begingroup$ Frame challenge: Why would anybody want such a set of restrictions? They are more burdensome to humans than doubling the required password length, and special characters in particular give you headaches on foreign-language keyboards. (If it's a machine-generated machine-used password, you don't need minimum restrictions either, there they actually reduce password space, though insignificantly.) $\endgroup$
    – toolforger
    May 6, 2022 at 11:02
  • $\begingroup$ 35 "special" characters? ASCII only has 32 punctuation/symbol characters. What are the other three? $\endgroup$
    – Dan
    May 6, 2022 at 15:57

7 Answers 7

16
$\begingroup$

The most-bullet-headed formula uses multinomials:

$$\sum_{i+j+k+l=7}\binom{15}{i+2,j+2,k+2,l+2}10^{i+2}26^{j+k+4}35^{l+2}$$ Where $i+2,j+2,k+2,l+2$ counts the the number of digits, lower case, upper case, and special characters, respectively.

The multinomial counts the number of ways to get an ordered partition of the $15$ positions into sets of sizes $i+2,j+2,k+2,l+2,$ and the exponents are the number of words using any such partition.

There are $\binom{10}{3}=120$ tuples $(i,j,k,l).$

We can simplify this formula:

$$\sum_{i+l\leq7}\binom{15}{i+2,l+2,11-i-l}10^{i+2}35^{l+2}26^{11-i-l}\sum_{j=0}^{7-i-l}\binom{11-i-l}{j+2}\\= \sum_{i+l\leq7}\binom{15}{i+2,l+2,11-i-l}10^{i+2}35^{l+2}26^{11-i-l}\left(2^{11-i-l}-2(12-i-l)\right)$$

Because the inner sum is the terms of $(1+1)^{11-i-l}$ minus the first two and last two. This means we have $36$ terms because we have $36$ pairs $(i,l)$ with $i+l\leq7.$

This might be the best way when computing for passwords of length $15.$ But for passwords of length $N$ in general, the number of terms is $\binom{N-7}{2}=O(N^2).$

The other approaches will have a fixed number of terms for all $N.$


Here is a python program that does this simpler computation:

import math

def multinomial(*args):
   n = sum(args)
   if n<0:
       return 0
   value = math.factorial(n)
   for i in args:
       if i<0:
           return 0
       value = value//math.factorial(i)
   return value

value = 0
N=15
for i in range(0,N-7):
    for l in range(0,N-7-i):
       r = N-4-l-i # r = j+k+4 in the original answer
       m = multinomial(i+2,l+2,r)
       e = (10**(i+2))*(35**(l+2))*(26**r)
       value += m*e*((2**r) - 2*(r+1))

print(value)

This returns:

244,746,643,734,876,703,775,955,600,000

or about $2.45\cdot 10^{29}.$


Inclusion/Exclusion.

Let $A$ be all $15$-letter words. Let $B,C,D,E$ all words containing $0$ or $1$ letters, respectively, from lowercase letters, uppercase letters, digits, and special characters.

You want to compute:

$$|A\setminus(B\cup C\cup D\cup E)|$$

This is, by inclusion-exclusion:

$$\begin{align} |A|-&\left(|B|+|C|+|D|+|E|\right)\\ +&\left(|B\cap C|+|B\cap D|+\cdots +|D\cap E|\right)\\ -&\left(|B\cap C\cap\cap D|+\cdots+|C\cap D\cap E|\right)\\ +&|B\cap C\cap D\cap E|\end{align}$$

The last term is zero, since it isn’t possible foe there to be fewer than 2 of each character class and still get $15$ letter words.

If there are $b,c,d,e$ characters of each type, then: $$|A|=(b+c+d+e)^{15}\\|B|=(c+d+e)^{15}+15b(c+d+e)^{14}\\ |C|=(b+d+e)^{15}+15c(b+d+e)^{14}\\ \dots$$ Where we get similar counts for $|D|$ and $|E|.$

The hard part are the other terms. I don’t see a good way to do them other than checking all four cases for the two-term cases and all eight cases for the three-term cases.

So:

$$|B\cap C|=(d+e)^{15}+15(b+c)(d+e)^{14}+15\cdot14bc(d+e)^{13}$$ and similarly for the other pairs.

$$|B\cap C\cap D|=e^{15}+15(b+c+d)e^{14}+15\cdot 14(bc+bd+cd)e^{13}\\+15\cdot 14\cdot 13bcd e^{12}$$ and similarly for the other triples.

Not pleasant, but it works.


Generating Functions

The generating function technique was a good approach. Sadly, the person who posted it deleted it rather than correct the a wrong first pass.

You want the coefficient of $\frac{x^{15}}{15!}$ in $$(e^{26x}-26x-1)^2(e^{10x}-10x-1)(e^{35x}-35x-1)$$

Expanding this gives in the general case $81$ terms, but since two of the values, $26,$ are the same, you get fewer distinct terms. Each term of the form $ax^ne^{mx}$ and contributing a term of $$a\frac{15!}{(15-n)!}m^{15-n}.$$

Some inspection shows this is the same as the inclusion-exclusion value.

It’s still a fair amount of work, but work a computer can do.

For example, the terms with $m=36$ have expansions: $2(1+35x)(1+26x)=2+122x+1820x^2,$ yielding terms $$2\cdot 36^{15}+122\cdot 15\cdot 36^{14}+1820\cdot15\cdot14\cdot 36^{13}$$

More generally, if we had $k$ disjoint character types and $b_i$ characters in type $i,$ and want a password of $N$ letters, then, for each $S\subseteq \{1,2,\dots,k\},$ define $b_{S}=\sum_{i\in S} b_i.$ Then the terms in the expansion are:

$$(-1)^{k-|S|}e^{b_Sx}\prod_{i\notin S}(1+b_ix)$$ has $k-|S|+1$ terms.

This means that in general, the product will have $$\sum_{i=0}^k (k-i +1)\binom{k}i=(k+1)2^k-k2^{k-1}=(k+2)2^{k-1}$$ terms. That’s 48 terms in the general case, but fewer when values $b_S$ are not distinct, as in the original question. Wolfram Alpha gives $36$ terms in the original.

Define $p_S=\prod_{i\in S} b_i.$

You can write the exact formula as:

$$\sum_{S}(-1)^{k-|S|}\sum_{T\subseteq S^c}p_T \frac{N!}{(N-|T|)!}b_{S}^{N-|T|}$$

You can combine terms where $|T|=i$ and it becomes:

$$T_N=\sum_{S}(-1)^{k-|S|}b_S^{N}\sum_{i=0}^{k-|S|}\frac{N!}{(N-i)!b_S^{i}}\sum_{|T|=i,T\cap S=\emptyset}p_T.$$

(Here, you need $b_{\emptyset}^0=0^0=1.$)

Of course: $$\sum_{|T|=i, T\cap S=\emptyset} p_T$$ is just the elementary symmetric polynomial of degree $i$ on the $k-|S|$ tuple $(b_r)_{r\notin S}.$

If $s_i(x_1,\dots)$ is the elementary symmetric polynomial of degree $i$ then this becomes: $$T_N=\sum_{S}(-1)^{k-|S|}b_S^{N}\sum_{i=0}^{k-|S|}\frac{N!}{(N-i)!b_S^{i}}s_i(b_r)_{r\notin S}.\tag 1$$

You see the symmetric polynomials in the inclusion-exclusion section clearly, in the computation for $|B\cap C\cap D|.$


It's not really surprising that symmetric polynomials come into it, since $T_N$ is definitely symmetric in $b_1,\dots,b_k$ since any re-ordering of the $b_i$ should give the same count. But it would be interesting to see the total expression expressed for each $N$ as a polynomial on the $s_i=s_{i}(b_i)_{i=1}^k$ for $i=0,\dots,k.$

We see that $T_N(b_1,\dots,b_k)$ is a homogeneous polynomial of degree $N$ for each $N.$ So it can be written as:

$$\sum_{i_1+2i_2+\dots+ki_k=N} c_{i_1,i_2,\dots,i_k}s_1^{i_1}s_2^{i_2}\cdots s_k^{i_k}$$

For some $c_{*}.$


The coefficient of $b_S^N$ in $(1)$ is a polynomial of degree $k-|S|$ in $N.$ So we get that $T_N$ satisfies a “simple” linear recurrence. But the recurrence is of degree $(k+2)2^{k-1},$ so it won’t be useful here for $k=4, N=15.$

But if you want to compute a lot of consecutive $T_N,$ the recurrence might be the easiest formula.

The degree of the recurrence will be smaller with repeated $b_i$ or repeated $b_S$ values more generally. In the case of the original problem, there are $1,3,4,3,1$ distinct values $B_S$ for $|S|=0,1,2,3,4$ respectively, and the recurrence is of degree $1\cdot 1+2\cdot 3+3\cdot 4+4\cdot 3+5\cdot 1=33,$ down from $48$ in the general case $k=4.$ Also, $b_{\emptyset}=0,$ so it mostly isn't needed, except when $N=0.$

And of course, $T_0=T_1=\cdots = T_7=0.$ So you need to compute $T_{8}$ through $T_{32}$ and then you get a recurrence of degree $N$ for computing higher $N.$

For each $b=b_S$ for some $S,$ let $f(b)$ be the size of the smallest $S$ which has $b_S.$ Let $B$ be the set of distinct non-zero values $b_S.$

Then we expand $$p(x)=\prod_{b\in B}(x-b)^{k+1-f(b)}=\sum_{k=0}^{D} a_ix^i.$$ We get $a_{D}=1,$ and the recurrence: $$T_{n+D}=\sum_{i=0}^{D-1} a_{i}T_{n+i},$$ when $N>0.$ In our case: $$T_{n+32}=-\sum_{i=0}^{31} a_iT_{n+i}$$ when $n>0.$

Still not practical for finding $N=15.$

But we can get the symmetric polynomial formula for $T_n$ this way. For the general case. This is because we can express the coefficients of $\prod_{S\neq\emptyset} (x-b_S)^{k+1-|S|}$ in terms of the symmetric polynomials in the general case. That is messy, but possible.

For $k=4,$

$$\begin{align}T_8/s_4^2&=2520\\ T_9/s_4^2 &= 7560s_1\\ T_{10}/s_4^2 &= 18900s_1^2-12600s_2\\ T_{11}/s_4^2&=\binom{11}{5,2,2,2}\sum b_i^3+\binom{11}{4,3,2,2}\sum_{i\neq j}b_i^2b_j+\binom{11}{3,3,3,2}s_3\end{align}$$ Th terms in $T_{11}$ are already getting messy.

I definitely don't see a good general result for computing the $c_*.$

$\endgroup$
5
  • $\begingroup$ It becomes even hard if you require two or more different lowercase letters, uppercase letters, etc. So if you don’t allow aaAA%%111111111 because the two lower case letters aren’t different. Then $$|B|=(c+d+e)^{15}+15\sum_{k=1}^{n}\binom nk(c+d+e)^{n-k}=15(1+c+d+e)^{15}-14(c+d+e)^{15}.$$ $\endgroup$ May 5, 2022 at 2:28
  • $\begingroup$ See the start of my answer, for an explanation of why I rejected Inclusion-Exclusion. $\endgroup$ May 5, 2022 at 4:03
  • $\begingroup$ @ThomasAndrews If you use my method, I do not think "different" makes it much harder. If you want at least two distinct characters from each set but otherwise allow duplicates, then I think the answer is about $2.25 \times 10^{29}$, while if you want at least two characters from each set and no character used more than once then about $8.42\times 10^{28}$. Compare this to the actual answer to this question of about $2.45\times 10^{29}$ and the unrestricted answer of $97^{15} \approx 6.33 \times 10^{29}$ $\endgroup$
    – Henry
    May 5, 2022 at 12:34
  • $\begingroup$ You say that there are four cases for the two-terms cases. Wouldn't it be six? BC, BD, BE, CD, CE, DE? For the three-term cases wouldn't there be only be four? BCD, BCE, BDE, and CDE? $\endgroup$
    – DuperSoup
    May 5, 2022 at 12:34
  • 2
    $\begingroup$ @DuperSoup four cases for each two-term case. You get zero or one lower case letter and zero or one upper case letter, for four cases. $\endgroup$ May 5, 2022 at 13:12
7
$\begingroup$

*** Edited *** I made a mistake in the generating function on my first try--so here is a corrected version.

The following solution uses a generating function combined with a computer algebra system. Readers not familiar with generating functions can find many resources in the answers to this question: How can I learn about generating functions?

The exponential generating function for the number of ways to form an acceptable password of $r$ characters is $$f(x) = (e^{26x}-1-26x)^2 (e^{10x}-1-10x)(e^{35x}-1-35x)$$ The answer to the OP is $15!$ times the coefficient of $x^{15}$ when $f(x)$ is expanded as a power series. I used Mathematica's $\texttt{Series[]}$ function to extract the coefficient, with the result that the number of acceptable passwords is $2.44747 \times 10^{29}$ or, to be precise, $244746643734876703775955600000$.

An alternative approach to finding the coefficient is to expand $f(x)$ as $$1-e^{10 x}-2 e^{26 x}-e^{35 x}+2 e^{36 x}+e^{45 x}+e^{52 x}+2 e^{61 x}-e^{62 x}-2 e^{71 x}-e^{87 x}+e^{97 x}+97 x-87 e^{10 x} x-142 e^{26 x} x-62 e^{35 x} x+122 e^{36 x} x+52 e^{45 x} x+45 e^{52 x} x+72 e^{61 x} x-35 e^{62 x} x-52 e^{71 x} x-10 e^{87 x} x+3366 x^2-2496 e^{10 x} x^2-3040 e^{26 x} x^2-1196 e^{35 x} x^2+1820 e^{36 x} x^2+676 e^{45 x} x^2+350 e^{52 x} x^2+520 e^{61 x} x^2+48620 x^3-23660 e^{10 x} x^3-18200 e^{26 x} x^3-6760 e^{35 x} x^3+236600 x^4$$ from which it is possible to "read off" the coefficient of $x^{15}$ (but I'm not going to try).

$\endgroup$
5
  • 1
    $\begingroup$ Seems odd to get a precise value ending in so many zeros. You sure there was no rounding? $\endgroup$ May 5, 2022 at 15:34
  • $\begingroup$ Okay, then ending zeros are not surprising. It certainly ends in four zeros, since one formula is $$\sum_{i+j+k+l=7}\binom{15}{i+2,j+2,k+2,l+2}10^{i+2}26^{j+k+4}35^{l+2}=6151600^2\sum\binom{15}{i+2,j+2,k+2,l+2}10^i26^{j+k}35^{l}$$ Most of these other terms have additional factors of $10,$ as will the multinomial. For example, we get two more factors of $10$ when $i\geq2,$ or $i,l\geq 1$ and $j+k\geq1,$ od when $l\geq2$ and $j+k\geq2.$ I think in other terms, you’ll get factors of $5$ from the multinomial. In any event, it is less surprising that $10^6$ factors the count. $\endgroup$ May 5, 2022 at 16:20
  • $\begingroup$ @ThomasAndrews The value (with the ending zeros) should be exact, since Mathematica uses exact rational arithmetic. $\endgroup$
    – awkward
    May 5, 2022 at 16:35
  • $\begingroup$ I used both @ThomasAndrews inclusion exclusion method and Henry's constraint table method and both gave me the same exact value of 244746643734876700000000000000. I used MATLAB for this. Can you give more information on how your answer might be more precise than the others? $\endgroup$
    – DuperSoup
    May 5, 2022 at 18:03
  • $\begingroup$ @DuperSoup I think MATLAB is using double precision floating point for its computations, so the most you can get is $16$ significant digits. By contrast, Mathematica uses exact integer and rational arithmetic with numbers essentially unlimited in length. If you know Python, you might try your computations in that language, since Python also offers exact integer arithmetic with numbers essentially unlimited in length. $\endgroup$
    – awkward
    May 5, 2022 at 18:28
6
$\begingroup$

How I would do it is set up $f_i(n)$ as the number of ways of meeting the $i$th constraint with $n$ characters just from that set. So for the first constraint you have $f_1(n)=26^n$ for $n\ge 2$ and $0$ for $n <2$, and similarly for the others. You only have to work out this from $f_i(0)$ through to $f_i(15)$.

I would then find $g_i(n)$ as the number of ways of meeting all of the initial $i$ constraints with $n$ characters just from those sets. So for the first constraint you have $g_1(n)=f_1(n)$ while for the others you have $$g_i(n) = \sum\limits_{k=0}^n {n \choose k} f_i(k)\,g_{i-1}(n-k)$$ and again you only have to find this from $g_i(0)$ through to $g_i(15)$.

The final answer here is $g_4(15) \approx 2.447\times 10^{29}$, which is about $39\%$ of your $97^{15}$ unrestricted case.

The $f_i$ and $g_i$ calculations are:

n     f_1(n)       f_2(n)    f_3(n)    f_4(n)
0  0.000000e+00 0.000000e+00  0e+00 0.000000e+00
1  0.000000e+00 0.000000e+00  0e+00 0.000000e+00
2  6.760000e+02 6.760000e+02  1e+02 1.225000e+03
3  1.757600e+04 1.757600e+04  1e+03 4.287500e+04
4  4.569760e+05 4.569760e+05  1e+04 1.500625e+06
5  1.188138e+07 1.188138e+07  1e+05 5.252188e+07
6  3.089158e+08 3.089158e+08  1e+06 1.838266e+09
7  8.031810e+09 8.031810e+09  1e+07 6.433930e+10
8  2.088271e+11 2.088271e+11  1e+08 2.251875e+12
9  5.429504e+12 5.429504e+12  1e+09 7.881564e+13
10 1.411671e+14 1.411671e+14  1e+10 2.758547e+15
11 3.670344e+15 3.670344e+15  1e+11 9.654916e+16
12 9.542896e+16 9.542896e+16  1e+12 3.379221e+18
13 2.481153e+18 2.481153e+18  1e+13 1.182727e+20
14 6.450997e+19 6.450997e+19  1e+14 4.139545e+21
15 1.677259e+21 1.677259e+21  1e+15 1.448841e+23

and

n     g_1(n)       g_2(n)       g_3(n)       g_4(n)
0  0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
1  0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
2  6.760000e+02 0.000000e+00 0.000000e+00 0.000000e+00
3  1.757600e+04 0.000000e+00 0.000000e+00 0.000000e+00
4  4.569760e+05 2.741856e+06 0.000000e+00 0.000000e+00
5  1.188138e+07 2.376275e+08 0.000000e+00 0.000000e+00
6  3.089158e+08 1.544579e+10 4.112784e+09 0.000000e+00
7  8.031810e+09 8.995627e+11 5.949828e+11 0.000000e+00
8  2.088271e+11 4.970084e+13 5.847465e+13 1.410685e+14
9  5.429504e+12 2.671316e+15 4.869830e+15 4.105093e+16
10 1.411671e+14 1.414494e+17 3.706015e+17 7.580668e+18
11 3.670344e+15 7.428777e+18 2.669386e+19 1.136213e+21
12 9.542896e+16 3.883959e+20 1.854810e+21 1.510688e+23
13 2.481153e+18 2.025613e+22 1.257366e+23 1.860364e+25
14 6.450997e+19 1.054996e+24 8.374450e+24 2.174100e+27
15 1.677259e+21 5.490676e+25 5.505214e+26 2.447466e+29

And here is a simulation using R to demonstrate that the "about $39\%$ of the unrestricted case" is correct:

goodsample <- function(n){
  s <- sample(c("L","U","N","S"), n, replace=TRUE, prob=c(26,26,10,35))
  return(sum(s=="L")>=2 & sum(s=="U")>=2 & sum(s=="N")>=2 & sum(s=="S")>=2)
  } 
set.seed(2022)
sims <- replicate(10^6, goodsample(15))
mean(sims)
# 0.38619
$\endgroup$
2
  • 3
    $\begingroup$ Nice answer. This is the equivalent of the generating function answer - it amounts to the same as multiplying the terms of $(e^{26x}-1-26x)^{2}(e^{35x}-1-35x)(e^{10x}-1-10x).$ But it makes explicit the counting argument that is hidden in the generating function argument. $\endgroup$ May 5, 2022 at 15:39
  • $\begingroup$ @Henry do you have the precise answer with all decimal places? I performed your method in MATLAB and got 2.447466437348767e+29 but I'm looking for the precise answer. $\endgroup$
    – DuperSoup
    May 5, 2022 at 18:09
5
$\begingroup$

This is an ugly problem. Usually, such a problem will yield to one of the following lines of attack:


  • Inclusion-Exclusion
  • Recursion
  • Computer simulations
  • The direct approach.

Initially, I regarded this problem as a job for Inclusion-Exclusion, as discussed here and here.

However, ultimately I rejected this approach because each constraint can be violated in two distinct ways. For example, the lowercase letters constraint can be violated by having either $(0)$ lowercase letters, or $(1)$ lowercase letter. This means (for example) that when you are considering the intersection of the violation of $(3)$ of the $(4)$ constraints, you have to analyze $(2^3)$ situations.

I then considered Recursion. I rejected this approach only because I could not find an elegant way to make it work.

Using a Computer simulation against the original problem is probably not feasible. In my experience, the PC will balk at much greater than $(10)^8$ cases.


This leaves the direct approach. The analysis and computations below are straightforward, but very clumsy. If an exact value is required, then I advise using this answer as a guide and having a computer program do all of the computations.

Stars and Bars theory is discussed here and here.

Superficially, one surmises that this is not a Stars and Bars problem. That is not exactly correct. You can use Stars and Bars theory as a guide in determining how many situations need to be explored, and (more importantly) which situations may be grouped together.


Assume that all $(4)$ of the constraints are obeyed.

Let $x_1$ denote $(-2)~ + $ the # of lowercase letters used.

Let $x_2$ denote $(-2)~ + $ the # of uppercase letters used.

Let $x_3$ denote $(-2)~ + $ the # of numerical characters used.

Let $x_4$ denote $(-2)~ + $ the # of special characters used.

Then, the number of different situations to explore is equal to the number of non-negative integer solutions to

$$x_1 + x_2 + x_3 + x_4 = 7 ~: \binom{10}{3} = 120 ~\text{solutions}. \tag2 $$

These $(120)$ solutions will be grouped in common patterns.

I will use the syntax $(a,b,c,d)$ to denote that these $4$ amounts represent the values assigned to the $(4)$ variables $x_1, x_2, x_3, x_4$, in some order.

I will use the variable $T_k$ to denote the computation associated with Case $k$, below.

In each Case below, I will identify how many of the $(120)$ distinct solutions are represented by that Case.

I will use the syntax of $[(a,b,c,d)]$ to denote specifically that $x_1 = a, x_2 = b, x_3 = c, x_4 = d.$


$\underline{\text{Helper Function} ~: f([a,b,c,d)]}$
I will use the function $f([a,b,c,d)]$ to denote the number of valid passwords associated with $[(a,b,c,d)].$

The general formula is

$$f([a,b,c,d)] =$$

$$\binom{15}{a+2} \times (26)^{(a+2)} \times \binom{13-a}{b+2} \times (26)^{(b+2)} $$

$$\times \binom{11-a-b}{c+2} \times (10)^{(c+2)} \times \binom{9-a-b-c}{d+2} \times (35)^{(d+2)}. \tag3 $$


$\underline{\text{Case 1: Pattern} ~= (7,0,0,0)}$
Number of solutions $~= 4.$

$T_1 = $
$f[(7,0,0,0)]$
$+ ~f[(0,7,0,0)]$
$+ ~f[(0,0,7,0)]$
$+ ~f[(0,0,0,7)].$


$\underline{\text{Case 2: Pattern} ~= (6,1,0,0)}$
Number of solutions $~= 12.$

$T_2 = $
$f[(6,1,0,0)]$
$+ ~f[(6,0,1,0)]$
$+ ~f[(6,0,0,1)]$

$+ ~f[(1,6,0,0)]$
$+ ~f[(0,6,1,0)]$
$+ ~f[(0,6,0,1)]$

$+ ~f[(1,0,6,0)]$
$+ ~f[(0,1,6,0)]$
$+ ~f[(0,0,6,1)]$

$+ ~f[(1,0,0,6)]$
$+ ~f[(0,1,0,6)]$
$+ ~f[(0,0,1,6)].$


$\underline{\text{Case 3: Pattern} ~= (5,2,0,0)}$
Number of solutions $~= 12.$

$T_3 = $
$f[(5,2,0,0)]$
$+ ~f[(5,0,2,0)]$
$+ ~f[(5,0,0,2)]$

$+ ~f[(2,5,0,0)]$
$+ ~f[(0,5,2,0)]$
$+ ~f[(0,5,0,2)]$

$+ ~f[(2,0,5,0)]$
$+ ~f[(0,2,5,0)]$
$+ ~f[(0,0,5,2)]$

$+ ~f[(2,0,0,5)]$
$+ ~f[(0,2,0,5)]$
$+ ~f[(0,0,2,5)].$


$\underline{\text{Case 4: Pattern} ~= (5,1,1,0)}$
Number of solutions $~= 12.$

$T_4 = $
$f[(5,0,1,1)]$
$+ ~f[(5,1,0,1)]$
$+ ~f[(5,1,1,0)]$

$+ ~f[(0,5,1,1)]$
$+ ~f[(1,5,0,1)]$
$+ ~f[(1,5,1,0)]$

$+ ~f[(0,1,5,1)]$
$+ ~f[(1,0,5,1)]$
$+ ~f[(1,1,5,0)]$

$+ ~f[(0,1,1,5)]$
$+ ~f[(1,0,1,5)]$
$+ ~f[(1,1,0,5)].$


$\underline{\text{Case 5: Pattern} ~= (4,3,0,0)}$
Number of solutions $~= 12.$

$T_5 = $
$f[(4,3,0,0)]$
$+ ~f[(4,0,3,0)]$
$+ ~f[(4,0,0,3)]$

$+ ~f[(3,4,0,0)]$
$+ ~f[(0,4,3,0)]$
$+ ~f[(0,4,0,3)]$

$+ ~f[(3,0,4,0)]$
$+ ~f[(0,3,4,0)]$
$+ ~f[(0,0,4,3)]$

$+ ~f[(3,0,0,4)]$
$+ ~f[(0,3,0,4)]$
$+ ~f[(0,0,3,4)].$


$\underline{\text{Case 6: Pattern} ~= (4,2,1,0)}$
Number of solutions $~= 24.$

$T_6 = $
$f[(4,2,1,0)]$
$+ ~f[(4,2,0,1)]$
$+ ~f[(4,1,2,0)]$
$+ ~f[(4,0,2,1)]$
$+ ~f[(4,1,0,2)]$
$+ ~f[(4,0,1,2)]$

$+ ~f[(2,4,1,0)]$
$+ ~f[(2,4,0,1)]$
$+ ~f[(1,4,2,0)]$
$+ ~f[(0,4,2,1)]$
$+ ~f[(1,4,0,2)]$
$+ ~f[(0,4,1,2)]$

$+ ~f[(2,1,4,0)]$
$+ ~f[(2,0,4,1)]$
$+ ~f[(1,2,4,0)]$
$+ ~f[(0,2,4,1)]$
$+ ~f[(1,0,4,2)]$
$+ ~f[(0,1,4,2)]$

$+ ~f[(2,1,0,4)]$
$+ ~f[(2,0,1,4)]$
$+ ~f[(1,2,0,4)]$
$+ ~f[(0,2,1,4)]$
$+ ~f[(1,0,2,4)]$
$+ ~f[(0,1,2,4)].$


$\underline{\text{Case 7: Pattern} ~= (4,1,1,1)}$
Number of solutions $~= 4.$

$T_7 = $
$f[(4,1,1,1)]$
$+ ~f[(1,4,1,1)]$
$+ ~f[(1,1,4,1)]$
$+ ~f[(1,1,1,4)].$


$\underline{\text{Case 8: Pattern} ~= (3,3,1,0)}$
Number of solutions $~= 12.$

$T_8 = $
$f[(1,0,3,3)]$
$+ ~f[(1,3,0,3)]$
$+ ~f[(1,3,3,0)]$

$+ ~f[(0,1,3,3)]$
$+ ~f[(3,1,0,3)]$
$+ ~f[(3,1,3,0)]$

$+ ~f[(0,3,1,3)]$
$+ ~f[(3,0,1,3)]$
$+ ~f[(3,3,1,0)]$

$+ ~f[(0,3,3,1)]$
$+ ~f[(3,0,3,1)]$
$+ ~f[(3,3,0,1)].$


$\underline{\text{Case 9: Pattern} ~= (3,2,2,0)}$
Number of solutions $~= 12.$

$T_9 = $
$f[(3,0,2,2)]$
$+ ~f[(3,2,0,2)]$
$+ ~f[(3,2,2,0)]$

$+ ~f[(0,3,2,2)]$
$+ ~f[(2,3,0,2)]$
$+ ~f[(2,3,2,0)]$

$+ ~f[(0,2,3,2)]$
$+ ~f[(2,0,3,2)]$
$+ ~f[(2,2,3,0)]$

$+ ~f[(0,2,2,3)]$
$+ ~f[(2,0,2,3)]$
$+ ~f[(2,2,0,3)].$


$\underline{\text{Case 10: Pattern} ~= (3,2,1,1)}$
Number of solutions $~= 12.$

$T_{10} = $
$f[(3,2,1,1)]$
$+ ~f[(3,1,2,1)]$
$+ ~f[(3,1,1,2)]$

$+ ~f[(2,3,1,1)]$
$+ ~f[(1,3,2,1)]$
$+ ~f[(1,3,1,2)]$

$+ ~f[(2,1,3,1)]$
$+ ~f[(1,2,3,1)]$
$+ ~f[(1,1,3,2)]$

$+ ~f[(2,1,1,3)]$
$+ ~f[(1,2,1,3)]$
$+ ~f[(1,1,2,3)].$


$\underline{\text{Case 11: Pattern} ~= (2,2,2,1)}$
Number of solutions $~= 4.$

$T_{11} = $
$f[(1,2,2,2)]$
$+ ~f[(2,1,2,2)]$
$+ ~f[(2,2,1,2)]$
$+ ~f[(2,2,2,1)].$


Final Computation:

$$\sum_{r=1}^{11} T_r.$$

$\endgroup$
3
$\begingroup$

If you are OK with an approximate answer, by far the easiest way to get it is to generate 1 million passwords in the un-restricted space, and see what percent of them meet all the restrictions. This is relatively computationally efficient as long as the restrictions don't restrict almost all of the un-restricted space.

$\endgroup$
1
  • 2
    $\begingroup$ I have just added that simulation to the end of my answer. The million simulations suggested a proportion of $38.619\%$ compared with an exact figure closer to $ 38.64921\%$ $\endgroup$
    – Henry
    May 5, 2022 at 15:28
2
$\begingroup$

I think this can be best handled by generating functions

Each type must have at least two, so any type can't have more than a maximum of $15-2\cdot3 = 9$

But each type has a number of distinct characters, eg $10$ digits, $26$ upper case, $26$ lower case, and $35$ special characters

The generating function needed to give possible permutations correcting for multiple occurrences of $10$ distinct digits will thus be

$f(10x)=\left(\frac{(10x)^2}{2!} + \frac{(10x)^3}{3!} +\frac{(10x)^4}{4!} + .... +\frac{(10x)^9}{9!}\right)$,

You can see from the expression that the factorials in the denominator correct for multiple occurrences of a symbol in the permutations.

Similarly, for characters we shall use $f(26x)^2$ (the exponent coming because of upper case and lower case), and $f(35x)$ for special characters

Finally, we need to extract $15!$ times the coefficient of $x^{15}$ from the expression

$f(10x)\cdot f(26x)^2\cdot f(35x)$

This type of generating function is called an exponential generating function which you might like to look up, and could have been written in a more compact form using the symbol e, but has been written in a form that indicates how repetitions of the same element have been compensated for.

$\endgroup$
4
  • 3
    $\begingroup$ This solution never uses the fact that there are 26 letters, 10 digits and 35 special characters. These three numbers need to go into the formula somewhere. $\endgroup$
    – quarague
    May 5, 2022 at 13:14
  • 1
    $\begingroup$ That number seems way too small. This doesn’t take into account the number of letters in each class. The technique can work but you need to have four different terms. For example, for the numeric digit count, you’d have $$\frac{10^2x^ 2}{2!}+\cdot+\frac{10^9x^{9}}{9!}$$ In generall it will be the coefficient of $x^{15}$ in $f(26x)^2f(10x)f(35x)$ where $f(x)$ is your polynomial. $\endgroup$ May 5, 2022 at 13:20
  • $\begingroup$ @quarague: Thanks for pointing out the omission. $\endgroup$ May 6, 2022 at 8:44
  • $\begingroup$ @Thomas Andrews: Thanks, have amended, though belatedly. $\endgroup$ May 6, 2022 at 8:45
1
$\begingroup$

Another technique for solving this kind of problem is dynamic programming: Count the number of strings that satisfy similar constraints for all the lengths up to 15.

Define a function $f(n, u, l, d, s)$ := number of ways to create a password of length $n$, using at least $u$ uppercase letters, at least $l$ lowercase letters, at least $d$ digits, and at least $s$ symbols.

$f(0, u, l, d, s) = $
      $1$ if $u <= 0$, $l <= 0$, $d <= 0$ and $s <= 0$
      $0$ otherwise

Reason: There's only one string of length zero: the empty string. If u, l, d, and s are all <= 0, then it satisfies the constraints. If any of them are positive, there are no strings that satisfy the constraints.

Every string of length > $1$ is (one of those four types) followed by (a string of length $n-1$, with requirements decreased by whatever the first character was)

For n > 0: $f(n,u,l,d,s) = 26*f(n-1,u-1,l,d,s) + 26*f(n-1,u,l-1,d,s) + 10*f(n-1,u,l,d-1,s) + 35*f(n-1,u,l,d,s-1)$

For example, the #(5 character passwords with at least 2 uppercase letters and 1 digit) equals #(uppercase letters)#(4 character passwords with as least 1 uppercase letter and at least 1 digit) + #(lowercase letters)#(4 character passwords with at least 2 uppercase and 1 digit) + #(digits)#(4 character passwords with at least 2 uppercase) + #(symbols)#(4 character passwords with at least 2 uppercase and 1 digit).

Next, every time you finish evaluating $f$ for some list of arguments, store the result. If you ever need $f$ for that list again, just use the previously calculated value.

To calculate f(15,2,2,2,2) you'll use 153333 intermediate values (n is 0,1,2,..., or 14) * (u is <=0, 1, or 2) * (l is <= 0, 1, or 2) * (d is <= 0, 1, or 2) * (s is <= 0, 1, or 2).

Sample Javascript code:

function f(n, u, l, d, s) {
    if (n == 0) { return u <= 0 && l <= 0 && d <= 0 && s <= 0 ? 1n : 0n; }
    var k = [n,u,l,d,s].join(' ');
    if (k in f) return f[k];
    return f[k] = 26n*f(n-1, Math.max(u-1, 0), l, d, s) + 26n*f(n-1, u, Math.max(l-1, 0), d, s) + 10n*f(n-1, u, l, Math.max(d-1, 0), s) + 35n*f(n-1, u, l, d, Math.max(s-1, 0));
}
f(15,2,2,2,2)
244746643734876703775955600000n
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .