경우의 수 개념정리

원순열·중복순열·이항정리 · '순서냐 / 같은 걸 어찌 처리냐' 두 질문.

원순열중복순열같은것이있는순열중복조합이항정리파스칼삼각형

들어가기 전에 · 경우의 수는 결국 두 질문이에요

한줄핵심: 모든 세기 문제는 "순서를 따지나?"와 "같은 게 섞였나?" 두 질문으로 갈려요.

경우의 수를 어려워하는 이유는 공식이 많아 보여서예요. 하지만 출발점은 두 개뿐이에요.

순열( $_n\mathrm{P}_r$ ): 순서를 따져 줄을 세우기
조합( $_n\mathrm{C}_r$ ): 순서 없이 뽑기

이번 단원은 이 둘에 조건을 하나씩 비트는 변형이에요.

줄이 아니라 원형 → 원순열
다시 뽑기 가능 → 중복순열
대상 중에 똑같은 게 있음 → 같은 것이 있는 순열
중복 허용 + 순서 무시 → 중복조합

그래서 기준 상태에서 무엇이 다르고, 그걸 어떻게 처리하는가를 보면 돼요.

원순열 · 돌려서 같은 건 한 번만 세요

한줄핵심: 원형이면 회전해서 겹치는 $n$ 가지가 다 같으니, 일렬보다 $n$ 배 적어요.

일렬로 $n$ 명을 세우면 $n!$ 이에요. 그런데 원탁에 앉히면 'A-B-C-D'를 한 칸씩 돈 것들이 자리 모양은 똑같아요. 돌릴 수 있는 방향이 $n$ 가지니까, 일렬 배열 $n$ 개가 원형에서는 1개로 뭉쳐요.

$\text{원순열} = \frac{n!}{n} = (n-1)!$

더 쉬운 생각법: 한 사람을 고정해 버려요. 그 사람을 기준으로 나머지 $n-1$ 명을 줄 세우면 $(n-1)!$ . 이 "한 명 고정" 발상이 원순열의 핵심이에요.

주의: 뒤집어도 같다고 보면(목걸이·팔찌) 한 번 더 2로 나눠 $\dfrac{(n-1)!}{2}$ 이 돼요.

중복순열 · 다시 뽑아도 되면 그냥 곱하기예요

한줄핵심: 매 자리마다 후보가 항상 $n$ 개이니, 곱하면 끝이에요.

순열은 한 번 뽑은 걸 못 써서 후보가 줄었어요. 중복을 허용하면(비밀번호·신호기) 매 자리 후보가 계속 $n$ 개예요.

$_n\Pi_r = n^r$

여기서 $r$ 이 $n$ 보다 커도 된다는 게 포인트예요. 5개 중 7개를 뽑는 것도 가능하거든요.

자주 헷갈리는 함정 · 함수의 개수예요. 집합 $X$ (원소 $a$ 개)에서 $Y$ (원소 $b$ 개)로 가는 함수는 $b^a$ 개예요. '보내지는 쪽 후보수) $^{(\text{보내는 쪽 개수})}$ ' · 정의역이 지수가 아니에요.

같은 것이 있는 순열 · 일단 다 다르다 치고, 같은 만큼 나눠요

한줄핵심: 모두 다르다고 $n!$ 로 센 뒤, 똑같은 것끼리 자기들끼리 섞은 경우의 수로 나눠요.

'banana'를 배열하는 예를 생각해 봐요. a가 3개, n이 2개 섞여 있어요. a 세 개는 자리만 바뀌어도 글자로는 구별이 안 돼요. 그래서 과하게 센 만큼 나눠줘야 해요.

$\frac{n!}{p!\,q!\,r!\cdots} \quad (p+q+r+\cdots = n)$

'banana'는 $\dfrac{6!}{3!\,2!\,1!} = 60$ 가지예요.

