Skip to main content
added 1728 characters in body
Source Link

This is not an answer, but a reformulation. Consider all permutations $\sigma$ of the numbers $\{1,2,\dots,2n\}$ such that $$\sigma(1)>\sigma(2),\,\sigma(3)>\sigma(4),\dots,\sigma(2n-1)>\sigma(2n)$$ and also $$\sigma(1)>\sigma(3)>\dots>\sigma(2n-1).$$ Note that these can be identified with perfect matchings on $\{1,2,\dots,2n\}$ ( each $\sigma(2i-1)$ is paired with $\sigma(2i)$). Write these in lexicographic order. For instance, when $2n=6$, there are $15$ such permutations and writing them from largest to smallest gives $654321$, $654231$, $654132$, $645321$, $\dots$, $615243$. Then I think your observation would follow from the statement ``Any two adjacent permutations have distinct parity".

In fact, the pfaffian can be defined as $$\sum_{\sigma}\operatorname{sgn}(\sigma)a_{\sigma(2i-1),\sigma(2i)},$$ summed over such sigma. In your case, this sum will be a sum of $\pm\alpha^{n_{\sigma}}$ for some integers $n_{\sigma}$, and I think it is clear from your condition on $s_i$ that $n_{\sigma}>n_\tau$ if and only if $\sigma>\tau$. So if the statement above holds the signs alternate.

I suggested above that any two adjacent permutations differ by a transposition, but that is certainly false as can be seen from the example 654132,645321 above. But I did check that the claim holds for $2n=6$.

Updated after seeing SiOn's answer to their own question:

The claim above can be proved by induction on $n$. Sketch of proof: Let $\sigma>\tau$ be two lexicographically adjacent matchings. We always have $\sigma(1)=\tau(1)=2n$. If $\sigma(2)=\tau(2)=j$, then the remaining parts of $\sigma$ and $\tau$ are permutations $\sigma'$, $\tau'$ of $\{1,2,\dots,\hat j,\dots,2n-1\}$. Identifying that set with $\{1,2,\dots,2n-2\}$ it follows inductively that $\operatorname{sgn}(\sigma')=-\operatorname{sgn}(\tau')$ and hence $\operatorname{sgn}(\sigma)=-\operatorname{sgn}(\tau)$.

