Solution - Quiz 19

$E(x)=x$ 라 주장한다.

$E(1)=1$ 이다. $k$ 이하의 수 $j$에 대해 $E(j)=j$ 라 하자.

$E(0)=0$

$E(k+1)$ 의 한 번의 자리바꾸기 후의 상황을 고려한다.

모든 경우의 수는 $(k+1)!$ 임이 자명하다.

$P(x,y)$를 팀원 $x$명이 서있을 때 한 번의 자리 바꾸기로 $y$ 명이 자신의 자리가 아니고 $x-y$ 명이 자신의 자리를 가게 될 확률이라고 하자.

$$ \begin{aligned} E(k+1)&=1+ \displaystyle \sum_{i=0}^{k+1}P(k+1,i) \cdot E(i) \\ &=1+\sum_{i=0}^{k+1} i \cdot P(k+1, i) \end{aligned} $$

$x$ 명이 자리를 바꾸었는데 그 중 $y$ 명이 자신의 자리가 아닌 경우의 수는 $\dbinom{x}{y} \cdot D_y$ 이다.

$D_y=$ 교란 순열

즉,

$$ \begin{aligned} P(k+1, i)&=\dfrac{\dbinom{k+1}{i} \cdot D_i}{(k+1)!} \\ &=\dfrac{\dfrac{(k+1)!}{i! \cdot (k+1-i)!} \cdot D_i}{(k+1)!} \\ &=\dfrac{D_i}{i! \cdot (k+1-i)!} \end{aligned} $$

$$ \begin{aligned} E(k+1)&=1+\displaystyle \sum_{i=0}^{k+1}\dfrac{i \cdot D_i}{i! \cdot (k+1-i)!} \end{aligned} $$

여기서 수식 전개에 실패했다. $E(k+1)=k+1$ 임을 보이면 귀납이 성립되어 $E(X)=X$ 가 보여진다.

하지만 이를 코드로 나타내면 $X=31$ 에서는 명백히 원하는 결과를 얻는다.

이것으로 해설을 일단 대신한다.

void solve() {  
   vector<double> F(32, 1), D(32);  
   for (int i = 2; i <= 31; i++) F[i] = F[i - 1] * i;  
   D[1] = 0, D[2] = 1;  
   for (int i = 3; i <= 31; i++) D[i] = (i - 1) * (D[i - 2] + D[i - 1]);  
   double ans = 1;  
   for (int i = 0; i <= 31; i++) ans += i * D[i] / (F[i] * F[31 - i]);  
   cout << ans;  
}

output: 31