Let \(a_n\) count the admissible permutations and put \(p_n=a_n/n!\). The exact recurrence in the companion claim is \[ a_n=(n+1)a_{n-1}-(n-2)a_{n-2}-(n-5)a_{n-3}+(n-3)a_{n-4}\qquad(n\geq4), \] with \(a_0=a_1=1\) and \(a_2=a_3=0\).

Set \(\Delta_n=p_n-p_{n-1}\). Dividing the recurrence by \(n!\), subtracting \(p_{n-1}\), and collecting terms gives \[ n\Delta_n=\Delta_{n-1}+ \frac{(n-2)p_{n-2}-(n-5)p_{n-3}+p_{n-4}} {(n-1)(n-2)}. \tag{1} \] The numerator in the fraction has the useful form \[ 3p_{n-3}+p_{n-4}+(n-2)(p_{n-2}-p_{n-3}). \tag{2} \]

Now \(p_2=p_3=0\) and \(p_4=2/4!=1/12\), so \(\Delta_4>0\). For \(n=5\), the comparison needed in (2) is \(p_3\geq p_2\). At every later step it follows from the preceding induction cases. All probabilities are nonnegative, so (2) is nonnegative. Equation (1) then gives \(\Delta_n>0\) from \(\Delta_{n-1}>0\). Induction proves \(p_n>p_{n-1}\) for every \(n\geq4\). Replacing \(n\) by \(n+1\) answers the stated question: \[ \boxed{p_{n+1}>p_n\quad\text{for every }n\geq4.} \]

The forbidden unordered value pairs are the \(n-1\) edges of the path \[ 1-2-\cdots-n. \] Choose \(k\) of these edges for an inclusion-exclusion term. If the chosen edges form \(r\) nonempty runs, they collapse to \(r\) blocks. Each block has two orientations, and collapsing all \(k\) edges leaves \(n-k\) objects to permute. The number of \(k\)-edge subsets with \(r\) runs is \[ \binom{k-1}{r-1}\binom{n-k}{r}. \] Consequently \[ a_n=n!+\sum_{k=1}^{n-1}(-1)^k(n-k)! \sum_{r=1}^{k}2^r\binom{k-1}{r-1}\binom{n-k}{r}. \tag{3} \]

Rearranging (3) as a formal power series gives \[ A(x)=\sum_{n\geq0}a_nx^n =\sum_{m\geq0}m!\left(\frac{x(1-x)}{1+x}\right)^m. \tag{4} \] If \(F(z)=\sum_{m\geq0}m!z^m\), then \[ z^2F'(z)+(z-1)F(z)+1=0. \] Substitute \(z=x(1-x)/(1+x)\) in this formal identity and extract coefficients. This yields \[ a_n=(n+1)a_{n-1}-(n-2)a_{n-2}-(n-5)a_{n-3}+(n-3)a_{n-4} \] for \(n\geq4\), starting with \(1,1,0,0\).

The first positive terms are \[ 2,14,90,646,5242,47622,479306,5296790,63779034,831283558, \] at sizes 4 through 13. This is OEIS A002464, known as Hertzsprung's problem and as permutations without rising or falling successions.

The initial counts identify OEIS A002464. Its definition matches the candidate exactly: permutations of length \(n\) without rising or falling successions. The entry records Hertzsprung's problem, the four-term recurrence, the inclusion-exclusion formula, the generating function, and references reaching back to the early twentieth century.

John Riordan's 1965 paper is devoted to the recurrence. Abramson and Moser studied the broader avoidance of rising or falling \(w\)-sequences in 1967. Flajolet and Sedgewick derive the generating function on page 373 of `Analytic Combinatorics`. Claesson's 2022 paper places the problem in the modern theory of Hertzsprung patterns.

The ménage search led to a different family: straight ménage permutations restrict the value allowed at each position. The present condition restricts neighboring values in one-line notation. Searches using the exact initial terms, A002464, Hertzsprung, successions, normalized probabilities, and monotonicity found the classical enumeration and asymptotic ratio \(p_n\sim e^{-2}\). They yielded no explicit proof or statement that \(p_{n+1}>p_n\) for every \(n\geq4\). The monotonicity proof in this entry should therefore be treated as a new derivation with novelty unverified.

The program builds \(a_0,\ldots,a_{500}\) from Riordan's recurrence. It independently evaluates the run-based inclusion-exclusion formula through size 80 and enumerates every permutation through size 9. It verifies the first-difference identity used in the proof and all strict comparisons \(p_n>p_{n-1}\) for \(4\leq n\leq500\) using exact rational arithmetic.

The compact JSON array of all 501 counts is 257,598 bytes and has SHA-256 digest `057d0a8c39cfc574ba2d08470fdbe863460b6d7ccb669aea42afe3519099b3ca`. The complete five-line output is 660 bytes including its final newline, with SHA-256 digest `809a8620b1a1cd257d8a275e8e15172a15ed0913ca0ef5c9b3da07de1d5f2394`.