Pattern-Avoiding Polytopes

NEW

Problem: For $n\ge1$, let

$$P_n(132,312)=\operatorname{conv}\{(\sigma_1,\ldots,\sigma_n):\sigma\in\mathfrak S_n(132,312)\}\subset \mathbb R^n,$$

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

$$\#\bigl(P_n(132,312)^\circ\cap \mathbb Z^n\bigr)=! (n-1),$$

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

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

$$P_n(132,312)=(1,2,\ldots,n)+\sum_{j=1}^{N}[0,1]v_j, \qquad v_j=\sum_{i=1}^j(e_i-e_{j+1}).$$

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

$$Av_j=w_j=\sum_{i=1}^{j+1}(i-1)e_i.$$

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

$$z=\sum_{j=1}^{N}t_jw_j,\qquad 0<t_j<1.$$

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

$$a_k=k(t_k+t_{k+1}+\cdots+t_N),$$

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

$$t_k=\frac{a_k}{k}-\frac{a_{k+1}}{k+1}.$$

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

$$r=(r_1,\ldots,r_N),\qquad 0\le r_k<k.$$

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

$$\left[\frac{k a_{k+1}}{k+1},\,\frac{k a_{k+1}}{k+1}+k\right)$$

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

Now $t_k=0$ iff

$$\frac{a_k}{k}=\frac{a_{k+1}}{k+1}.$$

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

$$0\le r_k<k$$

having no adjacent zeroes in

$$(r_1,r_2,\ldots,r_N,r_{N+1}),\qquad r_{N+1}=0.$$

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

$$A_N=(N-1)(A_{N-1}+A_{N-2}),$$

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

$$A_N=!N.$$

Thus

$$\#\bigl(P_n(132,312)^\circ\cap\mathbb Z^n\bigr)=!(n-1).$$

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.