Sets of two-digit numbers, such that...

We'll solve the problem in the general case, namely for $n$ distinct digits, using recurrence relations. Let the answer be $a_n$ . Notice that $a_0=1, a_1=0, a_2=0$ .

Let's consider the digits with which the two $0$ 's are paired. Call them $x$ and $y$ . If the second $x$ is paired with the second $y$ , we have $a_{n-3}$ ways to pair off the rest of the digits. If on the other hand $x$ is paired with, say, $z$ , we now consider the second $y$ and the second $z$ 's relation: if they're paired together, there's $a_{n-4}$ ways to pair the rest, otherwise let the second $z$ be paired with $\alpha$ , and so on.

In general, if the cycle binding $x$ and $y$ together lasts for $k$ numbers, we have:

$\large\binom{n-1}{k-1}\cdot\frac{(k-1)!}{2}\cdot a_{n-k}=\large\frac{(n-1)!}{2\cdot(n-k)!}\cdot a_{n-k}$

solutions. That is true, because there's $\large\binom{n-1}{k-1}$ ways to pick the $k$ digits (0 is always included), and $(k-1)!$ ways to make a cycle of length $k$ with those digits. Since we order the digits in each number such that the first is smaller than the second, we've counted each cycle twice - once properly and once in reverse.

So we've arrived at the recurrence relation:

$\displaystyle a_{n}=\sum_{k=3}^{n} \frac{(n-1)!}{2\cdot (n-k)!}\cdot a_{n-k}=\sum_{k=0}^{n-3} \frac{(n-1)!}{2\cdot k!}\cdot a_{k}$

We sum from $k=3$ because it's impossible for the cycle containing the two $0$ 's, $x$ 's and $y$ 's to be of length shorter than $3$ .

Multiplying by $n$ , it's easily seen the equation is equivalent to $a_{n+1}=n\cdot a_n+\binom{n}{2}a_{n-2}$ .

Plugging in successively larger values for $n$ , one finds $a_{10}=286884$ .