경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요![[분류:조합론]] '''다항계수'''(multinomial coefficient)는 [[이항계수]]의 일반화이다. == 모티브 == 다항계수의 정의는 사실 '''다항정리'''에서 시작된 것이다. 먼저 [[이항정리]]를 보자: <div align=center> <math>(x_1 + x_2 )^n = \sum_{r=0}^n \binom n r {x_1}^r {x_2}^{n-r}.</math></div> 이제 ''자연스럽게'' 이것을 확장할 수 있을 것이다. 즉 우리는 <div align=center> <math>(x_1 + x_2 + \cdots + x_m )^n = \sum_{n_1 + \cdots + n_m = n} C(n_1, n_2, \cdots, n_m) {x_1}^{n_1} {x_2}^{n_2}\cdots {x_m}^{n_m}</math></div> 으로 나타내고 싶다(?). 이항정리에서, <math>x^r y^{n-r}</math>의 계수는 <math>n</math> 개의 대상(object)을 <math>r</math> 개와 <math>n-r</math> 개로 양분(서로 다른 둘로 [[분할]])하는 경우의 수이다. 따라서 다음과 같이 정의해볼 수 있다. : '''다항계수'''는 <math>n</math> 개의 대상을 <math>m</math> 개로 나누는 경우의 수이다. 더 명시적으로, 다항계수 <math>\binom{n}{n_1, \cdots, n_m}</math>는 <math>n</math> 개의 대상을 <math>n_1, \; n_2, \; \cdots , \; n_m</math> 개씩 분할하는 경우의 수이다. 자, 이제 이 경우의 수를 구해보자. 먼저 <math>n</math> 개의 대상에서 <math>n_1</math> 개를 골라내고, 남은 것에서 <math>n_2</math> 개를 골라내고, 이런 식으로 반복하면 다항계수는 다음과 같음을 알 수 있다: <div align=center> <math>\binom{n}{n_1, \cdots, n_m} = \binom{n}{n_1} \binom {n-n_1}{n_2} \cdots \binom{n-n_1 - \cdots - n_{m-1}}{n_m} = \prod_{j=1}^n \binom{n-\sum_{k=1}^{j-1} n_k}{n_j}.</math></div> 이항계수의 정의를 이용하여 전개해보면: <div align=center> <math>\binom{n}{n_1, \cdots, n_m} = \frac{n!}{n_1 ! (n-n_1 )! } \frac{(n- n_1)!}{n_2 ! (n-n_1 -n_2)! } \cdots \frac{(n- n_1 - \cdots - n_{m-2})!}{n_{m-1} ! (n- n_1 - \cdots - n_{m-1})! } \frac{(n- n_1 - \cdots - n_{m-1})!}{n_m ! 0! } = \frac{n!}{n_1 ! n_2 ! \cdots n_m !} .</math></div> 어...? 어디서 많이 본 것 같다? 정의에서도 알 수 있듯, 이것은 같은 것이 있는 [[순열]]과 같다. 같은 것이 있는 순열은 미리 종류를 정해주고 섞는 것이라면, 다항계수는 무작위로 종류를 정해주는 것이라고 생각할 수 있기 때문이다. == 정의 == 다항계수 <math>\binom{n}{n_1, \cdots, n_m}</math>는 다음의 동치인 진술 중 하나로 정의된다: * <math>\binom{n}{n_1, \cdots, n_m} =\frac{n!}{\prod_{j=1}^m n_j !} = \frac{n!}{n_1 ! n_2 ! \cdots n_m !} </math> * <math>(x_1 + x_2 + \cdots + x_m )^n </math>의 <math> {x_1}^{n_1} {x_2}^{n_2}\cdots {x_m}^{n_m}</math>-항의 계수 * <math>j</math>라고 이름 붙여진 대상이 <math>n_j</math> 개씩 있을 때, 그것을 나열하는 경우의 수(순열) (<math>j=1, \cdots, m</math>) == 성질 == * 이항계수 <math>\binom{n}{r} = \binom{n}{r, n-r}</math>이다. * <math>\sigma</math>를 [[치환 (선형대수학)|치환]]이라고 하면, <math>\binom{n}{n_1, \cdots, n_m} = \binom{n}{\sigma(n_1), \cdots, \sigma(n_m)}</math>이다. * (다항계수 항등식) <math>\binom{n}{n_1, \cdots, n_m} = \sum_{j=1}^{m} \binom{n - 1}{n_1, \cdots, n_{j-1} , n_j - 1 , n_{j+1}, \cdots, n_m} </math> * 다항정리에서 <math>x_j = 1</math>일 때 <math>\sum_{\sum n_j = n}\binom{n}{n_1, \cdots, n_m} = m^n </math>이다. * [[나눗셈 정리]]에 의해 <math>n=mr+k \; \; (0\le k < m)</math>이라 하면, 다항계수 중에서 최댓값을 가지는 것은 <math>\binom{n}{\underbrace{r, \cdots, r}_{m-k}, \underbrace{r+1, \cdots, r+1}_{k}} = \frac{n!}{r!^{m-k}(r+1)!^k}= \frac{n!}{r!^{m}(r+1)^k}</math>이다. 다항식 <math>(x_1 + \cdots + x_m)^n</math>에서 이 최댓값을 계수로 갖는 항의 수는 <math>\binom{m}{k}</math> 개이다.<ref>Q. Wu, ''Maximal Coefficient of the Multinomial <math>(x_1 + x_2 + \cdots + x_k)^n</math>'', Southeast Asian Bulletin of Maths. '''15''' (1991), 77-82</ref> == 참고문헌 == * Chuan Chong Chen, Khee Meng Koh, ''Principles and Techniques in Combinatorics'', World Scientific (1992). == 주석 == <references/> 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:각주 (원본 보기) (준보호됨)