위키득계정 ↗
과학

정수 분할

정수 분할과학
영어
Integer partition
항의 조건
양의 정수
순서
항의 순서를 구분하지 않음
반복
추가 제한이 없으면 같은 항을 허용
정수 분할은 음이 아닌 정수를 양의 정수들의 합으로 나타내되 더하는 항들의 순서를 구분하지 않는 표현이다. 같은 수가 여러 번 나타날 수 있으며, 보통 큰 항부터 작은 항으로 정렬해 적는다. 0에는 빈 분할 하나가 있다고 정한다.

순서 없는 합의 표현

7=4+2+1과 7=1+4+2는 같은 정수 분할이다. 반면 7=4+3은 항의 구성이 달라 별개의 분할이다. 순서를 무시하므로 표현을 큰 항부터 나열해 쓰면 같은 분할을 여러 번 적는 일을 피할 수 있다.

작은 정수의 분할 수

5의 분할은 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1의 일곱 가지다. 제한 없는 분할의 개수는 흔히 p(n)으로 나타내므로 p(5)=7이다. 한 개의 큰 항으로 쓰는 경우부터 모두 1로 쓰는 경우까지 포함한다.

부분의 개수와 빈도

분할의 각 항을 부분이라고 부르며 부분의 개수를 제한하거나 특정 크기의 부분만 허용할 수 있다. 각 크기 i의 사용 횟수를 jᵢ라고 두면 j₁+2j₂+⋯+njₙ=n이라는 조건으로 표현한다. 여기서 jᵢ는 음이 아닌 정수이며 같은 크기의 항이 몇 번 등장하는지 기록한다.

다른 분할 문제와 구별

집합의 분할은 서로 다른 원소들을 블록으로 나누는 문제이고 정수 분할은 수의 크기를 합으로 나누는 문제다. 더하는 항의 순서까지 구분하는 경우도 별개의 문제다. 각 항이 서로 달라야 한다거나 홀수여야 한다는 조건을 붙이면 허용되는 분할과 그 개수 역시 달라진다.

관련 문서

집합의 분할 / 자연수 / 양의 정수 / 조합 / 점화식 / 벨 수