Calculating permutations for a specific password policy

The security researcher Troy Hunt posted an example of an obscure password policy and I've been trying to figure out how to calculate the possible permutations (Source: https://twitter.com/troyhunt/status/885243624933400577)

The rules are:

• The password must contain $9$ numbers (and only $9$ numbers)
• It must include at least $4$ different numbers
• It cannot include the same number more than three times

I understand the basic permutations will be $10^9$ ($0-9$ nine times) $= 1,000,000,000$

What I don't understand is how you factor in the reduction in permutations by enforcing $4$ different numbers and limiting repeats to $3$.

• Perhaps en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle will help out. Jul 14 '17 at 12:41
• I would first count the number of passwords obeying the first and third conditions, then subtract off those also not obeying the second condition. This is because the number of passwords obeying the first and third conditions but not the second will be relatively easy to count. Jul 14 '17 at 12:58

We calculate the number of valid passwords with the help of exponential generating functions.

At first we are looking for strings of length $9$ built from the alphabet $V=\{0,1,\ldots,9\}$ which contain a digit from $V$ no more than three times.

The number of occurrences of a digit can be encoded as \begin{align*} 1+x+\frac{x^2}{2!}+\frac{x^3}{3!} \end{align*}

In the following we denote with $[x^n]$ the coefficient of $x^n$ in a series. Since we have to consider ten digits building strings of length $9$ we calculate with some help of Wolfram Alpha \begin{align*} 9![x^{9}]\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^{10}=916\,927\,200\tag{1} \end{align*}

The second condition requires at least four different digits for valid passwords.

We respect the second condition by subtracting invalid words from (1).

• We observe there are no words of length $9$ which consist of one or two different digits whereby each digit does not occur more than three times.

• We conclude the only type of invalid strings of length $9$ counted in (1) is built of words with three different digits each digit occurring exactly three times.

There are $\binom{10}{3}$ possibilities to choose three digits out of $V$. The first digit can be placed in $\binom{9}{3}$ different ways, leaving $\binom{6}{3}$ different possibilities for the second digit and $\binom{3}{3}$ for the third digit.

We finally conclude the number of valid passwords is \begin{align*} 9![x^{9}]&\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^{10}-\binom{10}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}\\ &=916\,927\,200-120\cdot 84\cdot 20\cdot 1\\ &=916\,927\,200-201\,600\\ &=\color{blue}{916\,725\,600} \end{align*}

The multiplicities of the various digits in an admissible password induce a partition of $9$ into $\geq4$ parts of size $\leq3$. There are $11$ such partitions, beginning with $(3,3,2,1)$, $(3,3,1,1,1)$, $\ldots$, and ending with nine ones. We list them in the format $(x,y,z)$, whereby $x$, $y$, $z$ denote the number of parts of size $3$, $2$, $1$: \eqalign{&(2,1,1),\quad(2,0,3),\quad(1,3,0),\quad(1,2,2),\quad(1,1,4),\quad(1,0,6),\cr &(0,4,1),\quad(0,3,3),\quad(0,2,5),\quad(0,1,7),\quad(0,0,9)\ .\cr} Given such a partition $(x,y,z)$ we can choose the $x$ digits that appear three times in ${10\choose x}$ ways, then the $y$ digits that appear $2$ times in ${10-x\choose y}$ ways, and finally the $z$ digits that appear just once in ${10-x-y\choose z}$ ways. When the digits have been chosen they can be arranged in $${9!\over (3!)^x(2!)^y(1!)^z}$$ ways. It follows that the total number $N$ of admissible passwords is given by $$N=\sum_{k=1}^{11} {10\choose x_k}{10-x_k\choose y_k}{10-x_k-y_k\choose z_k}{9!\over 6^{x_k} \cdot 2^{y_k}}=916\,725\,600\ .$$

A brute force solution:

Nine numbers: Each number appears exactly once. We choose nine of the ten digits, then arrange the selected digits. $$\binom{10}{9}9!$$

