동전을 n번 던졌을 때, 연속으로 앞면이 나타날 경우의 수는?

이런 경우의 수를 계산하는 것이 쉽지는 않습니다.  어떻게 생각을 해야 하는지가 중요하죠.  동전을 n번 던졌을 때의 경우의 총 수는 \(2^n\)입니다.  연속으로 앞면이 나타날 경우의 수는 총 경우의 수에서 연속으로 앞면이 나타나지 않을 경우의 수를 빼면 됩니다.  그러면 연속으로 앞면이 나타나지 않는 경우의 수를 어떻게 계산할까요?

 

동전 던지기

 

수열을 만드는 과정을 생각해보죠.

동전의 뒷면을 0으로 앞면을 1로 가정을 해보도록 합니다.  4번 동전을 던진다면, 1이 연속으로 나타나는 경우의 수는

0011, 0110, 0111, 1011, 1100, 1101, 1110, 1111

으로 총 8가지입니다.

컴퓨터로 모든 경우의 수에 대해서 연속 1이 나오는지 카운팅하면 되겠지만, 수학적으로는 어떻게 풀까요?

 

수열을 만들때, 1이 연속으로 나타나지 않으면서 마지막이 0으로 끝나는 수열을 생각해보도록 할께요.  우리는 1개 적은 수열에서는 0을 붙이고, 2개 적은 수열에서는 10을 붙이도록 합니다.  수열은 항상 0으로 끝나므로 이 수열은 1이 연속으로 나타나지 않는 수열이죠.  또한 그러한 모든 경우를 포함하고 있습니다.  2x1 직사각형 나무로 2xn 면적을 채우는 방법과 동일합니다.

 

수열길이	경우의 수	수열들
1	1	0
2	2	00 10
3	3	000 100 010
4	5	0000 1000 0100 0010 1010
5	8	00000 10000 01000 00100 10100 00010 10010 01010
6	13	000000 100000 010000 ...
7	21	0000000 1000000 0100000 ...
8	34	...
9	55	...

 

규칙성을 찾으셨나요?  이 수열에서 경우의 수는 피보나치 수열과 같습니다.  

우리가 필요로 하는 수열은 뒤에 0이 제거된 수열들입니다.  그러면 \(2^n\)에서 해당 경우의 수를 빼면 되죠.  F(1)=1, F(2)=2, F(n)=F(n-1)+F(n-2) 로 정의된 수열을 생각해본다면,

 

동전을 n번 던져서 연속으로 앞면이 나오는 경우의 수는 다음과 같이 표현할 수 있습니다.

\[ 2^n - F(n+1) \]

 

그래서 n=1 부터 나열해보면,

0, 1, 3, 8, 19, 43, ...

형태가 됩니다.

 

피보나치 수열은 일반항을 구할 수 있으니까,

\[ 2^n - \frac{1}{\sqrt{5}} ( \phi^n - \phi^{-n} ) \]

으로 놓을 수도 있습니다.

 

동전의 앞면이 연속으로 3번 이상 나타나는 경우는  트리보나치(tribonacci)로 계산할 수 있습니다.