The devil

If $n \ge 2$ , the number of orderings where the first $u$ (but not the first $u+1$ ) are correct, and where the last $v$ (but not the last $v+1$ ) are correct, is (by the Inclusion-Exclusion Principle): $(n-u-v)! - (n-u-v-1)! - (n-u-v-1)! + (n-u-v-2)!$ provided that $u+v \le n-2$ . Thus the probability that, when $n$ symbols are shuffled, precisely $a$ symbols are fixed, leaving $n-a$ symbols to be shuffled next time around, is $p_{n,a} \; =\; \left\{ \begin{array}{lcl}\frac{(a+1)\big[(n-a)! - 2(n-a-1)! + (n-a-2)!\big]}{n!} & \quad & 0 \le a \le n-2 \\ 0 & \quad & a = n-1 \\ \frac{1}{n!} & \quad & a = n \end{array} \right.$ Using conditional expectations (and setting $X(0) = 0$ for convenience) $\begin{array}{rcl} X(n) & = & \displaystyle\sum_{a=0}^n p_{n,a}\big(1 + X(n-a)\big) \; = \; 1 + \sum_{a=0}^n p_{n,a} X(n-a) \\ & = & \displaystyle1 + \sum_{a=0}^{n-2} p_{n,a}X(n-a) \; = \; 1 + \sum_{a=0}^{n-2} \frac{(a+1)\big[(n-a)! - 2(n-a-1)! + (n-a-2)!\big]}{n!}X(n-a) \\ & = & \displaystyle1 + \sum_{a=2}^n \frac{(n+1-a)[ a! - 2(a-1)! + (a-2)!]}{n!}X(a) \\ & = & \displaystyle1 + \sum_{a=2}^n \frac{(n+1-a)(a^2 - 3a + 3)(a-2)!}{n!}X(a) \end{array}$ for all $n \ge 2$ , so that $X(2) = 2$ and $X(n) \; = \; \dfrac{n(n-1)}{2n-3}\left[1 + \sum_{a=2}^{n-1} \frac{(n+1-a)(a^2 - 3a + 3)(a-2)!}{n!}X(a)\right]$ for all $n \ge 3$ .

A quick computer calculation yields $X(15) \; =\; \dfrac{469087886108518}{8538321867075}$ so the answer is $469087886108518 + 8538321867075 = 477626207975593$ .