How to find the password space given several restrictions?

Question

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.

Answer 1

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_*.$

Answer 2

*** 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).

Answer 3

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

Answer 4

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.$$

Answer 5

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.

Answer 6

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.

Answer 7

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