집합 $\{1, \dots, n \}$의 순열중에서 정확하게 $k$개의 부동점을 갖는 것들의 개수를 $P_n(k)$라고 하자. $\sum_{k=0}^n k P_n(k) = n!$ 임을 증명하여라.
태그 보관물: 순열
1998 제11회 한국수학올림피아드 최종시험 6번문제
자연수 $n$에 대하여 다음의 두 조건을 만족시키는 전단사(일대일 대응) 함수 $f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ 전체의 집합을 $F_n$이라고 하자.
(1) $f(k)\le k+1$ ($k=1,2,\ldots,n-1$),
(2) $f(k)\neq k$ ($k=2,\ldots,n$).
$F_n$의 원소 $f$를 임의로 뽑을 때 $f(1)\neq 1$일 확률을 구하여라.
2013 캐나다수학올림피아드 2번문제
$a_1,a_2,\ldots,a_n$을 $1,2,\ldots,n$의 순열이라 하자. 총 $n+1$개의 수 $0$, $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, $\ldots$, $a_1+a_2+\cdots+a_n$을 각 $n+1$으로 나눴을때 나머지가 모두 서로 다르게 하는 양의 정수 $n$을 모두 구하여라.
(2013년 3월 27일, 출처)
2013 제26회 한국수학올림피아드 최종시험 6번문제
임의의 일대일대응 $f :\{1, 2, \ldots, n\}\to\{1, 2,\ldots, n\}$ ($n$은 양의 정수)에 대하여, 네 집합 $A$, $B$, $C$, $D$를 다음과 같이 정의하자. \[ A=\{i \mid i \gt f(i)\}\]\[ B=\{(i,j)\mid i\lt j \le f(j)\lt f(i)\text{ 또는 } f(j)\lt f(i) \lt i\lt j\}\]\[ C=\{(i,j)\mid i\lt j \le f(i)\lt f(j)\text{ 또는 } f(i)\lt f(j) \lt i\lt j\}\]\[ D=\{ (i,j)\mid i\lt j \text{이고 } f(i)\gt f(j)\}\] 다음 등식이 성립함을 보여라. (단, $|X|$는 집합 $X$의 원소의 개수이다.)\[ |A|+2|B|+|C|=|D|\]
(2013년 3월 24일, 4시간 30분)
2012 제73회 William Lowell Putnam 수학경시대회 B6
$p\equiv 2\pmod 3$인 홀수인 소수 $p$가 주어져있다. 정수를 $p$로 나눈 나머지들에 대해 $\pi(x)\equiv x^3\pmod p$가 되게 순열 $\pi$를 정의하였다. 이때 $\pi$가 우순열(even permuatation)일 필요충분조건이 $p\equiv 3\pmod 4$인 것임을 증명하라.
(2012년 12월 1일)
1999 제12회 한국수학올림피아드 최종시험 5번문제
$1$, $2$, $3$, $4$, $5$, $6$의 순열 중에서 서로 다른 두 항씩 자리를 바꾸는 조작을 $4$회 시행하여 $123456$을 복원할 수 있으며 $3$회 이하의 시행으로는 복원이 불가능한 순열 $a_1a_2a_3a_4a_5a_6$을 생각하자. 이러한 순열의 개수를 구하여라.
(1999년 4월 18일, 출처4시간 30분)