좀 야매로 때려맞췄습니다;;
머리가 복잡해져서 중간에 실수한게 있을수도 있구.. 또 아이디어 자체가 틀린것일수도 있지만..

올려 봅니다.



Define: Discrete Function Eo[n,k]

=> n명에서 k명을 방법 1로 뽑을 경우의 평균 시행 횟수

Define: Discrete Function En[n,k]

=> n명에서 k명을 방법 2로 뽑을 경우의 평균 시행 횟수


Eo[n,k] =
먼저 각각의 경우의 확률을 보면

　　　　　┳ 0명 뽑힐 확률 2*1/2^n
　　　　　┣ 1명 뽑힐 확률 2*C(n,1)/2^n
　　　　　┣ 2명 뽑힐 확률 2*C(n,2)/2^n
　　　　　：
　　　　　┣ k명 뽑힐 확률 2*C(n,k)/2^n
　　　　　：
　　　　　┗ [n/2] 명 뽑힐 확률 [x]는 x보다 작은 최대 정수

C(n,k) = (k) = n!　　　을 의미함
　　 　　(n)　━━━━
　　　　　　　k!(n-k)!

이는 Geomatric이므로 각각의 역수가 평균이 된다. 즉

Eo[n,k] = 2^n/2*C(n,k) = 2^(n-1) / C(n,k)　　　　　　　{Eo함수}

한편 En[n,k]는 1~k까지 뽑히면 뽑는 상황의 상태가 변한다. 다시 보면


En[n,k]　 ┳ 0명 뽑힘 ━ 상태유지
　　　　　┣ 1명 뽑힘 ━ En[n-1,k-1]
　　　　　┣ 2명 뽑힘 ━ En[n-2,k-2]
　　　　　：
　　　　　┣ k명 뽑힘 ━ En[n-k,0]
　　　　　：
　　　　　┗ 상태유지

가 된다. 즉 상태가 변화할 확률은 1명 뽑힐 확률 + 2명 ... k명 뽑힐 확률로 다음과 같다.

k　　　　　　　　　△
∑　C(n,i)/ 2^(n-1) = Sump(n,k)　　　　　(- Sum of Probabilities)
i=1

이 상태가 되었을 때 앞으로의 평균 시행 횟수를 Ea[n,t]라고 하면 En[n,k] 는 다음과 같이 쓸 수 있다.

En[n,k] = 1/Sump(n,k) + Ea[n,t] - 1　　　　　　　{1}

이것은 Geomatric에서 일정 수 Ea를 더한 만큼 가게 되며 Ea값이 n, k에 의해서만
바뀌기 때문게 가능한 가정이다.

12줄 위의 그림에서 Ea를 구해 보면, 평균은 각각의 확률 * 각각의 시행 평균 / 전체 확률 이 되므로

　　　　　k
　　　　　∑　(En[n-i,k-i] + 1) * C(n,i)/ 2^(n-1)
　　　　　i=1
Ea[n,k] = ━━━━━━━━━━━━━━━━━━━━　　　　　　{2}
　　　　　　　　　Sump(n,k)

가 된다. +1항은 k 이하의 사람이 뽑혀 En으로 내려갈 때 뽑힐 때 셋 횟수를 더한 값이다.
위 식에서 2^(n-1) 항은 소거되고, 새 함수를 정의하여

k　　　　　△
∑　C(n,i) = Sumc(n,k)
i=1

로 한 후, Ea를 {1}식에 대입하여 정리하면

　　　　　┏ k　　　　　　　　　　　　　　　┓
　　　　　┃ ∑　(En[n-i,k-i] + 1) * C(n,i) ┃ + 2^(n-1) - Sumc(n,k)
　　　　　┗ i=1　　　　　　　　　　　　　　┛
En[n,k] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　　　　　　　　　Sumc(n,k)


　　　　　┏ k　　　　　　　　　　　　┓
　　　　　┃ ∑　En[n-i,k-i] * C(n,i) ┃ + 2^(n-1)
　　　　　┗ i=1　　　　　　　　　　　┛
　　　　= ━━━━━━━━━━━━━━━━━━━━　　　　　　{En함수}
　　　　　　　　　Sumc(n,k)

가 된다.

En의 initial condition 을 살펴보면, 정리 전 식에서 i = k일 때 평균(En[n-i,k-i] + 1)이 1이 되므로

En[n,0] = 0　　　　　(n=자연수)

이 된다.

------------------------------------------------------------------------------------------------

Problem 1-1:

답 : Eo[10,3] = 512/120

Problem 1-2:

답 : En[10,3] ≒ 7.54794 (풀이는 맨 아래에)

Problem 1-3:

En'[10,4] ┳ 0명 뽑힘 ━ 상태유지
　　　　　┣ 1명 뽑힘 ━ En[9,2]
　　　　　┣ 2명 뽑힘 ━ En[8,1]
　　　　　┣ 3명 뽑힘 ━ En[7,0]
　　　　　┣ 4명 뽑힘 ━ En[4,1]
　　　　　：
　　　　　┗ 상태유지

