"이항계수와 조합"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
 
(사용자 2명의 중간 판 18개는 보이지 않습니다)
1번째 줄: 1번째 줄:
−
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">이 항목의 스프링노트 원문주소</h5>
+
==개요==
  
−
 
+
*  n개의 서로 다른 물건에서 r개를 선택하는 방법:<math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math>
 +
*  조합(combination)이라고도 함
 +
*  조합수학에서 가장 기본적이며 중요한 수열의 하나
 +
*  중요한 성질
 +
**  palindromic
 +
**  unimodality
  
−
 
+
  
−
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">개요</h5>
+
  
−
*  n개의 서로 다른 물건에서 r개를 선택하는 방법<br><math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math><br>
+
==생성함수==
−
*  고교수학에서 조합(combination)이라는 개념으로 등장<br>
 
−
*   <br>
 
  
−
 
+
* [[생성함수]]:<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>
  
−
 
+
  
−
<h5 style="margin: 0px; line-height: 2em;">생성함수</h5>
+
  
−
* [[생성함수]]<br><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><br>
+
==점화식==
  
−
 
+
*  n에 대한 이항계수를 통해, <math>n+1</math>에 대한 이항계수를 유도할 수 있음:<math>{n\choose r-1}+{n\choose r}={n+1\choose r}</math>
  
−
 
+
  
−
 
+
  
−
<h5 style="margin: 0px; line-height: 2em;">이항계수의 합</h5>
+
  
−
<math>2^n=\sum_{r=0}^{n} {n\choose r} = {n\choose 0} + {n\choose 1} + \cdots + {n\choose n}</math>
+
==이항계수의 합==
−
 
 
−
<math>n(1+1)^{n-1}=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>
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
고교수학에 조합(combination)이라는 개념이 있다. 1부터 42 까지 숫자 중에서 6개를 뽑는 방법의 수를 세는 것 같은 상황에서 쓰는 개념이 조합이다. n개의 서로 다른 물건에서 r개를 선택하는 방법은
 
−
 
 
−
<math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math>
 
−
 
 
−
으로 주어진다.
 
−
 
 
−
내가 고딩일 때 배울때는 <math>_n C_r</math> 라는 기호로 배웠지만, 대학에 와서 지금까지 공부를 하다보니, 업계의 선수들은 <math> {n\choose r}</math> 라는 기호를 더 애용하니, 여기서는 그렇게 쓰도록 하겠다.
 
−
 
 
−
이렇게 조합을 정의하고 나면, 꼭 나오는 문제 중에 이런게 있다.
 
−
 
 
−
<math>\sum_{r=0}^{n} {n\choose r} = {n\choose 0} + {n\choose 1} + \cdots + {n\choose n}</math>
 
−
 
 
−
을 계산하라.
 
−
 
 
−
가령 n=5 라고 한다면, 1부터 5까지 중에서 0개 뽑는 법, 1개 뽑는 법, …. 5개 뽑는법 다 더하면 얼마인가 묻는건데, 1+5+10+10+5+1=32 됨을 확인할 수 있다. 문제를 잘 들여다 보면, 결국 다섯개 원소를 갖는 집합의 부분집합의 개수는 모두 얼마인가 하는 문제와 같다는 것을 알 수 있다. 그러므로, 1이 들어가는 경우 안들어가는 경우, 2가 들어가는 경우 안들어가는 경우, …, 5개 들어가는 경우 안들어가는 경우 해서 모두 <math>2^5</math>가 되는 것이다.
 
−
 
 
−
일반적인 n에 대해서도 마찬가지로 답은 <math>2^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>
 
−
 
 
−
이 식에다가 x=1을 대입하면, 곧바로
 
  
 
<math>2^n=\sum_{r=0}^{n} {n\choose r} = {n\choose 0} + {n\choose 1} + \cdots + {n\choose n}</math>
 
<math>2^n=\sum_{r=0}^{n} {n\choose r} = {n\choose 0} + {n\choose 1} + \cdots + {n\choose n}</math>
  
−
이 됨을 알 수 있다.
+
(증명)
−
 
 
−
여기서 눈을 바로 뜨고 보아야 할 핵심은 자연수의 더하기 문제에다가 함수를 끌어들였다는 것이다. 이러한 생각의 파워를 느끼기 위해서는 다음과 같은 문제를 생각해 볼 필요가 있다.
 
