이항계수와 조합

수학노트
둘러보기로 이동 검색으로 이동

개요

  • n개의 서로 다른 물건에서 r개를 선택하는 방법:<math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math>
  • 조합(combination)이라고도 함
  • 조합수학에서 가장 기본적이며 중요한 수열의 하나
  • 중요한 성질
    • palindromic
    • unimodality



생성함수

  • 생성함수:<math>(1+x)^n=\sum_{r=0}^{n} {n\choose r}x^r = {n\choose 0} + {n\choose 1}x + \cdots + {n\choose r}x^r + \cdots + {n\choose n}x^n</math>



점화식

  • n에 대한 이항계수를 통해, <math>n+1</math>에 대한 이항계수를 유도할 수 있음:<math>{n\choose r-1}+{n\choose r}={n+1\choose r}</math>




이항계수의 합

<math>2^n=\sum_{r=0}^{n} {n\choose r} = {n\choose 0} + {n\choose 1} + \cdots + {n\choose n}</math>

(증명)

<math>(1+x)^n=\sum_{r=0}^{n} {n\choose r}x^r = {n\choose 0} + {n\choose 1}x + \cdots + {n\choose r}x^r + \cdots + {n\choose n}x^n</math>

<math>x=1</math>을 대입 ■


<math>n 2^{n-1}= \sum_{r=0}^{n} r {n\choose r}=0 {n\choose 0} + 1 {n\choose 1} + \cdots + r {n\choose r} + \cdots + n {n\choose n}</math>

  • 예:<math>80= 5 \times 2^4 = 0 {5\choose 0} + 1 {5\choose 1} + 2 {5\choose 2} +3 {5\choose 3} +4 {5\choose 4} + 5 {5\choose 5}</math>



파스칼의 삼각형



이항계수의 q-analogue

  • q-이항계수와 q-이항정리 항목 참조
  • 팩토리얼(factorial)의 q-analogue:<math>[n]_q!= [1]_q [2]_q \cdots [n-1]_q [n]_q=\frac{1-q}{1-q} \frac{1-q^2}{1-q} \cdots \frac{1-q^{n-1}}{1-q} \frac{1-q^n}{1-q} =\frac{(q;q)_n}{(1-q)^n}=\frac{(1-q)_q^n}{(1-q)^n}</math>:<math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math>:<math>{{[n]_q!} \over {[r]_q![n - r]_q!}}=\frac{(q;q)_n}{(q;q)_r(q;q)_{n-r}}=\frac{(1-q)_q^n}{(1-q)_q^r (1-q)_q^{n-r}}</math>



역사



메모

관련된 항목들



수학용어번역



사전 형태의 자료



관련논문



블로그

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'binomial'}, {'LEMMA': 'coefficient'}]
  • [{'LOWER': 'n'}, {'LOWER': 'choose'}, {'LEMMA': 'k'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=이항계수와_조합&oldid=52442"