Stars and bars (combinatorics)

Original article: w:Stars and bars (combinatorics)

조합론적 수학(Combinatorial mathematics)의 문맥에서, 별과 막대(stars and bars)는 특정 조합론적(combinatorial) 정리를 유도하기 위한 그래픽 보조 도구입니다. 그것은 확률(probability)에 관한 그의 고전적인 책에서 윌리엄 펠러(William Feller)에 의해 대중화되었습니다. 그것은, n 비-구별-가능한 공을 k 구별-가능한 상자에 넣을 수 있는 경우의 수와 같은, 많은 간단한 세는 문제(counting problems)를 해결하기 위해 사용될 수 있습니다.

Statements of theorems

별과 막대 방법은 종종 기초 조합론의 다음 두 정리를 증명하기 위해 특별히 도입됩니다.

Theorem one

양의 정수(positive integer) n과 k의 임의의 쌍에 대해, 그의 합이 n인 양의(positive) 정수의 k-튜플(tuple)의 숫자는 n − 1 원소를 갖는 집합의 (k − 1)-원소 부분-집합의 숫자와 같습니다.

이들 숫자의 둘 다는 이항 계수(binomial coefficient) $\textstyle {n-1 \choose k-1}$에 의해 제공됩니다. 예를 들어, n = 3이고 k = 2일 때, 정리에 의해 세어진 튜플은 (2, 1)과 (1, 2), 및 그들의 ${\tbinom {3-1}{2-1}}=2$가 있습니다.

Theorem two

양의 정수(positive integer) n과 k의 임의의 쌍에 대해, 그의 합이 n인 비-음의(non-negative) 정수의 k-튜플(tuple)의 숫자는 크기 n + 1의 집합으로부터 취해진 카디널리티 k − 1의 중복집합(multiset)의 숫자와 같습니다.

숫자 둘 다는 중복집합 숫자(multiset number) $\left(\!{\tbinom {n+1}{k-1}}\!\right)$, 또는 동등하게 이항 계수 ${\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}$ 또는 중복집합 숫자 ${\big (}\!{\tbinom {k}{n}}\!{\big )}$에 의해 제공됩니다. 예를 들어, n = 3이고 k = 2일 때, 정리에 의해 세어진 튜플은 (3, 0), (2, 1), (1,2)와 (0, 3), 및 그들의 $\left(\!{\tbinom {3+1}{2-1}}\!\right)=4$가 있습니다.

Proofs via the method of stars and bars

Theorem one

모든 상자는 적어도 하나의 대상을 포함하는 것을 만족하는, n 대상 (별로 나타내어지는; 아래 예제에서 n = 7)을 k 상자 (예제에서 k = 3)에 배치한다고 가정합니다; 상자는 (그들은 1에서 k까지 숫자로 말함) 구별-가능하지만 n 별은 구별되지 않습니다 (그래서 구성은 오직 각 상자에 있는 별의 숫자에 의해서 구별됩니다). 구성은 따라서 정리의 설명에서 처럼 양의 정수의 k-튜플로 표시됩니다. 별을 상자에 넣는 것 대신에, 별을 한 줄에 배치하는 것으로 시작합니다:

★ ★ ★ ★ ★ ★ ★

Fig. 1: 일곱 개 대상은 별에 의해 표시됩니다

여기서 첫 번째 상자에 넣을 별은 왼쪽으로부터 시작해서 취하고, 그 뒤부터는 두 번째 상자에 넣고, 이런 식으로 계속합니다. 따라서, 구성은 두 번째 상자에 넣을 첫 번째 별이 무엇인지, 및 세 번째 상자에 넣을 첫 번째 별이 무엇인지, 이런 식으로 계속해서 아는 것으로 결정될 수 있습니다. 이것은 두 별 사이의 어떤 위치에 k − 1 분리하는 막대(bar)를 놓음으로써 표시될 수 있습니다; 빈 상자는 허용되지 않으므로, 주어진 별들의 쌍 사이에 많아야 하나의 막대가 있을 수 있습니다:

★ ★ ★ ★

|

★

|

★ ★

