Permutation $\pi : [n] \to [n]$에 대해 Displacement를 $D(\pi) = \sum_{i=1}^{n} \lvert i - \pi (i) \rvert$로 정의한다. 주어진 양수 $k$에 대해, $D(\pi) = 2k$를 만족하는 짝순열의 개수를 $E_{k}$, 홀순열의 개수를 $O_{k}$라 두면 $E_{k} - O_{k} = (-1)^{k}\binom{n-1}{k}$임을 보여라.
Official Solution
(짝순열) - (홀순열) 꼴로 표현되는 counting 문제에 적용될 수 있는 굉장히 강한 도구라고 생각한다.
$a_{ij} = x^{\lvert i - j \rvert}$라고 두고, 행렬 $A = (a_{ij})$를 생각하자. 이 때 $\displaystyle\det A = \sum_{\pi} \mathrm{sgn}(\pi) a_{1,\pi(1)} \cdots a_{n,\pi(n)} = \sum_{\pi} \mathrm{sgn}(\pi)x^{D(\pi)}$로 표현된다. 이것만으로 문제의 80%는 풀린 셈이다.
문제가 너무 작위적인 건지, 아니면 이 툴이 진짜 강력한 건지는 잘 모르겠다. 근데 조합론을 더 보려면 알아둘 필요는 있는 것 같다.
이제 행렬 $A$의 determinant를 아무 방법으로 구하면 된다. 편의상 $A_{n}$이라고 부르자. Official solution에서는 $(n-1)$번째 row에 $x$를 곱해서 $n$번째 row에서 뺐더니 $(n,n)$에 $1 - x^2$, 나머지 $(n-1)\times(n-1)$ matrix에 $A_{n-1}$이 나왔다고 한다. 따라서 귀납적으로 $\det A_{n} = (1-x^{2})^{n-1}$이다. 그래서 $x^{2k}$의 계수는 $(-1)^{k}\binom{n-1}{k}$가 된다. 끝. $\square$