다음은 고등학교 수준에서 다뤄졌을 법한 전형적인 확률· 조합 문제이다.

N명의 사람이 각자 모자를 쓰고 왔는데 이 모자를 다 벗어서 모아놓았다. 잠시 뒤 이 모자를 무작위로 사람들이 찾아 쓸 때, 모든 사람이 한 명도 예외 없이 남의 모자를 쓰게 될 확률은?


수가 커질수록 소수를 발견하기 어려워지는 것만큼이나 저 확률은 0으로 수렴이라도 하는 걸까? 답부터 말하자면 그렇지 않다. N이 커질수록 그 확률은 1/e 에 수렴한다.
즉, 대략 37% 정도 된다는 뜻이고 이는 3지선다 문제를 깬또-_-로 맞힐 확률과 고만고만함을 의미한다. (깬또는 도대체 어느 나라 어원의 말일까? 순우리말이라면 흠좀무) 하필 자연대수와 관계가 있는 확률로 수렴한다는 것도 흥미로운 점.

신기하지 않은가? 이 정도면 여러분이 감으로 예상한 확률보다 높은 걸까 낮은 걸까? 수학이 좋은 점은, 인간의 감만으로는 아리까리한 문제에 대해서 명확하게 이렇게 될 수밖에 없다는 답을 제시한다는 것이다. 영적인 안목만 없을 뿐이지 추상적인 세계에서는 성경만큼이나 100% 절대무오한 진리를 담고 있는 학문이 바로 수학이다.

N개의 모자를 늘어놓을 수 있는 모든 가짓수는 잘 알다시피 N! (팩토리얼)이다.
N=2인 경우라면 1 2가 2 1로 뒤바뀌는 경우밖에 없으므로 1/2 = 50%
N=3이면 6가지 조합 중에 2 3 1, 3 1 2가 존재하므로 2/6 ≒ 33.3%
N=4는 잘 세어 보면 9가지 경우가 존재하여 9/24 = 37.5%
N=5일 때는 44가지 경우가 있다. 44/120 ≒ 36.7%
그리고 쭉쭉쭉...;;

그런데 이 가짓수에서 재미있는 패턴이 발견된다.
가짓수를 나타내는 함수를 f(x)라고 정의하면, 일단 f(x)의 값은 x-1의 배수임이 반드시 보장된다.
f(5)는 4의 배수인 11, f(4)는 3의 배수인 9인 식이다.
실제로 가짓수를 세어 보면, 왜 그렇게 되는지 알 수 있다.

이 f(x)를 구하는 방법은 점화식으로 의외로 간단하게 유도된다.
패턴을 잘 관찰해 보면 f(1)=0, f(2)=1 이후로 f(x) = (x-1)*(f(x-1)+f(x-2))가 된다.

f(4) = 3*(1+2) = 9
f(5) = 4*(2+9) = 44
f(6) = 5*(9+44) = 265

숫자의 증가의 폭이 팩토리얼과 동급으로 폭발적인 건 마찬가지이기 때문에, 그 비율의 극한이 0이나 무한대가 아니라 상수로 나온다.
f(x) = f(x-1)+f(x-2)인 피보나치 수열 점화식에다가 (x-1)을 곱한 것밖에 없으나, 점화식의 특성상 그 여파는 쌓이고 쌓이면서 훨씬 더 커진다. 피보나치 수열의 일반항은 2^n 같은 지수함수급인 반면 저건 팩토리얼급..;; 팩토리얼 자체가 f(x) = x*f(x-1)로, 점화식에 덧셈도 모자라서 곱셈이 등장하니까 말이다.

본인은 1/e라고 하면 x^x 함수를 최소로 만드는 값이기도 하다는 것을 예전부터 알고 있었다.
x^x는 a^x 같은 지수함수는 말할 것도 없고 심지어 팩토리얼보다도 더욱 폭발적으로 증가하는 괴랄한 함수이다.
이 함수는 양변에 로그를 씌워서 미분하는데, 도함수는 x^x * (ln x + 1)이 된다.

