구성(결합)

수학에서 정수 n의 구성은 (엄격한) 양의 정수 순서의 합으로 n을 쓰는 방법이다.용어의 순서가 다른 두 시퀀스는 합계의 다른 구성을 정의하는 반면, 같은 수의 분할을 정의하는 것으로 간주된다.모든 정수는 미세하게 구별되는 구성이 많다.음수는 어떠한 구성도 가지고 있지 않지만, 0은 하나의 구성, 즉 빈 시퀀스를 가지고 있다.각각의 양의 정수 n은 2개의ⁿ⁻¹ 뚜렷한 구성을 가지고 있다.

정수 n의 약한 구성은 n의 구성과 유사하지만, 수열의 항이 0이 되도록 허용하는 것은 n을 음이 아닌 정수의 수열의 합으로 쓰는 방법이다.결과적으로 모든 양의 정수는 무한히 많은 약한 구성을 인정한다.약한 구성의 끝에 0이라는 용어를 여러 개 추가하는 것은 보통 다른 약한 구성을 정의하는 것으로 간주되지 않는다. 즉, 약한 구성은 0이라는 용어에 의해 암묵적으로 무한히 확장되는 것으로 가정한다.

더 일반화하기 위해, (부정수 또는 양의) 정수의 부분 집합 A에 대해, 정수 n의 A 제한 구성은 합계가 n인 A에서 하나 이상의 원소의 순서 집합이다.^[1]

예

5의 16개 구성은 다음과 같다.

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 3
• 2 + 2 + 1
• 2 + 1 + 2
• 2 + 1 + 1 + 1
• 1 + 4
• 1 + 3 + 1
• 1 + 2 + 2
• 1 + 2 + 1 + 1
• 1 + 1 + 3
• 1 + 1 + 2 + 1
• 1 + 1 + 1 + 2
• 1 + 1 + 1 + 1 + 1.

5의 7개 파티션과 비교해 보십시오.

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1.

구성의 부분에 제약을 가할 수 있다.예를 들어 5의 다섯 가지 구성은 구별되는 용어로 다음과 같다.

• 5
• 4 + 1
• 3 + 2
• 2 + 3
• 1 + 4.

이것을 5의 세 개의 파티션과 구별되는 용어로 비교해 보십시오.

• 5
• 4 + 1
• 3 + 2.

작문수

일반적으로 빈 구성은 0의 유일한 구성으로 계산되며, 음의 정수의 구성은 없다.n ≥ 1의 두 가지ⁿ⁻¹ 구성이 있다. 여기에 증거가 있다.

어레이의 각 n - 1박스에 더하기 기호 또는 쉼표 배치

${\displaystyle {\big(}\,\overbrace {1\,\square \,1\,\square \,\ldots \,\square \,\n1},{\big )}}}}}}}}$

n의 독특한 구성을 생산하다.반대로 n의 모든 구성은 플러스와 콤마의 할당을 결정한다.n - 1 이항 선택이 있기 때문에 결과는 다음과 같다.같은 주장은 정확히 k 부분(k-composition)으로 n을 구성하는 횟수가 이항계수$({\displaystyle n\genfrac{}{}{0ex}{}{}{}}$- ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{k}}{}}$- 1$){\$에 의해 주어진다는 것을 보여준다$.$ 유의할 점은 가능한 모든 수의 부품을 합쳐서 2를ⁿ⁻¹ n의 전체 구성 수로 회복한다는 것이다.

${\displaystyle \sum _{k=1}^{n}{n-1 \선택 k-1=2^{n-1}.}$

약한 구성의 경우$,{\displaystyle }$ 각 k-구성 n + k의 약한 구성에 해당하므로 숫자는 (n${\displaystyle \genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}\genfrac{}{}{0ex}{}{}{}}$-${\displaystyle \genfrac{}{}{0ex}{}{}{}}$1${\displaystyle \genfrac{}{}{0ex}{}{}{}\genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ )${\displaystyle }$=$$(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$+ k${\displaystyle \genfrac{}{}{0ex}{}{}{}}$- ${\displaystyle \genfrac{}{}{0ex}{}{1}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$) {\$displaystyle {n+k-1 \선택$ k-1$={n+k-1$ 규칙으로 n의 약한 구성에 해당하기 $때문$에 n을 $선택$한다.

${\displaystyle a_{1}+a_{2}+\ldots +a_{k}=n+k\mapsto \mapsto \mapsto (a_{1}-1)+(a_{2}-1)+++\ldots +(a_{k}-1)=n}$

이 공식에서 정확히 k 부분에서의 n의 약한 구성의 수는 정확하게 n + 1 부분에서의 k - 1의 약한 구성의 수와 같다는 것을 알 수 있다.

For A-restricted compositions, the number of compositions of n into exactly k parts is given by the extended binomial (or polynomial) coefficient ${\displaystyle {\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}]\left(\sum _{a\in A}x^{a}\right)$$^{k$ 여기서 대괄호는 그 뒤에 오는 다항식에서 $x$ ${\displaystyle n^{}}$ ${\$의 계수 추출을 나타낸다.^[2]

동종 다항식

벡터 $공간{\displaystyle }$ K${\displaystyle }$[ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle }$x ${\displaystyle n_{}}$ ${\displaystyle {}_{}{}_{}}$ d ${\$의 치수는 필드 K 위에 있는 n 변수에 d의 동종 다항식 d의 약한$$ 합성 수입니다.In fact, a basis for the space is given by the set of monomials ${\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}$ such that ${\displaystyle d_{1}+\ldots +d_{n}=d}$. Since the exponents ${\displaystyle d_{i}}$ are allowed to be zero, then the number of such단항은 정확히 d의 약한 구성의 수에 의해 이루어진다.

참고 항목

• 별 및 막대(복합체)

참조

• Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373.

외부 링크

• 파티션 및 컴포지션 계산기