수를 쪼개자!- 분할수에 대해서

제가 소수에 관한 책을 읽고 있는데

중간에 퀴즈같지 않은 퀴즈(?)가 나왔어요.

다음 수열의 규칙성을 찾으라는 것이었는데,

첫 번째는 1, 3, 6,10, 15, .....이렇게 가더라고요.

이건 더해지는 수가 하나씩 늘어나는 계차수열인 것 같더라고요.

책에서는 '삼각수'라고 했습니다.

그 다음 수열은 1, 1, 2, 3, 5, 8,....이었습니다.

이건 '피보나치 수열'로 앞에 두 수를 더한 값이 뒤에 수가 됩니다.

그런데 마지막 수열이 저를 괴롭혔습니다.

1, 2, 3, 5, 7, 11, 15,....

(갑자기 베르나르 베르베르의 개미에 나오는 수열이 떠오르더군요.

그것도 못 풀었는데 이것도 못 풀겠다...뭐 이런 심정?)

이것이 바로 "분할수"라고 부르는 것입니다.

먼저, 분할수의 정의부터 알아볼까요?

분할수(partition number)란, 자연수를 분할하는 가짓수를 의미합니다.

(정확히 말하면 자연수에 0을 더한 범자연수라 볼 수 있습니다.

왜냐하면 뒤에 나올 함수식 형태로 표현한 것이

저는 1부터 설명하지만 많은 곳에서 0부터 시작하거든요.)

예를 들어, 5라는 수가 있으면

(5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)로 

총 7묶음으로 분할이 가능합니다.

이때, (3, 2)나 (2, 3)이나 똑같은 겁니다.

그래서 5의 분할수는 7이 됩니다.

다른 예를 들어볼까요?

좀 숫자가 커지면 힘들어지니까 5의 바로 다음 수인 6을 보겠습니다.

(6), (5, 1), (4, 2), (4, 1, 1), (3, 3), (3, 2, 1), 

(3, 1, 1, 1), (2, 2, 2), (2, 2, 1, 1), (2, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1)

총 11묶음이 나오니 6의 분할수는 11입니다.

일단 기본적인 분할수의 개념은 이렇게 됩니다.

그래서 이걸 p(n)이라고 부르고, p(5)=7, p(6)=11이라고 부릅니다.

그런데 분할수를 구할 때 보니 (2, 2, 1, 1)과 같이 같은 원소가 중복되는 묶음이 있습니다.

그 묶음을 제외한 것들만 추려낸 것도 있는데

정확한 명칭은 잘 모르겠습니다만, 기호로는 q(n)이라고 씁니다.

그래서 q(5)의 경우, (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)빼고

(5), (4, 1), (3, 2)만 계산하여 q(5)=3입니다.

마찬가지로 q(6)=4겠죠?

다음 표는 1에서 15까지 분할수 표입니다.

수	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
p(n)	1	2	3	5	7	11	15	22	30	42	56	77	101	135	176
q(n)	1	1	2	2	3	4	5	6	8	10	12	15	18	22	27

혹시 더 많은 분할수가 필요하신 분들은

http://oeis.org/ 에 들어가시기 바랍니다.

이 사이트는 여러 정수로 된 수열을 친절하게 데이터베이스 한 것입니다.

p(n)은 http://oeis.org/A000041

q(n)은 http://oeis.org/A000009 입니다.

이 분할수는 영 타블로(Young tableau)로 나타낼 수 있는데요,

사실은 영 타블로로 그린다기 보다는 페러스 그림으로 나타낸다는 표현이 더 옳습니다.

하지만 종종 섞어서 사용하는 표현인 것 같으니

페러스 그림과 영 타블로 그림에 대해 설명을 해보겠습니다.

영 타블로란 페러스 그림(Ferrers diagram)의 각 칸에 숫자를 기입한 것이랍니다.

페러스 그림은 그냥 잘라먹은 표처럼 생긴 그림입니다.

정의는 일련의 행들로 이루어진 도형...이라고 하더군요.

페러스 그림은 아래로 갈수록 길이가 같거나 짧아져야 합니다.

다음 그림과 같이요.

에고, 왜 이렇게 삐뚤빼뚤하지...?

어쨌든, 페러스 그림에서 영 타블로를 만드려고 숫자를 쓸 때는

두 가지 방법이 있습니다.

먼저, 표준 영 타블로(standard Young tableau)는

오른쪽으로 갈수록 숫자가 항상 증가해야 하고

아래쪽으로 갈수록 숫자가 항상 증가해야 합니다.

반면에, 준표준 영 타블로(semistandard Young tableau)는

오른쪽으로 갈수록 숫자가 항상 감소하지 않고(즉, 같거나 증가한다는 의미입니다.)

아래쪽으로 갈수록 숫자가 항상 증가해야합니다.

그래서 분할수를 페러스 그림으로 그리려면

아래 그림과 같이 그리면 되겠죠.

숫자는 어떻게 분할하면 되는지에 대한 내용입니다.

(저는 영 타블로 그림을 그린 것이 아니에요~^^;;)

저는 p(5)에 대해서 그려보았습니다.

음...이렇게 그리는 것이 아까보나 낫나요?

이게 훨씬 그리기는 편하네요...

그런데 이 분할수는 '분할수'라는 그런 규칙 외에 다른 식으로 나타낼 수 없을까요?

놀랍게도 가능하다고 합니다.

라마누잔이 하디와 함께 반올림하면 분할수가 되는 공식을 찾아냈고

후에 그걸 또 다듬어서 오차가 더 적고 마찬가지로 반올림하면 분할수가 되는 공식을 

'한스 라데마허'라는 분이 찾았다고 합니다.

그런데 라데마허씨의 공식은 너무너무 어렵고 복잡합니다.

어쩌피 둘다 어림식인데 어려운 걸 써서 뭐합니까.

그래서 우리는 아직도 라마누잔씨의 훨씬 쉬운 어림식을 쓰는 것을 즐겨하죠.

사실 하디와 라마누잔이 밝힌 식은 p(n)에 대해서입니다.

애석하게도 제가 아무리 찾아봐도 q(n)의 정확한 명칭이나 식을 만든 사람이 안 나오네요.

더 애석한 것은, 한스 라데마허씨는 인터넷에 나오지도 않아요...

어찌되었든 그가 만든 식을 제가 책에서 본 대로....옮기지는 못할 것 같습니다.

위에 수식을 쓸 때 전 Daum Equation Editor를 쓰는데

시그마 아래 범위를 어떻게 쓰는지 모르겠어요...

혹시 나중에 찾아보고 싶으시다면 '소수의 음악'이라는 책의

239쪽에 보시면 나와있습니다.

그래서 오늘 뭔가 이상하고 재미있었던 분할수에 대해 알아봤습니다.

혹시 저만 재미있었나요...?

마지막 수식에서 실망했어요?

저도 저 식 안 외우고 다니고 이해하려 들지 않습니다.

그 식 말고 그 위에 있는 내용들만 아셔도 충분하실 겁니다.

물론, 당신이 수학자가 아니라는 조건 아래에서요.

그럼 즐거운 하루 되세요!