이 논리가 진짜 중요한 이유는 최단경로 문제예요. 가로 3칸·세로 2칸을 가려면 오른쪽 R 3번, 위 U 2번을 섞는 방법은 $\dfrac{5!}{3!\,2!} = 10$ 가지. 최단경로를 보면 이 공식을 떠올리세요.

중복조합 · 칸막이로 바꾸면 결국 조합이에요

한줄핵심: 중복조합은 "별과 칸막이"로 번역되고, 그 순간 조합이 돼요.

중복조합 $_n\mathrm{H}_r$ 은 서로 다른 $n$ 종류에서 중복을 허용하고 순서 없이 $r$ 개를 뽑는 거예요. 3종류 과일에서 5개를 고르는데 같은 과일 여러 개 OK인 경우죠.

핵심 발상은 "별 $\bigstar$ 와 칸막이 $|$ "예요. 고른 $r$ 개를 별로, 종류를 가르는 경계를 막대로 표현해요. $n$ 종류로 나누려면 칸막이가 $n-1$ 개 필요해요. 그러면 별 $r$ 개와 막대 $n-1$ 개, 합쳐서 총 자리 중 어디에 막대를 놓을지만 정하면 돼요.

$_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$

활용이 진짜 중요해요. 방정식 $x+y+z = 5$ 의 음이 아닌 정수해 개수가 $_3\mathrm{H}_5 = 21$ 이에요. 양의 정수 조건이면 각각에 1개씩 미리 깔고 $_3\mathrm{H}_2 = 6$ 으로 바꿔요.

이항정리와 파스칼 삼각형 · 조합이 곧 전개 계수예요

한줄핵심: $(a+b)^n$ 을 펼칠 때 각 항의 계수가 바로 **조합 $_n\mathrm{C}_r$ **예요.

$(a+b)^n = (a+b)(a+b)\cdots(a+b)$ 는 괄호 $n$ 개의 곱이에요. 전개하면 각 괄호에서 $a$ 또는 $b$ 를 하나씩 골라 곱한 거죠. $a^{n-r}b^r$ 항이 나오려면 $n$ 개 괄호 중 $b$ 를 고를 $r$ 개를 정해야 하는데, 그 방법이 $_n\mathrm{C}_r$ 가지예요.

$(a+b)^n = \sum_{r=0}^{n} {}_n\mathrm{C}_r\, a^{n-r} b^r$

파스칼 삼각형의 핵심 성질은 $_{n}\mathrm{C}_{r} = {}_{n-1}\mathrm{C}_{r-1} + {}_{n-1}\mathrm{C}_{r}$ 위 두 수를 더하면 아래 수가 돼요. 세기 논리가 곧 계산 규칙이 되는 거죠.

한 행의 합은 $a=b=1$ 을 넣으면 $\sum_{r=0}^{n} {}_n\mathrm{C}_r = 2^n$ 이에요.

한눈 요약 · 다섯 가지를 한 표로

한줄핵심: 새 공식 5개가 아니라, 순열·조합에서 조건 하나씩 비튼 5갈래예요.

무엇을 묻는지부터 분류하세요

순서 + 안 겹침 → 순열 $_n\mathrm{P}_r$
순서 + 원형 → 원순열 $(n-1)!$
순서 + 다시 뽑기 → 중복순열 $n^r$
순서 + 같은 것 → 같은 것이 있는 순열 $\dfrac{n!}{p!q!\cdots}$
순서 무시 + 다시 뽑기 → 중복조합 $_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$

핵심 정신: "기준 상태로 다 센 다음, 똑같이 세어진 만큼 나눈다." · 원순열(n으로), 같은 것(p!q!로), 중복조합(칸막이로) 전부 같은 맥락이에요.

풀이 꿀팁

🎯 출제 포인트 · 중복조합 = 방정식 정수해

중복조합은 거의 방정식 정수해 개수로 위장해서 나와요. $x+y+z=n$ 꼴이 보이면 바로 $_3\mathrm{H}_n = {}_{n+2}\mathrm{C}_2$ . 조건이 붙는 두 패턴만 기억하세요.

