경우의 수

동그란 탁자에서는 자리를 한 칸씩 옮겨 앉아도 서로의 좌우 관계가 변하지 않아요.

돌려서 똑같아지는 배열이 정확히 n가지씩 생깁니다.

그래서 일렬 순열 n!을 n으로 나누어 (n-1)!이 돼요.

기호 Π는 그리스 문자 '파이(Pi)'의 대문자예요.

곱하기(Product)를 뜻하는 영단어의 앞 글자 P에 해당합니다.

매 자리마다 같은 수를 거듭하여 곱한다는 뜻이에요.

예제 1 (원순열과 이웃 조건): 부모님 2명과 자녀 3명(총 5명)이 원탁에 둘러앉을 때, 부모님이 이웃하여 앉는 경우의 수는?
→ 부모님 2명을 한 묶음으로 보면 총 4명을 원탁에 앉히는 원순열이므로 (4−1)! = 3! = 6가지입니다. 묶음 안에서 부모님이 자리를 바꾸는 경우가 2! = 2가지이므로, 구하는 경우의 수는 6 × 2 = 12가지입니다.

예제 2 (중복순열의 밑과 지수 구분): 서로 다른 편지 4통을 서로 다른 우체통 3개에 넣는 경우의 수는? (단, 빈 우체통이 있어도 됨)
→ 선택하는 주체(편지 4통)가 각각 3개의 우체통 중 하나를 고르므로, 첫째 편지 3가지 × 둘째 편지 3가지 × 셋째 편지 3가지 × 넷째 편지 3가지 = ₃Π₄ = 3⁴ = 81가지입니다.

예제 3 (같은 것이 있는 순열): 숫자 1, 1, 2, 2, 2, 3 총 6개를 일렬로 나열하여 만들 수 있는 여섯 자리 자연수의 개수는?
→ 전체 6개 중 1이 2개, 2가 3개, 3이 1개이므로 6! / (2! × 3! × 1!) = 720 / 12 = 60개입니다.

오른쪽으로 4칸, 위로 3칸 가야 목적지에 도착해요.

오른쪽 화살표 4개와 위쪽 화살표 3개를 나열하는 것과 같아요.

순서만 정하면 길이 결정되므로 같은 것 순열 공식과 일치합니다.

기호 H는 '동차(Homogeneous)'를 뜻하는 단어에서 따왔어요.

다항식에서 모든 항의 차수가 같을 때 동차식이라고 부릅니다.

문자들을 중복해서 뽑아 동차식을 만드는 데서 유래했어요.

식빵 하나를 세 조각으로 자르려면 칼질을 두 번만 하면 돼요.

구역을 n개로 나누려면 경계선은 n-1개면 충분합니다.

그래서 종류 수보다 1 작은 수만큼 칸막이를 씁니다.

예제 1 (음이 아닌 정수해 vs 양의 정수해): 방정식 x + y + z = 8의 해의 개수를 조건별로 구해 봅시다.
① 음이 아닌 정수해(x, y, z ≥ 0): 0이 되어도 되므로 서로 다른 문자 3개에서 중복을 허락해 8번을 뽑는 경우의 수와 같습니다. ₃H₈ = ₁₀C₈ = ₁₀C₂ = 45가지.
② 양의 정수(자연수)해(x, y, z ≥ 1): 각 문자가 최소 1 이상이어야 하므로 x = x′+1, y = y′+1, z = z′+1 (x′, y′, z′ ≥ 0)로 치환하면 x′ + y′ + z′ = 5가 됩니다. 따라서 ₃H₅ = ₇C₅ = ₇C₂ = 21가지입니다.

예제 2 (단조증가 함수의 개수): 정의역 X = {1, 2, 3}에서 공역 Y = {1, 2, 3, 4, 5}로의 함수 f 중 f(1) ≤ f(2) ≤ f(3)을 만족하는 함수의 개수는?
→ 등호가 포함되어 같은 함숫값을 중복해서 고를 수 있고, 뽑기만 하면 크기순으로 f(1), f(2), f(3)에 자동 배정되므로 공역 5개 중 중복을 허용해 3개를 뽑는 중복조합 ₅H₃ = ₇C₃ = 35가지입니다.

음이 아닌 정수는 0을 포함해요. 아무것도 받지 못하는 상자가 있어도 됩니다.

자연수는 1 이상이어야 해요. 빈 상자가 없어야 한다는 뜻이에요.

