경우의 수와 순열·조합 — 기본 개념 잡기
기본 개념 29개 · 교과서 흐름 순 · 개념마다 정의·공식·예시와 기출 해설 연결
확률과 통계(선택)
이 개념이 왜 생겼나 — 도박판의 셈에서 시작됐다. 1654년 도박을 즐기던 프랑스 귀족 슈발리에 드 메레는 '게임이 중간에 끊기면 판돈을 어떻게 나눠야 공정한가'를 파스칼에게 물었고, 파스칼은 페르마와 편지를 주고받으며 답을 찾았다 — 앞으로 일어날 수 있는 모든 경우를 빠짐없이, 겹치지 않게 세어 비교하는 것. 이 서신에서 확률론이 태어났고, '경우를 체계적으로 세는 기술'인 조합론이 그 뼈대가 됐다. 순열·조합의 공식들은 하나하나 세던 일을 곱셈 한 번으로 줄이는 압축 장치다.
지금 어디에 쓰이나 — 가능성의 개수를 재는 모든 곳의 언어다. 비밀번호가 몇 가지나 만들어지는지, 로또 당첨 확률이 얼마인지, 시험 일정이나 배송 경로를 몇 가지로 짤 수 있는지가 전부 경우의 수 계산이다. 보험료 산정, 암호의 안전성 평가, 유전자 조합의 예측, 알고리즘이 검토해야 할 후보의 개수 추정까지 — 셀 수 있어야 비교할 수 있고, 비교할 수 있어야 판단할 수 있다.
수능은 무엇을 묻나 — 조건이 붙은 상황에서 세는 방법을 고르는 능력이다. 순서를 따지는가(순열), 따지지 않는가(조합), 중복을 허용하는가(중복순열·중복조합)를 판별하고, 경우를 합의 법칙으로 나누고 단계를 곱의 법칙으로 이을 수 있는지 묻는다. 아래 개념들을 순서대로 읽으면 이에 대한 대비를 갖출 수 있다.
경우의 수와 합의 법칙·곱의 법칙
경우의 수
기출 3회
어떤 사건이 일어날 수 있는 모든 가짓수. 빠짐없이, 겹치지 않게 세는 것이 원칙이며, 나뭇가지 그림(수형도)이나 표로 직접 나열하는 것이 모든 공식의 출발점이다.
예시한 개의 주사위를 던질 때 짝수의 눈이 나오는 경우의 수는 $2,\ 4,\ 6$ 의 $3$
합의 법칙
기출 16회
두 사건이 동시에 일어나지 않을 때, 어느 한쪽이 일어나는 경우의 수는 각 경우의 수의 합 $m+n$ 이다. '또는'으로 이어지는 상황에서 경우를 나눠 세는 모든 풀이의 근거다.
사건 $A,\ B$ 가 동시에 일어나지 않으면 (경우의 수)$=m+n$
예시두 주사위의 눈의 합이 $4$ 인 경우 $3$가지, $5$ 인 경우 $4$가지 → 합이 $4$ 또는 $5$ 인 경우는 $3+4=7$가지
곱의 법칙
기출 12회
사건 $A$ 가 일어나는 각각의 경우에 대하여 사건 $B$ 가 일어날 수 있으면, 두 사건이 잇달아 일어나는 경우의 수는 곱 $m\times n$ 이다. '그리고'로 이어지는 단계별 선택에 쓴다.
(경우의 수)$=m\times n$
예시집에서 학교까지 길이 $3$가지, 학교에서 도서관까지 길이 $2$가지면 집에서 도서관까지 $3\times 2=6$가지
여사건의 경우의 수
기출 8회
구하려는 경우를 직접 세기 어려우면 전체에서 반대 경우를 뺀다. '적어도 하나'라는 조건이 붙으면 대부분 이 방법이 빠르다.
(사건 $A$ 의 경우의 수)$=$(전체 경우의 수)$-$($A$ 가 일어나지 않는 경우의 수)
예시두 주사위에서 적어도 하나가 $6$ 인 경우는 $36-5\times 5=11$가지
포함-배제의 원리
기출 1회
두 사건이 겹칠 수 있을 때는 각각을 더한 뒤 겹치는 부분을 한 번 뺀다 — 그대로 더하면 겹친 경우가 두 번 세어지기 때문이다.
$n(A\cup B)=n(A)+n(B)-n(A\cap B)$
예시$1$부터 $30$까지 중 $2$ 또는 $3$ 의 배수는 $15+10-5=20$개
순열
순열
기출 12회
서로 다른 $n$ 개에서 $r$ 개를 택하여 순서를 정해 나열하는 것. 첫 자리에 $n$ 가지, 다음 자리에 $n-1$ 가지…로 곱해 내려간다. 이웃하는 조건은 묶어서 한 덩어리로, 이웃하지 않는 조건은 나머지를 먼저 세우고 사이에 끼워 넣는 방식으로 처리한다.
${}_{n}\mathrm{P}_{r}=n(n-1)(n-2)\cdots(n-r+1)=\dfrac{n!}{(n-r)!}$, $\ n!=n(n-1)\cdots 2\cdot 1$
예시$5$명 중 $2$명을 뽑아 회장·부회장을 정하는 경우는 ${}_{5}\mathrm{P}_{2}=5\times 4=20$가지
원순열
기출 4회
서로 다른 $n$ 개를 원형으로 배열하는 경우의 수는 $(n-1)!$ 이다. 회전하면 같아지는 배열을 하나로 세기 위해, 한 명을 고정하고 나머지를 나열한다고 생각한다.
(원순열의 수)$=(n-1)!$
예시$4$명이 원탁에 둘러앉는 경우는 $(4-1)!=6$가지
중복순열
기출 9회
서로 다른 $n$ 개에서 중복을 허용하여 $r$ 개를 택해 나열하는 것. 각 자리마다 $n$ 가지씩 선택할 수 있으므로 $n^{r}$ 이다. 신호 만들기, 함수의 개수 세기에 연결된다.
${}_{n}\Pi_{r}=n^{r}$
예시$1,\ 2$ 두 숫자로 만들 수 있는 세 자리 문자열은 $2^{3}=8$가지
같은 것이 있는 순열
기출 10회
같은 것이 섞여 있으면 전체를 나열한 뒤 같은 것끼리 자리를 바꾼 중복만큼 나눈다. 최단 경로의 수를 셀 때도 가로·세로 이동의 나열로 보아 이 공식을 쓴다.
$n$ 개 중 같은 것이 각각 $p$ 개, $q$ 개, …일 때 $\dfrac{n!}{p!\,q!\cdots}$
예시$a,\ a,\ b,\ b,\ b$ 를 나열하는 경우는 $\dfrac{5!}{2!\,3!}=10$가지
조합
조합
기출 15회
서로 다른 $n$ 개에서 순서를 생각하지 않고 $r$ 개를 택하는 것. 순열에서 같은 구성의 $r!$ 가지 나열을 하나로 센 것이므로 순열을 $r!$ 로 나눈다.
${}_{n}\mathrm{C}_{r}=\dfrac{{}_{n}\mathrm{P}_{r}}{r!}=\dfrac{n!}{r!\,(n-r)!}$
예시$5$명 중 대표 $2$명을 뽑는 경우는 ${}_{5}\mathrm{C}_{2}=\dfrac{5\times 4}{2}=10$가지
조합의 성질
최근 5개년 직접 출제 없음
$r$ 개를 뽑는 것과 남길 $n-r$ 개를 정하는 것은 같은 일이므로 ${}_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r}$ 이다. 또 특정 하나를 포함하는 경우와 포함하지 않는 경우로 나누면 ${}_{n}\mathrm{C}_{r}={}_{n-1}\mathrm{C}_{r-1}+{}_{n-1}\mathrm{C}_{r}$ 이 성립한다.
${}_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r}$, $\ {}_{n}\mathrm{C}_{r}={}_{n-1}\mathrm{C}_{r-1}+{}_{n-1}\mathrm{C}_{r}$
예시${}_{10}\mathrm{C}_{8}={}_{10}\mathrm{C}_{2}=45$
중복조합
기출 11회
서로 다른 $n$ 개에서 중복을 허용하여 순서 없이 $r$ 개를 택하는 것. 방정식 $x_{1}+x_{2}+\cdots+x_{n}=r$ 의 음이 아닌 정수해의 개수와 같다 — 나눠 주기·배분 문제가 이 꼴로 귀결된다.
${}_{n}\mathrm{H}_{r}={}_{n+r-1}\mathrm{C}_{r}$
예시$x+y+z=2$ 의 음이 아닌 정수해는 ${}_{3}\mathrm{H}_{2}={}_{4}\mathrm{C}_{2}=6$개
순열과 조합의 활용
함수의 개수
기출 5회
정의역의 원소 하나하나에 공역의 원소를 대응시키는 선택의 문제로 본다. 아무 조건이 없으면 중복순열, 일대일이면 순열, $x_{1}\lt x_{2}$ 이면 $f(x_{1})\lt f(x_{2})$ 처럼 대소가 정해지면 조합, $f(x_{1})\le f(x_{2})$ 꼴이면 중복조합으로 센다.
$n(X)=a,\ n(Y)=b$ 일 때 함수 $b^{a}$개, 일대일함수 ${}_{b}\mathrm{P}_{a}$개, 증가 대응 ${}_{b}\mathrm{C}_{a}$개, $f(x_{1})\le f(x_{2})$ 꼴 ${}_{b}\mathrm{H}_{a}$개
예시$n(X)=2,\ n(Y)=3$ 이면 함수는 $3^{2}=9$개, 일대일함수는 ${}_{3}\mathrm{P}_{2}=6$개
이항정리
이항정리
기출 11회
$(a+b)^{n}$ 을 전개하면 각 항은 $n$ 개의 괄호에서 $b$ 를 몇 개 택했는가로 결정된다 — $b$ 를 $r$ 개 택하는 방법이 ${}_{n}\mathrm{C}_{r}$ 가지이므로 그 항의 계수가 ${}_{n}\mathrm{C}_{r}$ 이다. 특정 항의 계수는 일반항에 조건을 대입해 구한다.
$(a+b)^{n}=\displaystyle\sum_{r=0}^{n}{}_{n}\mathrm{C}_{r}\,a^{n-r}b^{r}$ · 일반항 ${}_{n}\mathrm{C}_{r}\,a^{n-r}b^{r}$
예시$(x+2)^{4}$ 에서 $x^{2}$ 의 계수는 ${}_{4}\mathrm{C}_{2}\times 2^{2}=6\times 4=24$
이항계수의 성질
최근 5개년 직접 출제 없음
이항정리에 $a=b=1$ 을 대입하면 이항계수의 총합이 $2^{n}$, $a=1,\ b=-1$ 을 대입하면 교대합이 $0$ 이 된다. 두 식을 더하고 빼면 짝수 번째 계수의 합과 홀수 번째 계수의 합이 각각 $2^{n-1}$ 임을 얻는다.
${}_{n}\mathrm{C}_{0}+{}_{n}\mathrm{C}_{1}+\cdots+{}_{n}\mathrm{C}_{n}=2^{n}$, $\ {}_{n}\mathrm{C}_{0}-{}_{n}\mathrm{C}_{1}+\cdots+(-1)^{n}{}_{n}\mathrm{C}_{n}=0$
예시${}_{5}\mathrm{C}_{0}+{}_{5}\mathrm{C}_{1}+\cdots+{}_{5}\mathrm{C}_{5}=2^{5}=32$
파스칼의 삼각형
최근 5개년 직접 출제 없음
이항계수를 $n$ 값별로 줄지어 쌓은 삼각형으로, 이웃한 두 수의 합이 바로 아래의 수가 된다. 이 규칙이 곧 ${}_{n-1}\mathrm{C}_{r-1}+{}_{n-1}\mathrm{C}_{r}={}_{n}\mathrm{C}_{r}$ 이다.
예시$1,\ 3,\ 3,\ 1$ 의 다음 줄은 $1,\ 4,\ 6,\ 4,\ 1$ — ${}_{3}\mathrm{C}_{1}+{}_{3}\mathrm{C}_{2}=3+3=6={}_{4}\mathrm{C}_{2}$
함께 쓰이는 다른 단원·기초 개념
확률의 기본 성질
기출 7회
모든 사건 $A$ 에 대하여 $0\le P(A)\le 1$ 이고, 전체 사건의 확률은 $1$, 절대로 일어나지 않는 사건의 확률은 $0$ 이다.
$0\le P(A)\le 1$, $\ P(S)=1$, $\ P(\varnothing)=0$
확률의 덧셈정리
기출 3회
두 사건 중 적어도 하나가 일어날 확률은 각 확률의 합에서 동시에 일어날 확률을 뺀 것이다. 배반사건이면 그대로 더한다.
$P(A\cup B)=P(A)+P(B)-P(A\cap B)$
여사건의 확률
기출 8회
사건 $A$ 가 일어나지 않을 확률은 $1-P(A)$ 다. '적어도' 유형에서 반대 사건으로 돌아 계산할 때 쓴다.
$P(A^{C})=1-P(A)$
조건부확률
기출 2회
사건 $A$ 가 일어났다는 조건 아래에서 사건 $B$ 가 일어날 확률로, 표본공간이 $A$ 로 줄어든 상태의 확률이다.
$P(B\mid A)=\dfrac{P(A\cap B)}{P(A)}$ $(P(A)\gt 0)$
복원추출
기출 1회
꺼낸 것을 다시 넣고 다음을 뽑는 방식. 매회의 조건이 같아지므로 같은 것을 다시 뽑을 수 있고, 각 회의 결과가 서로 영향을 주지 않는다.
표본평균
기출 1회
모집단에서 뽑은 크기 $n$ 의 표본의 평균 $\overline{X}$. 모평균이 $m$, 모분산이 $\sigma^{2}$ 이면 $\overline{X}$ 의 평균은 $m$, 분산은 $\dfrac{\sigma^{2}}{n}$ 이다.
$E(\overline{X})=m$, $\ V(\overline{X})=\dfrac{\sigma^{2}}{n}$
약수와 배수의 성질
기출 2회
$a$가 $b$의 배수라는 것은 $a=bk$인 정수 $k$가 있다는 뜻이다. 배수 조건이 붙은 경우의 수 문제에서는 배수 판정(예: $3$의 배수는 각 자리 숫자의 합이 $3$의 배수)으로 경우를 나눈다.
예시세 자리 수가 $5$ 의 배수 → 일의 자리가 $0$ 또는 $5$
나머지에 따른 수의 분류
기출 2회
정수를 어떤 수로 나눈 나머지에 따라 묶으면 전체가 겹침 없이 나뉜다. 홀수·짝수 분류가 대표적이며, 합이나 곱의 조건이 붙은 세기 문제에서 경우를 나누는 기준이 된다.
예시$3$ 으로 나눈 나머지로 정수는 $3k,\ 3k+1,\ 3k+2$ 세 부류로 나뉜다
다항식의 전개와 인수분해
기출 2회
다항식의 곱은 분배법칙에 따라 각 괄호에서 항을 하나씩 택해 곱한 것들의 합으로 전개된다 — 전개식의 항의 개수 자체가 곱의 법칙이다.
예시$(a+b)(x+y+z)$ 의 전개식의 항은 $2\times 3=6$개
지수법칙
기출 1회
밑이 같은 거듭제곱의 곱셈·거듭제곱은 지수의 덧셈·곱셈으로 계산한다. 중복순열 $n^{r}$ 꼴의 정리에 쓰인다.
$a^{m}a^{n}=a^{m+n}$, $\ (a^{m})^{n}=a^{mn}$
합성함수
기출 2회
$(g\circ f)(x)=g(f(x))$ — 한 함수의 출력을 다른 함수의 입력으로 넣는 것. 합성 조건이 붙은 함수의 개수 문제에서는 안쪽 함수의 치역이 바깥쪽 함수의 입력이 된다는 점을 쓴다.
예시$f(x)=x+1,\ g(x)=2x$ 이면 $(g\circ f)(1)=g(2)=4$
치역
기출 1회
함수의 함숫값 전체의 집합으로, 공역의 부분집합이다. 치역이 지정된 함수의 개수 문제는 공역의 원소가 빠짐없이 대응되는지를 따진다.
수열의 귀납적 정의
기출 1회
첫째항과 이웃 항 사이의 관계식으로 수열을 정의하는 방법. 경우의 수에서는 $n$ 단계의 답을 앞 단계의 답으로 나타내는 관계식을 세워 차례로 계산할 때 쓴다.
예시$a_{1}=1,\ a_{n+1}=2a_{n}$ 이면 $a_{2}=2,\ a_{3}=4$