−
 
 
−
<math>\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>
 
−
 
 
−
는 얼마인가?
 
−
 
 
−
n=5 인 경우에 대해서 노가다 계산을 해보면,
 
−
 
 
−
<math>\sum_{r=0}^{5} r {5\choose r} = 0 {5\choose 0} + 1 {5\choose 1} + 2 {5\choose 2} +3 {5\choose 3} +4 {5\choose 4}  + 5 {5\choose 5} =0+5+20+30+20+5=80</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>(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(1+x)^{n-1}=\sum_{r=0}^{n} r {n\choose r}x^{r-1} =0 {n\choose 0} + 1 {n\choose 1} + \cdots + r {n\choose r}x^{r-1} + \cdots + n {n\choose n}x^{n-1}</math>
+
  
−
을 얻고, 여기에 x=1을 대입할 경우,
+
<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>n(1+1)^{n-1}=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>
  
−
을 얻게 된다. n=5를 넣어보면, 다시
+
  
−
<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>
+
   
  
−
를 얻을 수 있다.
+
==파스칼의 삼각형==
  
−
더하기 문제에다가 함수를 끌어들여서 미분 적분의 파워를 활용하는 것이 이 방법론의 핵심이다. 아이디어가 쌈빡하지 않은가??
+
* [[파스칼의 삼각형]]
−
 
 
−
상황을 좀더 일반화 해서 요약을 하자면 다음과 같다.
 
−
 
 
−
'''1. 수열 <math>\{a_r\}</math>이 주어져 있다.'''(유한수열일 수도 있고, 무한수열 일수도 있다)<br> 위에서 다뤘던 경우는 수열이
 
−
 
 
−
<math>a_r = {n \choose r}</math>
 
−
 
 
−
로 정의된 유한수열이다.
 
−
 
 
−
'''<br> 2. 수열을 이용해서 다음과 같은 멱급수함수를 하나 만든다.''' (유한수열이면 다항식)
 
−
 
 
−
<math>f(x)=\sum_{r=0}^{\infty} a_r x^r</math>
 
−
 
 
−
그래서 우리의 경우는
 
−
 
 
−
<math>f(x)= {n\choose 0} + {n\choose 1}x + \cdots + {n\choose r}x^r + \cdots + {n\choose n}x^n</math>
 
−
 
 
−
를 만들었다.
 
−
 
 
−
'''3. 함수를 구한다.'''
 
−
 
 
−
우리의 경우에는 함수가
 
−
 
 
−
<math> f(x)=(1+x)^n</math>
 
−
 
 
−
이 된다.
 
  
−
 
+
  
−
<h5>재미있는 사실</h5>
+
  
−
 
+
==이항계수의 q-analogue==
  
−
* 네이버 지식인 http://kin.search.naver.com/search.naver?where=kin_qna&query=
+
* [[q-이항정리|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>
  
−
 
+
  
−
 
+
  
−
<h5>역사</h5>
+
==역사==
  
−
* [[수학사연표 (역사)|수학사연표]]
+
* [[수학사 연표]]
  
−
 
+
  
−
 
+
  
−
<h5>메모</h5>
+
==메모==
  
−
 
+
  
−
 
+
  
−
<h5>관련된 항목들</h5>
+
==관련된 항목들==
  
 
* [[파스칼의 삼각형]]
 
* [[파스칼의 삼각형]]
 +
* [[중복조합의 공식 H(n,r) =C(n+r-1,r)|중복 조합의 공식 H(n,r) =C(n+r-1,r)]]
  
−
 
+
  
−
 
+
  
−
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">수학용어번역</h5>
+
==수학용어번역==
  
 
* http://www.google.com/dictionary?langpair=en|ko&q=
 
* http://www.google.com/dictionary?langpair=en|ko&q=
−
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]<br>
+
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
−
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
+
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
  
−
 
+
  
−
 
+
  
−
<h5>사전 형태의 자료</h5>
+
==사전 형태의 자료==
  
−
* http://ko.wikipedia.org/wiki/
+
* [http://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98 http://ko.wikipedia.org/wiki/이항계수][http://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98http://en.wikipedia.org/wiki/binomial_coefficient ]
−
* http://en.wikipedia.org/wiki/
+
* http://en.wikipedia.org/wiki/binomial_coefficient
 
* http://www.wolframalpha.com/input/?i=
 
* http://www.wolframalpha.com/input/?i=
 +
* http://mathworld.wolfram.com/BinomialSums.html
 
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
 
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
−
* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]<br>
+
* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]
 
** http://www.research.att.com/~njas/sequences/?q=
 
** http://www.research.att.com/~njas/sequences/?q=
  
−
 
+
  
−
 
+
  
−
<h5>관련논문</h5>
+
==관련논문==
  
 
* http://www.jstor.org/action/doBasicSearch?Query=
 
* http://www.jstor.org/action/doBasicSearch?Query=
 
* http://dx.doi.org/
 
* http://dx.doi.org/
 +
  
−
 
+
   
−
 
+
   
−
<h5>관련도서 및 추천도서</h5>
 
−
 
 
−
* 도서내검색<br>
 
−
** http://books.google.com/books?q=
 
−
** http://book.daum.net/search/contentSearch.do?query=
 
−
* 도서검색<br>
 
−
** http://books.google.com/books?q=
 
−
** http://book.daum.net/search/mainSearch.do?query=
 
−
** http://book.daum.net/search/mainSearch.do?query=
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
<h5>관련기사</h5>
 
−
 
 
−
*  네이버 뉴스 검색 (키워드 수정)<br>
 
−
** http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
 
−
** http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
 
−
** http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
 
−
 
 
−
 
 
  
−
 
+
==블로그==
  
−
<h5>블로그</h5>
+
* [http://bomber0.byus.net/index.php/2007/09/30/452 고교 수학의 명장면 (2)]
−
 
 
−
* [http://bomber0.byus.net/index.php/2007/09/30/452 고교 수학의 명장면 (2)]<br>
 
 
** 피타고라스의 창, 2008-9-30
 
** 피타고라스의 창, 2008-9-30
−
*  구글 블로그 검색<br>
+
*  구글 블로그 검색
 
** [http://blogsearch.google.com/blogsearch?q=%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98 http://blogsearch.google.com/blogsearch?q=이항계수]
 
** [http://blogsearch.google.com/blogsearch?q=%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98 http://blogsearch.google.com/blogsearch?q=이항계수]
−
** http://blogsearch.google.com/blogsearch?q=
+
[[분류:조합수학]]
−
* [http://navercast.naver.com/science/list 네이버 오늘의과학]
+
[[분류:수열]]
−
* [http://math.dongascience.com/ 수학동아]
+
 
−
* [http://www.ams.org/mathmoments/ Mathematical Moments from the AMS]
+
==메타데이터==
−
* [http://betterexplained.com/ BetterExplained]
+
===위키데이터===
 +
* ID :  [https://www.wikidata.org/wiki/Q209875 Q209875]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'binomial'}, {'LEMMA': 'coefficient'}]
 +
* [{'LOWER': 'n'}, {'LOWER': 'choose'}, {'LEMMA': 'k'}]

2021년 2월 17일 (수) 05:57 기준 최신판

개요

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



생성함수

  • 생성함수\[(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\]



점화식

  • n에 대한 이항계수를 통해, \(n+1\)에 대한 이항계수를 유도할 수 있음\[{n\choose r-1}+{n\choose r}={n+1\choose r}\]




이항계수의 합

\(2^n=\sum_{r=0}^{n} {n\choose r} = {n\choose 0} + {n\choose 1} + \cdots + {n\choose n}\)

(증명)

\((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\)

\(x=1\)을 대입 ■


\(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}\)

  • 예\[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}\]



파스칼의 삼각형



이항계수의 q-analogue

  • q-이항계수와 q-이항정리 항목 참조
  • 팩토리얼(factorial)의 q-analogue\[[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}\]\[_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}\]\[{{[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}}\]



역사



메모

관련된 항목들



수학용어번역



사전 형태의 자료



관련논문



블로그

메타데이터

위키데이터

Spacy 패턴 목록

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