How to find the password space given several restrictions? I am trying to determine all valid passwords (the password space) that fulfill this list of requirements.

*

*Password is exactly 15 characters long.

*Must contain at least 2 lowercase letters (26 in total).

*Must contain at least 2 uppercase letters (26 in total).

*Must contain at least 2 numbers 0-9 (10 in total).

*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.
 A: 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.
A: 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.
A: 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