Fig. 2: 두 막대는 4, 1, 및 2 대상을 포함하는 세 상자를 만듭니다

n 별을 n − 1 틈을 정의하는 고정된 대상으로 보며, 이것의 각각에서 하나의 막대 (상자 분할)가 있을 수도 있고 없을 수도 있습니다. 구성은 실제로 막대를 포함하기 위한 이들 틈의 k − 1을 선택함으로써 얻습니다; 그러므로 ${\tbinom {n-1}{k-1}}$ 가능한 구성이 있습니다 (조합(combination)을 참조하십시오).

Theorem two

이 경우에서, 별을 상자로 나누는 막대를 갖는, 별과 막대의 수열로 튜플의 표현은 바뀌지 않습니다. (양의 값 대신에) 비-음의 값의 약화된 제한은 우리가 두 별 사이에 여러 막대를 배치할 수 있으며, 더불어 첫 번째 별 앞 또는 마지막 별 뒤에 막대를 배치할 수 있음을 의미합니다. 따라서, 예를 들어, n = 7 및 k = 5일 때, 튜플 (4, 0, 1, 2, 0)은 다음의 그림에 의해 표현될 수 있습니다:

★ ★ ★ ★

|

|

★

|

★ ★

|

Fig. 3: 네 막대는 4, 0, 1, 2, 및 0 대상을 포함하는 다섯 상자를 만듭니다

이것은 원하는 형식의 튜플과 n + 1 이용-가능한 틈으로부터 k − 1 틈의 대체를 갖는 선택, 또는 동등하게 크기 n + 1의 집합으로부터 빼낸 (k − 1)-원소 중복집합 사이에 일-대-일 대응을 수립합니다. 정의에 의해, 그러한 대상은 중복선택 숫자 $\left(\!{\tbinom {n+1}{k-1}}\!\right)$에 의해 세어집니다.

이들 대상은 이항 계수 ${\tbinom {n+k-1}{n}}$에 의해 역시 세어짐을 보기 위해, 원하는 배열은 n + k − 1 대상 (n 별과 k − 1 막대)로 구성됨을 관찰하십시오. 별에 대해 위치를 선택하는 것은 k − 1 막대에 대해 남겨진 정확히 k − 1 지점을 남깁니다. 즉, 별에 대해 위치를 선택하는 것은 전체 배열이 결정되므로, 배열은 ${\tbinom {n+k-1}{n}}$ 선택으로 결정됩니다. ${\tbinom {n+k-1}{n}}={\tbinom {n+k-1}{k-1}}$임을 주목하며, 우리는 k − 1 막대에 대해 위치를 선택함으로써 배열이 역시 결정될 수 있다는 사실을 반영합니다.

Examples

만약 n = 5, k = 4, 및 크기 k의 집합이 {a, b, c, d}이면, ★|★★★||★는 중복집합 {a, b, b, b, d} 또는 4-튜플 (1, 3, 0, 1)을 표현할 것입니다. 이 예제에 대해 임의의 중복집합의 표현은 n = 5 별과 k − 1 = 3 막대를 사용할 것입니다.

조합론에서 많은 초급 단어 문제(word problems)는 위의 정리에 의해 해결됩니다. 예를 들어, 만약 우리가 철수, 영희, 영구 사이에 7 비-구별-가능한 오백원 짜리 동전을 분배하는 방법의 숫자를 세기를 원하고 그들의 각자는 적어도 오백원을 받는다면, 분배는 본질적으로 3 양의 정수와 그들의 합이 7이 되는 튜플과 동일하다는 것을 관찰할 수 있습니다. (여기서 튜플의 첫 번째 항목은 철수에게 주는 동전, 등의 숫자입니다.) 따라서 별과 막대는 n = 7 및 k = 3으로 적용되고, 동전을 분배하기 위해 $\textstyle {7-1 \choose 3-1}=15$ 방법이 있습니다.

See also

• Twelvefold way

Further reading

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 0-387-97974-3.
• Weisstein, Eric W. "Multichoose". Mathworld -- A Wolfram Web Resource. Retrieved 18 November 2012.