This problem is solved using dynamic programming. Let ~f(n, c)~ be the number of sequences of length ~n~ with confusion ~c~.

The number of such sequences that start with the number ~1~ is ~f(n-1, c)~ because the ~1~ does not affect the confusion of the rest of the sequence and it makes no difference if we use numbers ~1 \dots n-1~ or ~2 \dots n~.

If ~1~ is the second number, then ~f(n, c) = f(n-1, c-1)~ because whichever element is first, it will form a confused pair with the ~1~. It's easy to see that the complete relation is:

$$\displaystyle f(n,c) = \sum_{i=0}^{n-1} f(n-1,c-i)$$

The time complexity of a direct implementation of this formula (using dynamic programming) would be ~\mathcal O(N^2 C)~, which is too slow.

We need to note that ~f(n, c) = f(n, c-1) + f(n-1, c) - f(n-1, c-n)~, which leads to an ~\mathcal O(NC)~ solution. It is also possible to cut down on the memory used by keeping only two rows of the matrix used for calculations at any time.