KAIST POW 2020-09 "Displacement of Permutations"

math-ps ― [ math , math-ps , combinatorics ]

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\)

Written on June 5, 2020