Eight numbers: We must use of the ten digits twice. We choose that digit, choose two of the nine locations for that number, choose seven of the other nine numbers, then arrange them in the seven open positions. $$10\binom{9}{2}\binom{9}{7}7!$$

Seven numbers: There are two ways of partitioning $9$ into seven positive integers. \begin{align*} 9 & = 3 + 1 + 1 + 1 + 1 + 1 + 1\\ & = 2 + 2 + 1 + 1 + 1 + 1 + 1 \end{align*}

One number appears three times, and six appear once each: We choose which of the ten digits appears three times, choose three of the nine positions for the numbers, select six of the other nine numbers, and arrange them in the six open positions.
$$10\binom{9}{3}\binom{9}{6}6!$$

Two digits appear twice, five numbers appear once each: We choose which two of the ten digits will appear twice, choose two of the nine positions for the smaller of those numbers, choose two of the seven remaining open positions for the larger of those numbers, choose five of the eight remaining numbers, and arrange them in the five open positions. $$\binom{10}{2}\binom{9}{2}\binom{7}{2}\binom{8}{5}5!$$

Six numbers: We partition $9$ into six positive integers. \begin{align*} 9 & = \color{red}{4 + 1 + 1 + 1 + 1 + 1}\\ & = 3 + 2 + 1 + 1 + 1 + 1\\ & = 2 + 2 + 2 + 1 + 1 + 1 \end{align*} The partition shown in red is prohibited since no number may appear more than three times.

One number appears three times, another number appears twice, and four numbers appear once each: We choose the number that appears three times, choose three of the nine positions for that number, choose which of the nine remaining numbers appears twice, choose two of the six remaining positions for that numbers, choose four of the eight remaining numbers, and arrange them in the four remaining positions. $$10\binom{9}{3} \cdot 9\binom{6}{2}\binom{8}{4}4!$$

Three numbers appear twice each, and three numbers appear once each: We choose three numbers to appear twice each, choose two of the nine positions for the smallest of those numbers, choose two of the seven remaining positions for the next smallest of those numbers, choose two of the five remaining positions for the largest of those numbers, choose three of the seven remaining numbers to appear once each, and arrange them in the the three remaining positions. $$\binom{10}{3}\binom{9}{2}\binom{7}{2}\binom{5}{2}\binom{7}{3}3!$$

We can partition $9$ into exactly five numbers in the following ways: \begin{align*} 9 & = \color{red}{5 + 1 + 1 + 1 + 1}\\ & = \color{red}{4 + 2 + 1 + 1 + 1}\\ & = 3 + 3 + 1 + 1 + 1\\ & = 3 + 2 + 2 + 1 + 1\\ & = 2 + 2 + 2 + 2 + 1 \end{align*}

We can partition $9$ into exactly four numbers in the following ways: \begin{align*} 9 & = \color{red}{6 + 1 + 1 + 1}\\ & = \color{red}{5 + 2 + 1 + 1}\\ & = \color{red}{4 + 3 + 1 + 1}\\ & = \color{red}{4 + 2 + 2 + 1}\\ & = 3 + 3 + 2 + 1\\ & = 3 + 2 + 2 + 2 \end{align*} The partitions shown in red are prohibited by the constraint that no digit can appear more than thrice.

Can you continue?

First, each number can appear at most 3 times. So we are choosing 9 elements from

1, 1, 1, 2, 2, 2, ..., 9, 9, 9.

Then, there must be at least 4 kinds of numbers. It's impossible to have 1, 2 kinds of numbers. The number of 3 kinds is 9 choose 3.

So 27 choose 9 - 9 choose 3 = 4686741 is the final answer.

• Your answer is incorrect. You have not taken the order of the elements into account. Also, to obtain $\binom{n}{k}$, type \binom{n}{k} when you are in math mode. Here is a tutorial on how to typeset mathematics on this site. Jul 15 '17 at 10:00