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

E(1)=1E(1)=1 이다. kk 이하의 수 jj에 대해 E(j)=jE(j)=j 라 하자.

E(0)=0E(0)=0

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

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

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

E(k+1)=1+∑i=0k+1P(k+1,i)⋅E(i)=1+∑i=0k+1i⋅P(k+1,i) \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}

xx 명이 자리를 바꾸었는데 그 중 yy 명이 자신의 자리가 아닌 경우의 수는 (xy)⋅Dy\dbinom{x}{y} \cdot D_y 이다.

Dy=D_y= 교란 순열

즉,

P(k+1,i)=(k+1i)⋅Di(k+1)!=(k+1)!i!⋅(k+1−i)!⋅Di(k+1)!=Dii!⋅(k+1−i)! \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}
E(k+1)=1+∑i=0k+1i⋅Dii!⋅(k+1−i)! \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+1E(k+1)=k+1 임을 보이면 귀납이 성립되어 E(X)=XE(X)=X 가 보여진다.

하지만 이를 코드로 나타내면 X=31X=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

Tags:

Categories:

Updated:

Comments

You may also enjoy