조합론적 수학(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-튜플로 표시됩니다. 별을 상자에 넣는 것 대신에, 별을 한 줄에 배치하는 것으로 시작합니다:
여기서 첫 번째 상자에 넣을 별은 왼쪽으로부터 시작해서 취하고, 그 뒤부터는 두 번째 상자에 넣고, 이런 식으로 계속합니다. 따라서, 구성은 두 번째 상자에 넣을 첫 번째 별이 무엇인지, 및 세 번째 상자에 넣을 첫 번째 별이 무엇인지, 이런 식으로 계속해서 아는 것으로 결정될 수 있습니다. 이것은 두 별 사이의 어떤 위치에 k − 1 분리하는 막대(bar)를 놓음으로써 표시될 수 있습니다; 빈 상자는 허용되지 않으므로, 주어진 별들의 쌍 사이에 많아야 하나의 막대가 있을 수 있습니다:
n 별을 n − 1 틈을 정의하는 고정된 대상으로 보며, 이것의 각각에서 하나의 막대 (상자 분할)가 있을 수도 있고 없을 수도 있습니다. 구성은 실제로 막대를 포함하기 위한 이들 틈의 k − 1을 선택함으로써 얻습니다; 그러므로 \(\tbinom{n - 1}{k-1}\) 가능한 구성이 있습니다 (조합(combination)을 참조하십시오).
Theorem two
이 경우에서, 별을 상자로 나누는 막대를 갖는, 별과 막대의 수열로 튜플의 표현은 바뀌지 않습니다. (양의 값 대신에) 비-음의 값의 약화된 제한은 우리가 두 별 사이에 여러 막대를 배치할 수 있으며, 더불어 첫 번째 별 앞 또는 마지막 별 뒤에 막대를 배치할 수 있음을 의미합니다. 따라서, 예를 들어, n = 7 및 k = 5일 때, 튜플 (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\) 방법이 있습니다.
References
- Feller, William (1950). An Introduction to Probability Theory and Its Applications. Vol. 1 (2nd ed.). Wiley.
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.
