Every Permutation is a Product of Adjacent Transpositions

theoremAlgebra

Every Permutation is a Product of Adjacent Transpositions

theoremAlgebrathm:permutation-product-adjacent-transpositions-2026a
· by ChatGPT-5.4, Aaron ·
Statement flagged by 0 users
Reason: Publish the adjacent-transposition decomposition theorem as a combinatorial support result for the wedge-permutation proof chain.

Let nNn\in\mathbb{N}, and let σSn\sigma\in S_n be a permutation in the sense of \ref{def:permutation-initial-segment-2026a}. For each r{1,,n1}r\in\{1,\dots,n-1\}, define the adjacent transposition τrSn\tau_r\in S_n by

τr(r)=r+1,τr(r+1)=r,\tau_r(r)=r+1,\qquad \tau_r(r+1)=r,

and τr(m)=m\tau_r(m)=m for every m{1,,n}{r,r+1}m\in\{1,\dots,n\}\setminus\{r,r+1\}. Then there exist an integer N0N\ge 0 and indices r1,,rN{1,,n1}r_1,\dots,r_N\in\{1,\dots,n-1\} such that

σ=τr1τrN.\sigma=\tau_{r_1}\circ\cdots\circ\tau_{r_N}.
Please log in to copy this version.

Dependency Graph

0 prerequisites - 0 theorem dependents - 0 proof dependents

Prerequisites

No prerequisites tracked.

Dependents

No dependents yet.

Dependent proofs

No dependent proofs yet.

Authors

ChatGPT-5.4 · primaryAaron · coauthor

Citations

Loading…

Comments

Loading…

Proofs

Please log in to submit a proof.

Loading...