$x,y,z \ge 1$ (양의 정수): 각자 1개씩 미리 깔고 $_3\mathrm{H}_{n-3}$
$x \ge 2$ 처럼 하한이 다름: 그 변수에 미리 2개 깔고 남은 걸로 다시 중복조합

부등식 $x+y+z \le n$ 이면 **여유변수 $w \ge 0$ **를 더해 $x+y+z+w = n$ 등식으로 바꿔요( $_4\mathrm{H}_n$ ). 이 치환 한 방이면 거의 다 풀려요.

⚡ 빠른 풀이 · 이항계수는 작은 쪽으로

$_n\mathrm{C}_r = {}_n\mathrm{C}_{n-r}$ 이니까 항상 작은 아래첨자로 바꿔 계산하세요. $_{20}\mathrm{C}_{18}$ 을 정직하게 풀지 말고 $_{20}\mathrm{C}_2 = \dfrac{20 \cdot 19}{2} = 190$ . 중복조합도 마찬가지로 ${}_7\mathrm{C}_5 = {}_7\mathrm{C}_2 = 21$ 처럼 뒤집으면 암산권이에요. 특정 항 계수 문제는 일반항 $_n\mathrm{C}_r\,a^{n-r}b^r$ 만 세워 지수 조건으로 $r$ 부터 확정한 뒤 계수를 계산하면 전개 안 해도 돼요. 예: $\left(x^2+\dfrac{1}{x}\right)^6$ 의 상수항은 $2(6-r)-r=0 \Rightarrow r=4$ , 계수 $_6\mathrm{C}_4=15$ .

⚠️ 여기서 다 틀려 · 원순열 '한 명 고정' vs 함수 방향

두 군데서 점수가 갈려요.

원순열: $(n-1)!$ 로 시작하되, '특정 두 사람을 이웃'시키면 둘을 한 덩어리로 묶고 $(n-2)!$ , 묶음 내부 $2!$ 를 곱하기. 처음부터 $n!$ 쓰면 회전 중복이 안 빠져 틀려요.
함수의 개수: 정의역 $a$ 개 → 공역 $b$ 개일 때 함수는 $b^a$ , 일대일함수는 $_b\mathrm{P}_a$ , ( $a=b$ 일 때) 일대일대응은 $a!$ . "보내질 곳이 밑, 보내는 개수가 지수"로 외우고, $a^b$ 로 거꾸로 쓰지 마세요.

🧠 강의 꿀팁 · 'banana 정신'과 '별·칸막이'

두 그림만 머리에 박아두면 절반은 끝나요.

같은 것이 있는 순열 = banana: '다 다르다 치고 $n!$ → 같은 글자 개수의 팩토리얼로 나누기'. 최단경로가 보이면 무조건 이 공식 $\dfrac{(a+b)!}{a!\,b!}$ . 경유점·장애물이 있으면 '구간을 끊어서 곱'으로 처리해요.
중복조합 = 별과 칸막이: 고를 개수만큼 $\bigstar$ , 종류 가르는 막대 $n-1$ 개. 총자리 $(n+r-1)$ 중 막대 자리 고르기. 외울 게 아니라 그림 그리면 식이 저절로 나와요.

🎯 출제 포인트 · 이항계수 합 트릭 ($x$에 값 대입)

$_n\mathrm{C}_0 + {}_n\mathrm{C}_1 + \cdots + {}_n\mathrm{C}_n = ?$ 처럼 계수들의 합을 묻는 문제는, 이항정리 $(1+x)^n$ 에 $x$ 에 적당한 수를 대입하는 게 정석이에요.

$x=1$ 대입 → 전체 합 $= 2^n$
$x=-1$ 대입 → 교대합 $= 0$ (짝수항 합 = 홀수항 합)

두 식을 더하거나 빼면 '짝수 번째 계수의 합 $= 2^{n-1}$ ' 같은 결과가 바로 나와요. 일일이 계산하지 말고 대입 한 방으로 잡으세요.