상태변화는 1~4명 뽑혔을 때까지에서 일어나며 변화 확률은 Sump(10,4)가 된다. 위와 같은 방법으로
Ea'를 구하면

　　　　　　┏ 3　　　　　　　　　　　　　　　　　　　 ┓
　　　　　　┃ ∑　(En[10-i,3-i] + 1) * C(10,i)/ 2^(9) ┃ + (En[4,1] + 1) * C(10,4)/ 2^(9)
　　　　　　┗ i=1　　　　　　　　　　　　　　　　　　 ┛
Ea'[10,4] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　　　　　　　　　Sump(10,4)

　　　　　　┏ 3　　　　　　　　　　　　　　　　┓
　　　　　　┃ ∑　(En[10-i,3-i] + 1) * C(10,i) ┃ + (En[4,1] + 1) * C(10,4)
　　　　　　┗ i=1　　　　　　　　　　　　　　　┛
　　　　　= ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　　　　　　　　　Sumc(10,4)

가 되며 이를 {1}식에 ' notation사용하여 대입하면

　　　　　　┏ 3　　　　　　　　　　　　　　　　┓
　　　　　　┃ ∑　(En[10-i,3-i] + 1) * C(10,i) ┃ + (En[4,1] + 1)*C(10,4) + 2^9 - Sumc(10,4)
　　　　　　┗ i=1　　　　　　　　　　　　　　　┛
En'[10,4] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　　　　　　　　　Sumc(10,4)

　　　　　　┏ 3　　　　　　　　　　　　　┓
　　　　　　┃ ∑　En[10-i,3-i] * C(10,i) ┃ + En[4,1]*C(10,4) + 2^9
　　　　　　┗ i=1　　　　　　　　　　　　┛
　　　　　= ━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　　　　　　　　　Sumc(10,4)

가 된다.

답 : En'[10,4] ≒ 4.52179

Problem 2-1:

답: En[n,3] = 얼마 안되므로 재귀로 표현할 수 있다.

Problem 2-2:

답: En[n,k] = 지금 방법으로는 표현 불가, n,k를 알면 알고리즘으로 사용 가능


--------------------------------------------------------------------------------------------------

Algorithm for Calculating En[n,k]

　　　　　┏ k　　　　　　　　　　　　┓
　　　　　┃ ∑　En[n-i,k-i] * C(n,i) ┃ + 2^(n-1)
　　　　　┗ i=1　　　　　　　　　　　┛
En[n,k] = ━━━━━━━━━━━━━━━━━━━━
　　　　　　　　　Sumc(n,k)


En[n,0] = 0

이며 이를 C 함수로 나타내면 다음과 같다.

double En(int n, int k) {
int i;
double s1, s2;

/* 이 부분은 n, k가 초기에 정상적으로 입력되었다고 가정할 때 주석처리가 가능하다
if(n<2*k+1 || k<0 || n<3 ) {
cout << "잘못된 숫자 입력n";
return 0;
}
*/

if(k==0)
return 0;
else {
s1 = expi(2,n-1); // (exponent for integer - expi(int a, int b) 는 double a^b를 리턴)
s2 = 0;
for(i=1;i<=k;++i) {
s1 += En(n-i,k-i)*C(n,i); // C(int a,int b) 는 int a!/[ b! * (a-b)! ]를 리턴
s2 += C(n,i);
}
}
return s1/s2;
}

double expi(int a, int b) {
int i;
double s = a;
for(i=1;i<b;++i)
s *= a;
return s;
}

int C(int a, int b) {
int i;
int s1, s2;

/* 이 부분은 a, b가 초기에 정상적으로 입력되었다고 가정할 때 주석처리가 가능하다
if(a<b) {
cout << "잘못된 숫자 입력n";
return 0;
}
*/

s1 = 1;
s2 = 1;
for(i=0;i<b;++i) {
s1 *= a-i;
s2 *= i+1;
}
return s1/s2;
}

-----------------------------------------------------------------------

답을 위해 작성한 main 함수

#include<iostream>

using namespace std;

double En(int n, int k);
double expi(int a, int b);
int C(int a, int b);

void main()
{
cout << En(10,3) << endl;
cout << ( En(9,2)*C(10,1) + En(8,1)*C(10,2) + En(4,1)*C(10,4) + expi(2,9) )/( C(10,1)+C(10,2)+C(10,3)+C(10,4) ) << endl;
}

--------------------------------------------------------------------------

결과창

7.54794
4.52179
Press any key to continue


........................................................................................
■ 박기현: c코드의 En함수에서 주석처리된 if 구문에서 n<3은 필요도 없고 En[2,0]때문에 맞지도 않는군요.. 수정해야겠습니다. (pl2115@hotmail.com) -[10/13-01:38]-
........................................................................................
■ 송홍엽: 고생했다... 정답을 검토할동안 조금만 기다려다오.. (hy.song@coding.yonsei.ac.kr) -[10/14-20:46]-