양수 x에 대해서 x^x 자체는 0이 결코 될 수가 없다(x가 0에 가까워져도 함수값은 1에 수렴). 하지만 x에다 1/e를 집어넣으면 ln x + 1이  ln 1 - ln e + 1 = 0-1+1 = 0이 된다. 고로 도함수의 값은 0. 이때가 최소이며, 그 최소값은 e^(-1/e)에 해당하는 약 0.69 정도.
e 자체뿐만이 아니라 e의 역수도 이런 의미를 지닌다는 걸 알 수 있다. 아래 그림을 참고하라.

사용자 삽입 이미지

대표적인 공돌이 유머인 미분 귀신 적분 귀신에 잘 묘사되어 있듯, 다항함수는 유한 번 미분하면 0이 되어 버린다. 그러나 초월함수들은 미분을 거듭해도 전혀 줄어들지 않으며 오히려 쓸데없는 계수들이 덧붙거나(지수함수), 형태만 바꾸면서 뱅글뱅글 순환한다(삼각함수).

그런데 그 정점에 있는 것이 바로 e^x이다. 미분해도 적분해도 형태가 전혀 변하지 않는다. ^^;;;
이 녀석은 테일러 급수로 다항식 전개를 해 보면.. 진짜 그렇게 될 수밖에 없는 형태임을 알 수 있다.
테일러 급수 자체가, 특정 지점에서 주어진 함수와 함수값과 n차까지 도함수가 일치하는 다항함수를 구하는 것이니 원..

1 + x + x^2/2 + x^3/6 + x^4/4! + x^5/5! ....

이게 끝없이 반복되니까 미분하면 왼쪽으로 shift, 적분하면 오른쪽으로 shift.. -_-;;
x에다가 1을 집어넣으면 결국 자연대수 e는 1부터 시작해 팩토리얼들의 역수의 합으로 2.71828...로 시작하는 그 값이 자연스럽게 유도된다. 수학에서 원주율 다음으로 유명하고 중요한 상수이다.
2.718281828 ..1828이 잠시 반복되는 덕분에 파이보다 외우기 쉽다.

우리는 학교 수학 시간에 자연상수에 대해서 (1+ 1/n)^n의 n 무한대 극한값이라고 처음으로 배운다. 이게 e로 수렴한다는 것도 무척 재미있는 사실이긴 하나, 저 식은 수렴 속도가 매우 느려서 비실용적이다. n=1000이 돼도 아직 2.716이고 2.718에도 도달 안 해 있다.
그 반면 팩토리얼 역수의 합은 직관적이고 수렴 속도도 꽤 빠른 편이어서 좋다. 6!까지 갈 때 이미 2.718에 도달하고 9!에서 벌써 소숫점 여섯째 자리까지 일치하기 시작한다. 굿..;;

범위가 0부터 1까지인 n차원 공간상의 점 P(a1, a2, a3, ... a_n)이 있을 때, 0<a1<a2<a3<...<a_n을 만족하는 영역이 차지하는 부피(?) 내지 product는 어떻게 될까? 1/n!이다. 2차원일 때는 한 변의 길이가 1인 삼각형의 넓이가 되므로 1/2, 3차원일 때는 삼각뿔의 부피가 되므로 거기에다가 1/3을 또 곱하면 1/6이 되고, 차원이 그보다 올라가도 적분을 거듭하면 그런 식으로 값이 더욱 작아진다는 걸 알 수 있다.

미분이나 적분을 하면 항의 차수가 1 늘거나 감소하는 대신에 원래 갖고 있던 계수가 곱해지거나 나눠지는 만큼, 이 과정을 일반화하면 팩토리얼 연산도 태생적으로 연관이 되지 않을 수 없게 되는 것 같다. 팩토리얼은 확률· 조합 같은 이산수학 영역뿐만이 아니라 해석학에서도 중요한 의미를 지니는 연산인 셈이다.
아울러, -1승이라 할 수 있는 1/x만 적분하면 ln x라는 완전히 다른 함수가 된다는 것도 아주 흥미로운 점이 아닐 수 없다.

