자연수 분할

위키백과, 우리 모두의 백과사전.
(분할수에서 넘어옴)
이동: 둘러보기, 검색
분할 9=5+4+1을 나타내는 영 타블로

정수론에서, 자연수 분할(영어: integer partition)은 어떤 자연수를 양의 정수들의 합으로 나타내는 방법이다.

정의[편집]

자연수 n\in\mathbb N분할 \{n_1,\dots,n_k\}은 다음을 만족시키는 중복집합이다.

n_1+\cdots+n_k=n

분할은 영 타블로로 나타낼 수 있다. 이 경우 각 가로의 길이는 분할의 각 원소의 크기에 대응한다. 분할수(分割數, 영어: partition number) p(n)n의 분할들의 수이다. 분할수의 값들은 다음과 같다 (p(0)=1부터 시작).

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, … (OEIS의 수열 A41)

q(n)n의 분할들 가운데, 원소가 중복되지 않는 것들의 수이다. 이는 다음과 같다 (q(0)=1부터 시작).

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, … (OEIS의 수열 A9)

[편집]

양의 정수 3을 생각해보자.

  1. 3 = 3
  2. 3 = 2 + 1
  3. 3 = 1 + 1 + 1

으로 총 세가지의 경우가 있으므로, 3의 분할수는 p(3) = 3, q(3)=2가 된다.

4일 때는,

  1. 4 = 4
  2. 4 = 3 + 1
  3. 4 = 2 + 2
  4. 4 = 2 + 1 + 1
  5. 4 = 1 + 1 + 1 + 1

총 다섯가지이므로, 4의 분할수는 p(4) = 5, q(4)=2이 된다.

참고 문헌[편집]

  • (영어) George E. Andrews, Kimmo Eriksson (2004). 《Integer Partitions》. Cambridge University Press. ISBN 0-521-60090-1
  • (영어) Andrews, George E. (1976년). 《The Theory of partitions》, Encyclopedia of Mathematics and its Applications 2. Cambridge University Press. ISBN 0-521-63766-X
  • (영어) Apostol, Tom M. [1976] (1990). 《Modular functions and Dirichlet series in number theory》, Graduate Texts in Mathematics 41, 2판, Springer. Zbl 0697.10023. ISBN 0-387-97127-0
  • (영어) Macdonald, Ian G. (1979). 《Symmetric functions and Hall polynomials》, Oxford Mathematical Monographs. Oxford University Press. Zbl 0487.20007. ISBN 0-19-853530-9
  • (영어) Nathanson, M.B. (2000). 《Elementary methods in number theory》, Graduate Texts in Mathematics 195. Springer-Verlag. Zbl 0953.11002. ISBN 0-387-98912-9
  • (영어) Bóna, Miklós (2002). 《A walk through combinatorics: An introduction to enumeration and graph theory》. World Scientific. ISBN 981-02-4900-4

바깥 고리[편집]