If $\sigma(2)\neq \tau(2)$ we can write $\sigma(2)=j$ and $\tau(2)=j-1$. Recall that the parity of perfect matchings is the crossing number. That is, if we draw $\{1,2,\dots,n\}$ as dots on a line and then connect $\sigma(2j-1)$ and $\sigma(2j)$ by arcs in the upper half-plane, then $\operatorname{sgn}(\sigma)$ is the parity of the number of crossings. In the situation at hand, $\sigma'$ is the lexicographically minimal matching on $\{1,2,\dots,\hat j,\dots,2n-1\}$, that is, $1$ is paired with $2n-1$, $2$ with $2n-2$ and so on. This matching has no crossings. The arc from $2n$ to $j$ crosses the arcs starting at $1,\dots,j-1$ and hence $\operatorname{sgn}(\sigma)=(-1)^{j+1}$. Likewise, $\tau'$ is the maximal matching on $\{1,2,\dots,\widehat {j-1},\dots,2n-1\}$, which pairs $1$ with $2$, $3$ with $4$ and so on. Again, $\operatorname{sgn}(\tau')=1$. If $j$ is even, the arc from $2n$ to $j-1$ can be drawn without crossing any other arcs, but if $j$ is odd it must cross the arc from $j-2$ to $j$. Hence, $\operatorname{sgn}(\tau)=(-1)^j$ and we see that also in this case $\operatorname{sgn}(\sigma)=-\operatorname{sgn}(\tau)$.

This is not an answer, but a reformulation. Consider all permutations $\sigma$ of the numbers $\{1,2,\dots,2n\}$ such that $$\sigma(1)>\sigma(2),\,\sigma(3)>\sigma(4),\dots,\sigma(2n-1)>\sigma(2n)$$ and also $$\sigma(1)>\sigma(3)>\dots>\sigma(2n-1).$$ Note that these can be identified with perfect matchings on $\{1,2,\dots,2n\}$ ( each $\sigma(2i-1)$ is paired with $\sigma(2i)$). Write these in lexicographic order. For instance, when $2n=6$, there are $15$ such permutations and writing them from largest to smallest gives $654321$, $654231$, $654132$, $645321$, $\dots$, $615243$. Then I think your observation would follow from the statement ``Any two adjacent permutations have distinct parity".

In fact, the pfaffian can be defined as $$\sum_{\sigma}\operatorname{sgn}(\sigma)a_{\sigma(2i-1),\sigma(2i)},$$ summed over such sigma. In your case, this sum will be a sum of $\pm\alpha^{n_{\sigma}}$ for some integers $n_{\sigma}$, and I think it is clear from your condition on $s_i$ that $n_{\sigma}>n_\tau$ if and only if $\sigma>\tau$. So if the statement above holds the signs alternate.

I suggested above that any two adjacent permutations differ by a transposition, but that is certainly false as can be seen from the example 654132,645321 above. But I did check that the claim holds for $2n=6$.

This is not an answer, but a reformulation. Consider all permutations $\sigma$ of the numbers $\{1,2,\dots,2n\}$ such that $$\sigma(1)>\sigma(2),\,\sigma(3)>\sigma(4),\dots,\sigma(2n-1)>\sigma(2n)$$ and also $$\sigma(1)>\sigma(3)>\dots>\sigma(2n-1).$$ Note that these can be identified with perfect matchings on $\{1,2,\dots,2n\}$ ( each $\sigma(2i-1)$ is paired with $\sigma(2i)$). Write these in lexicographic order. For instance, when $2n=6$, there are $15$ such permutations and writing them from largest to smallest gives $654321$, $654231$, $654132$, $645321$, $\dots$, $615243$. Then I think your observation would follow from the statement ``Any two adjacent permutations have distinct parity".

In fact, the pfaffian can be defined as $$\sum_{\sigma}\operatorname{sgn}(\sigma)a_{\sigma(2i-1),\sigma(2i)},$$ summed over such sigma. In your case, this sum will be a sum of $\pm\alpha^{n_{\sigma}}$ for some integers $n_{\sigma}$, and I think it is clear from your condition on $s_i$ that $n_{\sigma}>n_\tau$ if and only if $\sigma>\tau$. So if the statement above holds the signs alternate.

I suggested above that any two adjacent permutations differ by a transposition, but that is certainly false as can be seen from the example 654132,645321 above. But I did check that the claim holds for $2n=6$.

Updated after seeing SiOn's answer to their own question:

The claim above can be proved by induction on $n$. Sketch of proof: Let $\sigma>\tau$ be two lexicographically adjacent matchings. We always have $\sigma(1)=\tau(1)=2n$. If $\sigma(2)=\tau(2)=j$, then the remaining parts of $\sigma$ and $\tau$ are permutations $\sigma'$, $\tau'$ of $\{1,2,\dots,\hat j,\dots,2n-1\}$. Identifying that set with $\{1,2,\dots,2n-2\}$ it follows inductively that $\operatorname{sgn}(\sigma')=-\operatorname{sgn}(\tau')$ and hence $\operatorname{sgn}(\sigma)=-\operatorname{sgn}(\tau)$.

If $\sigma(2)\neq \tau(2)$ we can write $\sigma(2)=j$ and $\tau(2)=j-1$. Recall that the parity of perfect matchings is the crossing number. That is, if we draw $\{1,2,\dots,n\}$ as dots on a line and then connect $\sigma(2j-1)$ and $\sigma(2j)$ by arcs in the upper half-plane, then $\operatorname{sgn}(\sigma)$ is the parity of the number of crossings. In the situation at hand, $\sigma'$ is the lexicographically minimal matching on $\{1,2,\dots,\hat j,\dots,2n-1\}$, that is, $1$ is paired with $2n-1$, $2$ with $2n-2$ and so on. This matching has no crossings. The arc from $2n$ to $j$ crosses the arcs starting at $1,\dots,j-1$ and hence $\operatorname{sgn}(\sigma)=(-1)^{j+1}$. Likewise, $\tau'$ is the maximal matching on $\{1,2,\dots,\widehat {j-1},\dots,2n-1\}$, which pairs $1$ with $2$, $3$ with $4$ and so on. Again, $\operatorname{sgn}(\tau')=1$. If $j$ is even, the arc from $2n$ to $j-1$ can be drawn without crossing any other arcs, but if $j$ is odd it must cross the arc from $j-2$ to $j$. Hence, $\operatorname{sgn}(\tau)=(-1)^j$ and we see that also in this case $\operatorname{sgn}(\sigma)=-\operatorname{sgn}(\tau)$.

Source Link

This is not an answer, but a reformulation. Consider all permutations $\sigma$ of the numbers $\{1,2,\dots,2n\}$ such that $$\sigma(1)>\sigma(2),\,\sigma(3)>\sigma(4),\dots,\sigma(2n-1)>\sigma(2n)$$ and also $$\sigma(1)>\sigma(3)>\dots>\sigma(2n-1).$$ Note that these can be identified with perfect matchings on $\{1,2,\dots,2n\}$ ( each $\sigma(2i-1)$ is paired with $\sigma(2i)$). Write these in lexicographic order. For instance, when $2n=6$, there are $15$ such permutations and writing them from largest to smallest gives $654321$, $654231$, $654132$, $645321$, $\dots$, $615243$. Then I think your observation would follow from the statement ``Any two adjacent permutations have distinct parity".

In fact, the pfaffian can be defined as $$\sum_{\sigma}\operatorname{sgn}(\sigma)a_{\sigma(2i-1),\sigma(2i)},$$ summed over such sigma. In your case, this sum will be a sum of $\pm\alpha^{n_{\sigma}}$ for some integers $n_{\sigma}$, and I think it is clear from your condition on $s_i$ that $n_{\sigma}>n_\tau$ if and only if $\sigma>\tau$. So if the statement above holds the signs alternate.

I suggested above that any two adjacent permutations differ by a transposition, but that is certainly false as can be seen from the example 654132,645321 above. But I did check that the claim holds for $2n=6$.