in ${ {N-2} \choose {k-1}}$ ways and then permute them, keeping track of the number of left-to-right maxima with ${\{k\}!}$. For each of these, we may also then permute the rest of the entries in positions $k+1, k+2, \ldots, N-1$ in $(N-k-1)!$ ways. All together, these contribute $${\theta}^1 { {N-2} \choose {k-1}} {\{k\}!} (N-k-1)! = \frac{(N-2)!}{(k-1)!}
            {\theta}{\{k\}!}$$ to $W(N,k)$.

The initial conditions are immediate.

Now, let ${\Delta W}(N,k) = W(N,k+1) - W(N,k)$. The zeros of these polynomials will determine the intervals of ${\theta}$ that produce games for which a given positional strategy is optimal. We begin by translating the recurrence.

\[c:Wrec\] We have $${\Delta W}(N,k) = (N-1) {\Delta W}(N-1,k) + {\theta}^2 \frac{(N-2)!}{k!} {\{k\}!}$$ with initial conditions ${\Delta W}(N,N-2) = {\theta}({\theta}-(N-1)){\{N-2\}!}$.

By Theorem \[t:W\], we have $${\Delta W}(N,k) = W(N,k+1) - W(N,k) = (N-1) \left(W(N-1,k+1) - W(N-1,k)\right)$$ $$+ {\theta}(N-2)! \left( \frac{ {\{k+1\}!} }{ k! } - \frac{{\{k\}!}}{(k-1)!} \right)$$ $$= (N-1) {\Delta W}(N-1,k) + {\theta}\frac{(N-2)!}{k!} {\{k\}!} \left( ({\theta}+ k) - k \right)$$ yielding the result.

The initial conditions follow by subtracting $W(N,N-2) = (2N-3) {\theta}{\{N-2\}!}$ from $W(N,N-1) = {\theta}{\{N-1\}!}$.

It turns out that we can solve this recurrence.

\[t:dwmain\] We have $${\Delta W}(N,k) = c_1(N,k) \left( \left(\sum_{i=k+1}^{N-1} \frac{1}{i}\right){\theta}- 1 \right) {\theta}{\{k\}!}$$ for 