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

수학노트
둘러보기로 가기 검색하러 가기
14번째 줄: 14번째 줄:
 
 
 
 
  
−
<h5 style="margin: 0px; line-height: 2em;">점화식</h5>
+
<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>
  
 
 
 
 
22번째 줄: 22번째 줄:
 
 
 
 
  
−
<h5 style="margin: 0px; line-height: 2em;">생성함수</h5>
+
<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>
+
<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 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>
  
 
 
 
 
  
−
<h5 style="margin: 0px; line-height: 2em;">이항계수의 합</h5>
+
<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>
+
* [[파스칼의 삼각형]]<br>
−
 
 
−
<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>
 
  
 
 
 
 
47번째 줄: 49번째 줄:
  
 
<math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math>
 
<math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math>
 +
 +
 
  
 
으로 주어진다.
 
으로 주어진다.
 +
 +
 
  
 
내가 고딩일 때 배울때는 <math>_n C_r</math> 라는 기호로 배웠지만, 대학에 와서 지금까지 공부를 하다보니, 업계의 선수들은 <math> {n\choose 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>
 
<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=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>이 된다.
 
일반적인 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>
 
<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을 대입하면, 곧바로
 
이 식에다가 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>
 
<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 인 경우에 대해서 노가다 계산을 해보면,
 
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>\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>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>
 
<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을 대입할 경우,
 
을 얻고, 여기에 x=1을 대입할 경우,
 +
 +
 
  
 
<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>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>
 +
 +
 
  
 
을 얻게 된다. n=5를 넣어보면, 다시
 
을 얻게 된다. 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>
 
<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> 위에서 다뤘던 경우는 수열이
 
'''1. 수열 <math>\{a_r\}</math>이 주어져 있다.'''(유한수열일 수도 있고, 무한수열 일수도 있다)<br> 위에서 다뤘던 경우는 수열이
 +
 +
 
  
 
<math>a_r = {n \choose r}</math>
 
<math>a_r = {n \choose r}</math>
 +
 +
 
  
 
로 정의된 유한수열이다.
 
로 정의된 유한수열이다.
 +
 +
 
  
 
'''<br> 2. 수열을 이용해서 다음과 같은 멱급수함수를 하나 만든다.''' (유한수열이면 다항식)
 
'''<br> 2. 수열을 이용해서 다음과 같은 멱급수함수를 하나 만든다.''' (유한수열이면 다항식)
 +
 +
 
  
 
<math>f(x)=\sum_{r=0}^{\infty} a_r x^r</math>
 
<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>
 
<math>f(x)= {n\choose 0} + {n\choose 1}x + \cdots + {n\choose r}x^r + \cdots + {n\choose n}x^n</math>
 +
 +
 
  
 
를 만들었다.
 
를 만들었다.
 +
 +
 
  
 
'''3. 함수를 구한다.'''
 
'''3. 함수를 구한다.'''
 +
 +
 
  
 
우리의 경우에는 함수가
 
우리의 경우에는 함수가
 +
 +
 
  
 
<math> f(x)=(1+x)^n</math>
 
<math> f(x)=(1+x)^n</math>
 +
 +
 
  
 
이 된다.
 
이 된다.
178번째 줄: 262번째 줄:
  
 
* http://ko.wikipedia.org/wiki/
 
* http://ko.wikipedia.org/wiki/
−
* 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://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
 
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]

2009년 12월 7일 (월) 12:03 판

이 항목의 스프링노트 원문주소

 

 

개요
  • n개의 서로 다른 물건에서 r개를 선택하는 방법
    \(_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}\)
  • 고교수학에서 조합(combination)이라는 개념으로 등장

 

 

생성함수
  • 생성함수
    \((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\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}\)

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

 

파스칼의 삼각형

 

 

 

고교수학에 조합(combination)이라는 개념이 있다. 1부터 42 까지 숫자 중에서 6개를 뽑는 방법의 수를 세는 것 같은 상황에서 쓰는 개념이 조합이다. n개의 서로 다른 물건에서 r개를 선택하는 방법은

\(_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}\)

 

으로 주어진다.

 

내가 고딩일 때 배울때는 \(_n C_r\) 라는 기호로 배웠지만, 대학에 와서 지금까지 공부를 하다보니, 업계의 선수들은 \( {n\choose r}\) 라는 기호를 더 애용하니, 여기서는 그렇게 쓰도록 하겠다.

 

이렇게 조합을 정의하고 나면, 꼭 나오는 문제 중에 이런게 있다.

 

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

 

을 계산하라.

 

가령 n=5 라고 한다면, 1부터 5까지 중에서 0개 뽑는 법, 1개 뽑는 법, …. 5개 뽑는법 다 더하면 얼마인가 묻는건데, 1+5+10+10+5+1=32 됨을 확인할 수 있다. 문제를 잘 들여다 보면, 결국 다섯개 원소를 갖는 집합의 부분집합의 개수는 모두 얼마인가 하는 문제와 같다는 것을 알 수 있다. 그러므로, 1이 들어가는 경우 안들어가는 경우, 2가 들어가는 경우 안들어가는 경우, …, 5개 들어가는 경우 안들어가는 경우 해서 모두 \(2^5\)가 되는 것이다.

 

일반적인 n에 대해서도 마찬가지로 답은 \(2^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을 대입하면, 곧바로

 

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

 

이 됨을 알 수 있다.

 

여기서 눈을 바로 뜨고 보아야 할 핵심은 자연수의 더하기 문제에다가 함수를 끌어들였다는 것이다. 이러한 생각의 파워를 느끼기 위해서는 다음과 같은 문제를 생각해 볼 필요가 있다.

 

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

 

는 얼마인가?

 

n=5 인 경우에 대해서 노가다 계산을 해보면,

 

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

 

과 같다.

 

위에서 언급한 식을 사용해 보자면,

 

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

 

을 얻고, 여기에 x=1을 대입할 경우,

 

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

 

을 얻게 된다. n=5를 넣어보면, 다시

 

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

 

를 얻을 수 있다.

 

더하기 문제에다가 함수를 끌어들여서 미분 적분의 파워를 활용하는 것이 이 방법론의 핵심이다. 아이디어가 쌈빡하지 않은가??

 

상황을 좀더 일반화 해서 요약을 하자면 다음과 같다.

 

1. 수열 \(\{a_r\}\)이 주어져 있다.(유한수열일 수도 있고, 무한수열 일수도 있다)
위에서 다뤘던 경우는 수열이

 

\(a_r = {n \choose r}\)

 

로 정의된 유한수열이다.

 


2. 수열을 이용해서 다음과 같은 멱급수함수를 하나 만든다. (유한수열이면 다항식)

 

\(f(x)=\sum_{r=0}^{\infty} a_r x^r\)

 

그래서 우리의 경우는

 

\(f(x)= {n\choose 0} + {n\choose 1}x + \cdots + {n\choose r}x^r + \cdots + {n\choose n}x^n\)

 

를 만들었다.

 

3. 함수를 구한다.

 

우리의 경우에는 함수가

 

\( f(x)=(1+x)^n\)

 

이 된다.

 

재미있는 사실

 

 

 

역사

 

 

메모

 

 

관련된 항목들

 

 

수학용어번역

 

 

사전 형태의 자료

 

 

관련논문

 

관련도서 및 추천도서

 

 

관련기사

 

 

블로그
원본 주소 "https://wiki.mathnt.net/index.php?title=이항계수와_조합&oldid=17086"