Pattern-Avoiding Polytopes

NEW

Problem: For $n\ge1$, let

where $\mathfrak S_n(132,312)$ denotes permutations avoiding both patterns $132$ and $312$. The paper’s question is subjective as written (“nice combinatorial proof”), so I formalize it as: give a combinatorial proof, preferably bijective, that

the number of derangements of $[n-1]$. Here $P^\circ$ is relative interior.

Result: Let $N=n-1$. Davis--Sagan’s parallelotope description gives

Apply the unimodular map $A$ with $A_{ij}=-1$ for $i\le j$ and $0$ otherwise. Then

Thus interior lattice points of $P_n(132,312)$ are in bijection with lattice points

Write $z=(0,a_1,\ldots,a_N)$. Since the $(k+1)$-st coordinate is

with $a_{N+1}=0$, we have

For the half-open parallelepiped $0\le t_k<1$, reducing $a_k$ modulo $k$ gives a bijection with inversion sequences

Indeed, given $a_{k+1}$, the interval

contains exactly one integer in each residue class modulo $k$.

Now $t_k=0$ iff

Because $\gcd(k,k+1)=1$, this happens iff $r_k=r_{k+1}=0$, where we set $r_{N+1}=0$. Therefore interior lattice points are bijective with inversion sequences

having no adjacent zeroes in

Let $A_N$ be the number of such sequences. Then $A_0=1$, $A_1=0$, and for $N\ge2$:

• choose $r_N\in\{1,\ldots,N-1\}$;
• either $(r_1,\ldots,r_{N-1})$ is a valid sequence of length $N-1$, or $r_{N-1}=0$ and $(r_1,\ldots,r_{N-2})$ is valid of length $N-2$.

Hence

with $A_0=1,A_1=0$. This is the standard derangement recurrence, so

Thus

Moreover, the recurrence gives an explicit recursive bijection to derangements: if the valid sequence ends in $r_N=i\neq0$, then either append $N$ into the cycle of $i$ of a derangement of $[N-1]$, or, if the previous entry is $0$, add the transposition $(i\,N)$ to a derangement of the remaining $N-2$ elements. This matches exactly the usual derangement recurrence.

Citation: Davis--Sagan, Pattern-Avoiding Polytopes, arXiv:1609.01782, for the definition of $P_n(132,312)$, its parallelotope description, and the original open question. The residue/inversion-sequence bijective proof above supplies the requested combinatorial explanation.