자연수해 문제는 미리 1개씩 나눠 주고 시작하면 쉽게 풀립니다.

여기서 '이항'은 항을 다른 변으로 옮긴다는 뜻이 아니에요.

두 개(二)의 항(項)으로 이루어진 식이라는 뜻입니다.

a+b처럼 항이 두 개인 식의 거듭제곱을 다루는 정리예요.

(a+b)ⁿ은 (a+b) 괄호가 n개 곱해진 식이에요.

aⁿ⁻ʳbʳ 항을 만들려면 괄호 n개 중 r개에서 b를 골라야 해요.

괄호를 고르는 방법의 수가 바로 조합 ₙCᵣ이 된답니다.

1단계 (일반항 세우기): (A + B)ⁿ의 일반항 ₙCᵣ Aⁿ⁻ʳ Bʳ을 적습니다.
2단계 (계수와 문자의 거듭제곱 분리): 숫자는 숫자끼리, 문자 x는 지수법칙으로 한데 묶어 (계수 부분) × x^(지수 식) 꼴로 정리합니다.
3단계 (r값 결정 및 대입): 원하는 차수와 지수 식이 같아지는 r을 구해 계수 부분에 대입합니다.

예제 1: (x + 2)⁵의 전개식에서 x³의 계수는?
→ 일반항은 ₅Cᵣ x⁵⁻ʳ 2ʳ = ₅Cᵣ 2ʳ x⁵⁻ʳ입니다. 5 − r = 3 ⇒ r = 2를 대입하면 계수는 ₅C₂ × 2² = 10 × 4 = 40입니다.

예제 2 (상수항 구하기): (x² + 1/x)⁶의 전개식에서 상수항은?
→ 1/x = x⁻¹이므로 일반항은 ₆Cᵣ (x²)⁶⁻ʳ (x⁻¹)ʳ = ₆Cᵣ x¹²⁻³ʳ입니다. 상수항은 x의 지수가 0일 때이므로 12 − 3r = 0 ⇒ r = 4입니다. 따라서 상수항은 ₆C₄ = ₆C₂ = 15입니다.

파스칼 삼각형에서 빗변을 따라 비스듬히 숫자들을 더해 내려가 봐요.

그 합이 마지막 수의 반대쪽 아래에 적혀 있어요.

묶인 모양이 꺾인 하키스틱 채를 꼭 닮아서 이런 이름이 붙었어요.

모든 사람이 자기 물건을 갖지 않고 남의 것을 갖는 경우예요.

선물 교환이나 자기 시험지를 피해 채점할 때 나와요.

공식을 외우기보다 수형도로 차근차근 세는 것이 안전합니다.

인원수가 같은 조는 아직 이름이 없어 서로 구별되지 않아요.

A조, B조처럼 이름표를 붙이기 전에는 순서가 없는 셈이에요.

그래서 자리바꿈으로 생기는 중복만큼 나누어 줍니다.

예제 1 (4명의 완전순열 수형도): 4명(A, B, C, D)이 각자 자기 모자를 벗어 섞은 뒤 임의로 하나씩 쓸 때, 4명 모두 남의 모자(a, b, c, d)를 쓰는 경우의 수는?
→ 첫 번째 사람 A가 쓸 수 있는 모자는 b, c, d의 3가지입니다. 만약 A가 b를 썼다면, (B, C, D)가 (a, d, c), (c, d, a), (d, a, c)를 쓰는 3가지 경우가 생깁니다. 대칭성에 의해 A가 c나 d를 쓸 때도 똑같이 3가지씩 나오므로 총 3 × 3 = 9가지입니다.

예제 2 (조 나누기와 분배): 서로 다른 6명의 학생을 2명, 2명, 2명의 3개 조로 나눈 뒤, 3개의 서로 다른 봉사 구역에 배정하는 경우의 수는?
→ ① 조 나누기(분할): 세 조의 인원수가 2명으로 모두 같아 조끼리 구별되지 않으므로 ₆C₂ × ₄C₂ × ₂C₂ × (1/3!) = 15가지.
→ ② 구역 배정(분배): 나누어진 3개 조를 서로 다른 3개 구역에 일렬 배정하므로 15 × 3! = 90가지입니다.

딱 두 가지만 물어보면 돼요. "순서가 있는가?" 그리고 "중복이 되는가?"

순서가 있고 중복 없으면 순열(P), 중복되면 중복순열(Π)이에요.

순서가 없고 중복 없으면 조합(C), 중복되면 중복조합(H)입니다.