# P2536: Monotonicity of consecutive-adjacency avoidance in random permutations

- ID: `P2536`
- Reference: `permutation-no-consecutive-adjacency-monotone`
- Page: https://theoremdb.org/statements/P2536
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(p_n\) be the probability that a uniformly random permutation \(\pi\) of \(\{1,\ldots,n\}\) satisfies \(|\pi_{i+1}-\pi_i|\ne1\) for every \(i\). Is \(p_{n+1}>p_n\) for every \(n\ge4\)?

### Problem setup

- **Definition.** Adjacency refers to neighboring positions in the one-line permutation.
- **Remark.** The forbidden unordered value pairs are \(\{1,2\},\ldots,\{n-1,n\}\).

### What counts as a solution

- Prove strict monotonicity for every n at least 4, or give a specific n at least 4 with \(p_{n+1}\le p_n\).

## The answer

For every integer n at least 4, p_(n+1) is strictly greater than p_n, so the avoidance probability is strictly increasing. [4](#reference-4)

**Review status:** Supported.

**Lean verification:** not Lean-verified.

### Resolution argument

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.}
\]

## Work

### Proof and evidence for the resolution

**Proposition 1 (Direct answer and proof for Monotonicity of consecutive-adjacency avoidance in random permutations).** For every integer n at least 4, p_(n+1) is strictly greater than p_n, so the avoidance probability is strictly increasing.

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.}
\]

### Background and intake notes

The limit is expected to reflect a Poisson law for the roughly two appearances of forbidden adjacencies, but an asymptotic limit alone does not settle every finite comparison.

- Original intake status: Status not established. No literature search was performed. Menage-type adjacency avoidance is classical and may contain this sequence.
- The attractive route inserts n+1 into a good permutation of size n.
- The obstruction is that deleting n+1 can create a new forbidden adjacency across the deletion site, so the obvious insertion-deletion coupling does not compare the events cleanly. Record any refined coupling by the two exposed neighbors.

- Recorded example: There are 2 good permutations at n=4 and 14 at n=5.

### Supporting results

- **Proposition 2** (supported): Runs of selected path edges give an exact double sum, its generating function, and Riordan's four-term recurrence. [6](#reference-6)

### Prior approaches

- **Route 1** (supported): OEIS A002464, Riordan's 1965 paper, and Analytic Combinatorics cover the enumeration; the focused search found no explicit probability-monotonicity result. [6](#reference-6) [4](#reference-4) [3](#reference-3) [1](#reference-1) [5](#reference-5) [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks all 501 recurrence terms, inclusion-exclusion through 80, direct enumeration through 9, and every probability comparison through 500. [6](#reference-6)

### Computational notes

- Complete permutation enumeration gave good counts 2, 14, 90, 646, 5242, 47622, and 479306 for \(4\le n\le10\). Dividing by n! gives approximately 0.0833333, 0.116667, 0.125, 0.128175, 0.130010, 0.131233, and 0.132084, strictly increasing on this checked range.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `permutation-no-consecutive-adjacency-monotone`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20permutation-no-consecutive-adjacency-monotone%0A%0AExact%20title%3A%20Monotonicity%20of%20consecutive-adjacency%20avoidance%20in%20random%20permutations%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Fpermutation-no-consecutive-adjacency-monotone%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009. page 373 https://algo.inria.fr/flajolet/Publications/book.pdf
   - book; secondary source; PDF checked 2026-08-01; checked 2026-08-01
   - Source use: citation_only
   - For Monotonicity of consecutive-adjacency avoidance in random permutations, the reviewed source scope is page 373. The packet makes no inference beyond that cited scope.
2. <a id="reference-2"></a>Yiting Li, “Ménage Numbers and Ménage Permutations,” Journal of Integer Sequences 18 (2015), article 15.6.8; arXiv:1502.06068v1. definitions and enumerative results for ménage permutations https://arxiv.org/abs/1502.06068
   - preprint; secondary source; arXiv:1502.06068v1; checked 2026-08-01
   - Source use: citation_only
   - For Monotonicity of consecutive-adjacency avoidance in random permutations, this source describes a different permutation-restriction family that the source review checked and excluded; it is analogy only.
3. <a id="reference-3"></a>Morton Abramson and W. O. J. Moser, “Permutations without Rising or Falling $\omega$-Sequences”. The Annals of Mathematical Statistics 38(4) (1967), 1245-1254. DOI 10.1214/aoms/1177698793. Full journal article relevant to Monotonicity of consecutive-adjacency avoidance in random permutations. https://doi.org/10.1214/aoms/1177698793
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Monotonicity of consecutive-adjacency avoidance in random permutations, the reviewed source scope is Full journal article relevant to Monotonicity of consecutive-adjacency avoidance in random permutations.. The packet makes no inference beyond that cited scope.
4. <a id="reference-4"></a>John Riordan, “A Recurrence for Permutations without Rising or Falling Successions”. The Annals of Mathematical Statistics 36(2) (1965), 708-710. DOI 10.1214/aoms/1177700181. Full journal article relevant to Monotonicity of consecutive-adjacency avoidance in random permutations. https://doi.org/10.1214/aoms/1177700181
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Monotonicity of consecutive-adjacency avoidance in random permutations, the reviewed source scope is Full journal article relevant to Monotonicity of consecutive-adjacency avoidance in random permutations.. The packet makes no inference beyond that cited scope.
5. <a id="reference-5"></a>Anders Claesson, “From Hertzsprung’s problem to pattern-rewriting systems”. Algebraic Combinatorics 5(6) (2022), 1257-1277. DOI 10.5802/alco.202. Full journal article relevant to Monotonicity of consecutive-adjacency avoidance in random permutations. https://doi.org/10.5802/alco.202
   - journal_article; secondary source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Monotonicity of consecutive-adjacency avoidance in random permutations, the reviewed source scope is Full journal article relevant to Monotonicity of consecutive-adjacency avoidance in random permutations.. The packet makes no inference beyond that cited scope.
6. <a id="reference-6"></a>OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, A002464, “Hertzsprung's problem: permutations without rising or falling successions”, entry checked 2026-08-01. OEIS A002464 definition, formulas, and references; Riordan (1965); Flajolet and Sedgewick, Analytic Combinatorics (2009), page 373 https://oeis.org/A002464
   - Also cited at Inline CPython source below, executed on 2026-07-24
   - reference_database; reference source; web version checked 2026-08-01; checked 2026-07-24
   - Source use: citation_only
   - Records the exact sequence, recurrence, and generating function used to identify and cross-check the Hertzsprung enumeration.