역함수가 자신과 같아지는 함수의 개수

에 게시됨, 게시자:

서너 달 전인가, 지인이 다음과 같은 질문을 한 적이 있다.

n 개의 원소를 가진 집합 X 가 있다. 함수 f : X \to X가 두 번 합성하면 항등함수가 된다고 하자. 즉, f\circ f (x)= x 이다. 이러한 함수의 개수를 a_n 이라고 할 때, 일반항을 구하여라.

근데 쉽게 풀리지 않았다. 요 몇 달을 고민해봤는데 다음과 같은 풀이가 내가 낼 수 있는 최선의 풀이였다.

 

먼저 점화식을 다음과 같이 구한다. 편의상 X = \{1, 2, \cdots ,n-1\}이라고 하자. n이 X 에 추가되었다면, 함수 f 가 조건을 만족하기 위해서는

  1. f(n) = n 인 경우 : 이 때의 함수의 개수는 a_{n-1} 이 된다.
  2. f(n) = b (단, b \ne n) 인 경우 : 이 때는 f(b) = n 로 결정되므로 a_{n-2} 이 된다. 이러한 조합이 n-1가지가 있다.

위를 종합하면 점화식은 a_n = a_{n-1} + (n-1)a_{n-2}이 되는데, 이 점화식을 푸는 것이 녹록치 않다. ㅋ

먼저 이 점화식을 이용한 generating function T(x) 를 만들면 다음 미분방정식이 나온다.

x^3 T'(x) + (x^2 + x -1)T(x) = -1

그런데 이놈을 풀려면 초등함수로는 표현할 수 없는 적분식이 등장하므로 해결할 수 없다. 정확한 식을 구할 수는 없어도 Taylor Expansion을 해서 일반항을 찾으려고 용을 쓰다가 안 돼서, 행렬로 변형하거나 차분방정식 같은 테크닉을 검색해서 계산하다보니 어느새 두어 달이 지나가버렸다. 켁.

그래서 좀 다른 방법을 써봤다. 일단 주어진 점화식의 양변을 (n-1)! 로 나눈 후에 b_n = \frac{a_n}{n!} 이라고 두면, 점화식은 다음과 같이 바뀐다.

nb_n = b_{n-1} + b_{n-2}

이놈의 generating function을 만들면 신기하게도 앞의 미분방정식보다는 훨 쉬운 형태가 된다. 즉,

T'(x) = (1+x)T(x)

오오, 이놈은 쉽게 풀린다. 적분상수를 보정하면 간단하게 T(x) = \exp(x + \frac{x^2}{2}) 임을 알 수 있다. 이 함수를 원점에서 Taylor expansion 하여 일반항에 n! 을 곱해야 하므로 그냥 n계 도함수에 영을 대입한 값이 된다. 그리하여 좀 괴악하지만 다음과 같은 결과를 얻을 수 있다.

\displaystyle a_n = \frac{d^n}{dx^n}\left.\left(e^{x+ \frac{x^2}{2}}\right) \right|_{x=0}

더 나은 풀이가 있으신지?

이 글은 카테고리: 문제에 포함되어 있습니다. 고유주소를 북마크하세요.

“역함수가 자신과 같아지는 함수의 개수”에 대한 10개의 생각

  1. 실제로 이것은 일반항을 구하는건 힘든데 generating function이 \exp(x+x^2/2)가 되는 것을 보이는 것은 간단합니다. Richard Stanley 교수님의 Enumerative Combinatorics에서도 한 두번 등장하는 연습문제이기도 하고요. 가장 간단하게 derive할 수 있는 방법 중의 하나는 EC2의 Corollary 5.1.8, 즉 Compositional Formula permutation version을 쓰는 것입니다. 일반적으로 순열의 싸이클마다 그 싸이클의 길이가 k일 때 f(k)라는 값을 부여한 후 h(n)=\sum_{\pi \in S_n} f(\#C_1) \cdots f(\#C_k)g(k), h(0)=1 이라 하면 E_h(x)=E_g(\sum_{n \geq 1} f(n) \frac{x^n}{n}) 이라는 내용입니다. (여기서 E_f 는 f(1),... 의 exponential generating function) 그러면 우리가 구하는 것은 싸이클의 길이가 1이나 2인 것들의 개수이니까, f(1)=1, f(2)=1, f(3)=f(4)=…=0, g(0)=g(1)=g(2)=…=1로 두면 바로 \exp(x+\frac{x^2}{2})가 나옵니다.
    물론 순열적 관점이 아닌 원래 Compositional Formula를 써도 됩니다. (Theorem 5.1.4) 이 경우 싸이클이 아니라, n개짜리 집합을 부분집합들로 분할하는 것이 되는데 E_h(x)=E_g(E_f(x)) 입니다. 역시 앞과 같이 f,g를 정의해도 값은 똑같이 나오죠. (Compositional Formula의 증명은 전개해보면 거의 trivial합니다.)

    응답

    • ㅎㅎ 기호나 용어가 조금 낯설어서 책을 찾아봤습니다. 이런 정리가 있었군요. 감사합니다. :)

      응답

    • 제가 조합론은 문외한이라 유명한 문제인줄 몰랐군요. ㅎㅎ 이미 정수열 사전에 등록이 되어 있군요. :)

      응답

  4. 어어엇 이런 엄청난 우연이 ㅎㄷㄷ …..예전에 AOPS(Art Of Problem Solving)에서 Olympiad section에서 어떤 사람이 a_(n+1)a_n-a_n=n의 explicit form을 구하는 문제에 대하여 질문을 올린 적이 있습니다. (http://www.artofproblemsolving.com/Forum/viewtopic.php?f=36&t=457563참고) 그 때 제가 이를 변형시켜 A_1=a, A_2=a+1로 주어졌을 때(a는 임의로 주어진 상수) 귀납식 A_(m+1)=A_m+m*A_(m-1)을 푸는 문제로 바꿀 수 있다고 답변을 올렸었죠. 하지만 정작 A_m을 구하는 작업이 쉽지 않더군요… 그나마 저의 짧은 지식으로 시도해본 최후의 방법이 Taylor 급수와 생성함수였는데(아직 고딩이라 지식의 양의 한계가 大大大) 둘 다 최종적인 답을 구하기 어려운 식을 내놓고 실패하고 말았습니다. ㅜㅜ 그런데 우연히 zariski님의 블로그를 방문했다가 이번 포스트를 보고 깜짝 놀랐습니다 ㄷㄷㄷ 똑같은 문제를 보게 되니 반가운 마음과 놀라운 마음이 동시에 드는군요 ㅎㅎ

    어쨌든 그 풀리지 않을 것만 같았던 문제가 이미 잘 알려진 문제이고 또한 약간의 변형을 가하면 생성함수가 만족시키는 differential equation을 간단하게 만들 수 있다는 사실이 매우 놀랍게 느껴졌습니다. 이번 포스트는 저에게 매우 많은 도움이 된 것 같습니다, 감사합니다^^

    응답

댓글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

Gravatar
WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 / 변경 )

취소

%s에 연결하는 중