[수학, 계산] 고교수학(?)... 자연수의 분할

예전에 @yey 님께서 수열과 생성함수 01 를 통해서 분할수 란 것을 소개받은 적이 있었다.

사실 고등학교 시절 이산수학에서 분할수에 대해서 접한 적이 있다. 스털링수 카탈린 수, 벨 수... 추억이 아른거렸는데 [그 뒤로 접한적이 없다는게 함정... 대학교 이산수학 수업시간에는 점화식과 그래프이론 중심으로 배웠으니....]

아니 할머니 집에 가서 요즘 고등학생 수학 공부 이야기가 나왔는데 이 자연수의 분할과 집합의 분할 내용이 확률과 통계(?) 과정에 포함되어 수능에 나온다는 것이었다.

놀랍군.. 이산수학은 선택과목이었고 뭐 나야 정규 수업이 아닌 조합수학에 관심이 있어서 책을 살펴보고 ebs 강의를 찾아서 공부 했던 거였는데 이제는 이런 내용을 모든(?) 학생들이 공부해야 한다니...

유투브에 자연수의 분할 을 검색하니 수많은 강사들의 영상들이 나왔다.

하 ㅋㅋㅋ 고등학생으로 돌아가면 나는 수학 문제를 잘 풀 수 있을까? ㅋㅋㅋㅋ 아닐것 같다. 미적분이야 맨날 하는 거라 잘 할 수 있을 것 같은데,, 확률과 통계 이런 것들은 거의 다루질 않으니... 예전 같으면 경의의 수 같은거 효율적으로 세고 풀이법 이런것들을 생각했을지라도 지금은 그냥 computer 의 도움을 받는것이 너무나 자연스러워져서 ㅠㅠ

그래서 그냥 한번 예전 노트를 보면서 어떤 어떤 것들을 계산했었나 리뷰를 해봤다.

---

먼저 자연수의 분할이 머냐, 심심한데 5를 분할해 보자

라인 순서대로 5를 하나로 두개로 3개로 4개로 5개로 나누는 방법을 적어 보았다. 사실 1+4 를 4+1 set 과 다른 걸로 본다면 이 자연수의 분할을 세는 것은 엄청 쉬워졌을 것이다. 그냥 단순 조합에 불과하다. 굳이 공식을 적어보자면 n 을 k 개의 자연수의 합으로 순서를 고려하여 표현하는 경우 n-1 C k-1을 가진다.
문제는 이 1+4 와 4+1 set 을 같은 것으로 보기에(순서를 고려하지 않는 경우다) 쉬어 보이는 문제가 복잡해 진 것이다.

일단 문제를 정형화 해보자

자연수의 분할은 자연수 n 을 k 개로 쪼개는 방법 수를 말한다.

여기서 k 가 가지는 범위를 생각해 보면 1부터 n 까지 가능하다는 것을 알 수 있다.

좀 더 나아가 볼까? 이 자연수 n 을 나누는 총 방법을 p(n) 이라 하고 k 개로 나누는 가짓수를 p(n,k) 라고 하면

를 갖는다. 즉 p(n) 을 구하기 위해서는 p(n,k) 의 성질들에 대해서 알아야 한다는 것이다. [물론 몰라도 그냥 다 분할해서 경우의 수를 더할 수 도 있다.... ]

p(n,k) 의 성질

p(n,k)는 다음과 같은 성질을 가진다

@yey 님이 3번째 식 유도과정을 설명해 주신다고 했는데.... ㅠㅠ 아직까지 글이 없다. ㅠㅠ 그냥 포스팅 하다가 해당 내용을 포함해 버렸다;;
[ Hardy 의 Some Famous Problems of the Theory of Numbers 를 보면 유도과정이 잘 나와있다. 사실 이산수학이나 조합수학 책에 증명이 나와있긴 한데 그 증명들은 Hardy 의 책에서 따온 듯 하다. ]

저런 성질들을 어떻게 유도할까? 물론 눈으로 쉽게 보이는 것들도 여러개 있다. 대표적으로 p(n,n) 나 p(n,1) , p(n,2) 같은 경우는 쉽게 보인다.

일반적으로 p(n,k) 를 어떻게 구할까?

그걸 구하기 위해서는 p(n,k) 는 도대체 무엇인가에 대해서 곰곰이 생각해 볼 필요가 있다.

p(n,k) 는

다음 방정식의 음이 아닌 정수해의 갯수와 연관이 있다.

먼저 더 나아가기 전에 간단히 치환을 통해 저 식이

와 같음을 알 수 있다. (n_i 대신에 n_i+1 을 대입해 보면 알 수 있다)

그러면 이 식으로 부터

관계식을 얻는다.

recursion relation 처럼 보이는 다른 관계식은 포함과 배제의 원리를 이용하면 쉽게 보일 수 있다.

이

식을 가지고 적용해 보자. n_k= 1인 경우와 n_k 가 2보다 크거나 같은 경우를 나누어서 보면 된다.

생성함수

p(n,k) 공식을 구하고 싶다면 생성함수에 대한 기초지식이 필요하다. 생성함수 관련 내용을 기술하자면 너무 길어져서, 어떤 생성함수가 필요한지만 서술하고자 한다.

식의 음이 아닌 정수해 갯수

로 다음과 같은 생성함수를 만들 수 있다.

엄밀히 말하면 g(x) 가 아니라 g(x,k) 가 되어야 된다.

p(n,3)

즉 p(n,3) 는

로 부터 구할 수 있다. 사실 저 식으로 부터 p(n+3,3) 을 얻을 수 있다.

저 식을 살짝 변형하여 다른 알려진 생성함수를 이용하여 전개한 뒤 계수를 비교하면 p(n,3) 값을 구할 수 있다

즉 이런식으로

이로부터

이 식의 생성함수가

라 x^n 의 계수를 비교하면 된다.

여기서 w 는 w^3=1 의 복소해로 다른 말로 w^2+w+1=0 의 해이다.

저 등호를 보이는게 사실 엄청 귀찮은 일이다. Hardy 책에는 계산을 하면 된다 과정만 나와있다 ㅠㅠ

사실

로 부터

를 얻은뒤 통분을 통해서 계수를 정해주면 된다..... 차마 손으로 확인 할 수가 없었다..... [프로그램이 왜 있는가!]

x^n 항의 비교를 통해 계수를 읽어내면

즉

하 p(n,3) 이 자연수 임으로 이로부터 3번째 식을 얻는다.

p(n) 의 생성함수

그러면 p(n) 은 어떻게 구할까?
똑같은 방식으로 구할 수 있다.

위 두 식으로 부터

를 얻는다.

---

하 쓰다보니 너무 길어졌다. 여하튼 요즘 고등학생들이 이런걸 배운다니 너무 부럽다.(?) ㅋㅋㅋㅋ 집합의 분할이라 쓰고 스털링 넘버들을 배우던데.... 도대체 어디까지 배우려나 모르겠다.

얘네들은 나중에 대학와서 조합론 이산수학 같은 수업을 들으면 꿀이겠군......