위키득계정 ↗
과학

순서 있는 정수 분할

순서 있는 정수 분할과학
영어
Composition of an integer
항의 조건
양의 정수
순서
항의 순서를 구분
전체 개수
n≥1에서 2ⁿ⁻¹
순서 있는 정수 분할은 양의 정수를 양의 정수들의 합으로 나타내면서 항의 순서를 구분하는 표현이다. 영어로 composition이라고 한다. 순서를 무시하는 정수 분할과 달리 2+3과 3+2를 서로 다른 표현으로 센다.

순서가 바뀌면 다른 표현

정수 3의 순서 있는 분할은 3, 2+1, 1+2, 1+1+1의 네 가지다. 보통의 정수 분할에서는 2+1과 1+2가 같지만 여기서는 다르다. 항의 순서를 유지한 하나의 유한 수열로 이해할 수 있으며, 같은 크기의 항이 반복되는 것도 허용한다.

틈을 자르는 방법

n개의 1을 한 줄로 놓으면 이웃한 1 사이에 n−1개의 틈이 생긴다. 각 틈을 자르거나 붙여 두어 각 덩어리의 합을 한 항으로 만든다. 모든 틈에서 두 선택을 하므로 전체 개수는 2ⁿ⁻¹이다. 이 설명은 n이 양의 정수라는 조건에서 적용한다.

항의 개수가 정해진 경우

정확히 k개의 양의 항을 만들려면 n−1개의 틈 중 k−1개를 잘라야 한다. 따라서 1≤k≤n에서 개수는 binom(n−1,k−1)이다. 예를 들어 6을 세 양의 항으로 나타내는 순서 있는 표현은 binom(5,2)=10가지다. k가 n보다 크면 만들 수 없다.

0을 허용하는 경우

항으로 0을 허용하는 약한 합성은 다른 조건을 가진다. n≥0이고 항의 개수 k≥1을 고정하면 개수는 binom(n+k−1,k−1)이다. 항의 개수를 고정하지 않은 채 0을 자유롭게 추가하면 같은 합을 갖는 표현을 끝없이 만들 수 있으므로 유한한 개수를 세려면 조건을 분명히 해야 한다.

관련 문서

정수 분할 / 조합 / 이항계수 / 수열 / 자연수 / 중복조합