미르카, 수학에 빠지다 1

생성함수, 수열을 다루는 강력한 방법

미르카, 수학에 빠지다 1 - 유키 히로시 저

중학생 시절 수학걸이라는 이름으로 읽었던 책이다. 15년이 지난 지금 생각이 나서 찾았는데 미르카, 수학에 빠지다라는 이름의 시리즈로 다시 나온 것 같다.

당시 가장 인상에 남는 것은 피보나치 수열의 일반항을 구하는 과정과 일반항에 무리수 루트 5가 존재한다는 사실이었다. 후반부는 미분 등의 개념을 몰라 이해를 못 한 것으로 기억이 난다.

시간이 흐른 지금 이 책을 상당히 재미있게 읽었다. 과거 이해하지 못했던 부분도 따라갈 수 있었고, 문제마다 읽기를 멈추고 직접 생각해 본 뒤 읽고 비교해 보는 것도 재미가 있었다.

수열과 생성함수

미르카, 수학에 빠지다 1에서는 주로 수열에 관해 다룬다. 그리고 수열을 다루는 강력한 방법으로 생성함수라는 개념을 사용한다.

수열의 각 항 a_n을 x^n의 계수로 보는 것이다. 생성함수에 관해서는 아직 잘 모르지만, 수열을 무한 차수의 다항식으로 대응시켜 미분 등의 해석 유용한 해석 기법을 사용할 수 있게 만드는 것으로 이해했다.

이렇게 만든 생성 함수를 수열의 성질과 해석 기법을 통해 닫힌 식으로 변형한다.

마지막으로 위의 닫힌 식f(x)을 다시 다항식으로 전개하면 일반항 을 얻고 수열의 일반항 a_n*x^n을 얻을 수 있다. 결국 원래의 수열 -> 생성함수 -> 생성함수의 닫힌 식 -> 다시 전개의 과정을 통해 수열의 일반항을 얻는 것이다.

우리가 아는 한, 수열을 다루는 제일 강력한 방법은 대상이 되는 수열을 생성하는 무한급수를 조종하는 것이다.

본 책에서 언급된 구체 수학 - Concrete Mathematics에 인용된 문구인데, 인상이 깊어 시간을 내서 이 책도 공부하고 싶다.

분할수

소개된 문제들이 대부분 흥미로워 잠깐 읽기를 멈추고 생각하는 시간을 가졌다. 하지만 가장 흥미로웠던 문제는 분할수라는 문제이다.

분할수란, 액면이 1원, 2원, 3원, ...인 동전이 있다고 가정할 때 n원을 지불하기 위한 동전의 조합의 수 이다.

이 문제를 생각하는데 시간을 가장 많이 사용했는데, 일반항을 구하지는 못했지만 점화식을 구하고 프로그램을 작성해서 답을 구할 수 있었다. 구체적인 과정은 따로 정리했다(링크).

간략하게 설명하면, n원을 지불하기 위한 방법으로 최대 액면가가 n원, n-1원, ... , 1원인 경우를 나누어 생각하는 것이다. 이때 최대 액면가가 k원인 n원의 부분 분할수를 라고 하면 다음과 같은 관계를 가진다.