Posted by 사무엘

2011/01/06 12:23 2011/01/06 12:23
, ,
Response
No Trackback , 10 Comments
RSS :
http://moogi.new21.org/tc/rss/response/445

Trackback URL : http://moogi.new21.org/tc/trackback/445

Comments List

  1. 김 기윤 2011/01/06 13:48 # M/D Reply Permalink

    주어진 문제가 1/e 에 수렴하는 것 재밌네요. 뭐랄까, 0에 수렴할줄 알았는데.

    그 밖에 (게임 등에서..) 99% 의 성공확률을 가지는 어느 행동이 있는데, 이걸 계속 하다보면 어째 이 성공확률보다도 실패를 더 많이하는 것 같이 느껴질 때가 있습니다. 그런데 이걸 다시 99%를 N번 시행할때 M번 실패할 확률..이란 식으로 다시 계산해 보면 납득이 가능 수치가 되더군요.

    역시, 수학은 계산하면 답이 나옵니다. (..)


    그 외에 피보나치 수열 하니까 생각났는데, 이전에 알고리즘 문제로 재미있는 문제를 본 적이 있습니다.
    어떠한 수열이 있는데 0과 1로만 이루어져있고, 1은 연속해서 등장하지 않습니다. 그리고 길이가 작은게 앞에 옵니다. 같은 길이라면 오름차순입니다.
    1 ->0
    2 ->1
    3 ->100
    4 ->101
    5 ->1000
    6 ->1001
    7 ->1010
    8 ->10000
    9 ->10001
    10->10010
    11->10100
    12->10101
    13->100000
    ... (후략)
    이런 수열이 있을때 수열의 n번째 원소는 무엇인지 돌려주는 프로그램을 작성하시오.
    하는 문제였는데, 피보나치와 연계해서 풀면 금방 풀립니다. ㄲㄲㄲ 재밌는 문제더군요!

    1. 사무엘 2011/01/06 18:43 # M/D Permalink

      으하... 오늘 가히 필 받으셨나 보군요.
      작정하고 이곳 과월호 글들 다 읽어보신 듯?? ㅋㅋㅋㅋㅋ

      언뜻 보기에 모든 사람이 다 틀린다고 하니까 0에 가까워질 것 같은데, 이 문제는 그렇지 않습니다.
      신기한 면모이죠.

  2. 김재주 2011/01/08 00:45 # M/D Reply Permalink

    1이 두 번 반복되지 않고 0과 1만으로 이루어졌다라...

    3번째 수는 100이 아니라 10이 되어야 하지 않을까요

  3. 사무엘 2011/03/16 21:17 # M/D Reply Permalink

    예전에 썼던 글에다가 오랜만에 첨언한다.
    확률 1/n의 사건이라고 해서 n번의 시도 만에 반드시 일어나리라는 보장은 없다.
    n번의 시행 후에도 확률 1/n의 사건이 전혀 일어나지 못할 확률 역시, n이 커지면 1/e로 수렴한다. 무려 37%나 된다는 뜻이다. 저렇게 n명의 사람이 모두 전혀 다른 모자를 쓰고 있을 확률과 같은 차원이라는 뜻 되겠다.
    뭔가 확률의 확률이라고나 할까? 이 정도면 e는 확률과 조합 분야에서도 수학적으로 정말 의미심장한 수가 아닐 수 없다.

  4. 인민 2011/07/16 12:33 # M/D Reply Permalink

    테일러전개는 가히 놀라운 결과이죠. e^x를 그대로 말짱 e^x가 되는 경우가 이상해서 여러번 검색해서 나온 결과.
    “e^x가 쓰러지지 않아”

    lim n->∞ 1-{(n-1)/n}ⁿ가 1/e에 수렴하긴 하네요.
    사실 미분 테크닉을 쓰다가 자연로그 덕분에 꽤 e를 많이 보는 것일 수 있죠(미분해서 1/x가 나오는 함수는 ln x)

    것보다 점화식 f(x)=(x-1){f(x-1)+f(x-2)} 일반형으로 나타내 보신 분?

    1. 사무엘 2011/07/17 01:39 # M/D Permalink

      점화식의 일반항을 구하는 건 일반적으로 굉장히 어려운 일입니다.
      피보나치 수열만 해도 딱 떨어지는 게 있는 특수한 케이스이기 때문에 이차방정식의 형태로 바꿔서 일반항을 구할 수 있는 것이고요.
      문제의 점화식은 수학 패키지로 돌려 봐도 답이 안 나오고, 깔끔하게 일반항을 못 구하는 형태인 것 같습니다. ㄲㄲ

      말씀하신 극한은 미적분학에서 처음 배우는 e의 극한값 식을 형태만 바꾼 것입니다. 일반적으로 ((n+p)/n)^n의 n 무한대 극한은 e^p가 되지요.

      그런데 인민 님, 중학생이라고 하시지 않았나요? 덜덜;;
      님 블로그 링크를 여기에도 추가했습니다. ^^

    2. 인민 2011/07/17 10:21 # M/D Permalink

      미적분 가지고 미적거리는 수준일 뿐인데요 뭐
      것보다 위의 “그”점화식에서 우변을 n!으로 나누면 일반항 구할 수 있지 ··· 않을까요?(라고 쓰고 않을까나? 라고 읽게 됩니다. 조심)

      (통신강좌에서 점화식/꽤 골치아픈 식을 함수로 주고 생성함수를 구하게 시킨 다음에 테일러로 계수를 구해서 함수를 구한 것이 있었는데 테크닉은 너무 어려워서 시도해보지 못했음)

  5. 범쥬이 2011/08/03 11:00 # M/D Reply Permalink

    역시나 수학은 바바박!!-_-;한 공식들 때문에 지겹기도 하지만
    무한을 다루는 학문이라서 그런지 흥미는 유발됩니다.ㅎ

    좋은글 감사드려요. 샬롬!^^

    (근데.. 김 형제님은 대체 못하시는게 뭐에요??^^; 엄청 재밋으시네유~~^^;;)

    1. 사무엘 2011/08/03 11:27 # M/D Permalink

      이 블로그가 다루고 있지 않은 다른 모든 주제에 대해서는 저는 완전 젬병이고 못하는 것 투성이입니다. 가령, 연애라든가.. ㅋㅋㅋㅋㅋ
      그리고 사실은 다루고 있는 주제라 하더라도 저보다 고수는 세상에 많죠. ㄲㄲㄲㄲㄲ

  6. 소범준 2011/11/21 16:09 # M/D Reply Permalink

    첨언으로, 제 폰 계산기로 글 마지막에 있는 자연대수 e를 구하는 일반적인 공식((1+1/n)^n)을 이용하여 n이 무엇일 때 대략값인 2.71828에 수렴하는지 직접 두드려가며 살펴보았습니다.(방금 전) 그 결과, n=195000과 n=200000 사이에서 처음으로 이 값에 수렴하는 것으로 드러났고,
    더 자세히 탐구해보니 n=198900과 n=199200 사이의 어떤 값에서 처음으로 이 값이 등장하는 것을 발견했습니다. ㅎㅎ;;

Leave a comment
« Previous : 1 : ... 1748 : 1749 : 1750 : 1751 : 1752 : 1753 : 1754 : 1755 : 1756 : ... 2131 : Next »

블로그 이미지

그런즉 이제 애호박, 단호박, 늙은호박 이 셋은 항상 있으나, 그 중에 제일은 늙은호박이니라.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2024/03   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            

Site Stats

Total hits:
2632523
Today:
1075
Yesterday:
1314