순열과 조합Permutations & Combinations

메인 그리고 음료 — 곱의 법칙:

A main and a drink — multiplication principle:

$(1)$ $5! = 120$.

$(2)$ $\dfrac{6!}{4!} = 6 \times 5 = 30$ — 꼬리가 통째로 약분된다.

$(3)$ $_6\mathrm P_2 = 6 \times 5 = 30$ — $(2)$와 같은 계산이다: $\frac{n!}{(n-r)!}$의 정체가 "앞에서 $r$개만 곱하기"임을 보여 준다.

$(1)$ $5! = 120$.

$(2)$ $\dfrac{6!}{4!} = 6 \times 5 = 30$ — the tail cancels wholesale.

$(3)$ $_6\mathrm P_2 = 6 \times 5 = 30$ — the same computation as $(2)$: $\frac{n!}{(n-r)!}$ unmasked as "multiply just the first $r$ factors."

$5$개 중 $2$개를 뽑으면 자동으로 $3$개가 남는다 — 뽑기와 남기기의 일대일 대응이 $_n\mathrm C_r = {}_n\mathrm C_{n-r}$의 이유다.

Choosing $2$ of $5$ automatically leaves $3$ — the choose/leave correspondence is the reason $_n\mathrm C_r = {}_n\mathrm C_{n-r}$.

순열: $r$개의 자리를 차례로 채운다 — 첫 자리 $n$가지, 둘째 $n-1$가지, …, $r$번째 자리는 $n - (r-1) = n - r + 1$가지. 곱의 법칙으로

(뒤 등호는 분자 $n!$에서 쓰지 않은 꼬리 $(n-r)!$을 나눈 것). $\blacksquare$

조합: 같은 순열을 두 단계로 다시 센다 — 먼저 배열할 $r$개를 순서 없이 뽑고($_n\mathrm C_r$가지), 뽑힌 $r$개를 줄 세운다($r!$가지). 두 셈이 같은 대상을 세므로

핵심은 이중 세기 — 한 집합을 두 방법으로 세어 등식을 얻는 이 논법은 조합론의 주력 무기다.

채점 기준 (논리가 맞는 다른 풀이도 만점)

• 곱의 법칙 연쇄로 순열 (1점)
• 두 단계 재세기 설정 (1점)
• 나눗셈 결론 (1점)

Permutations: fill $r$ seats in turn — $n$ options, then $n-1$, …, with $n - (r-1) = n - r + 1$ for the $r$th seat. By the multiplication principle,

(the last equality divides $n!$ by its unused tail $(n-r)!$). $\blacksquare$

Combinations: recount those same permutations in two stages — select the $r$ objects without order ($_n\mathrm C_r$ ways), then line them up ($r!$ ways). Two counts of one set must agree:

The heart is double counting — counting one set two ways to force an equation: combinatorics' main weapon.

Rubric (any logically correct proof earns full credit)

• The multiplication-principle chain (1 pt)
• The two-stage recount setup (1 pt)
• The division conclusion (1 pt)

$(1)$ 회장과 부회장은 역할이 다르다 — 순열: $_7\mathrm P_2 = 7 \times 6 = 42$.

$(2)$ 대표 둘은 같은 자격 — 조합: $_7\mathrm C_2 = \dfrac{42}{2} = 21$.

같은 상황, 다른 질문 — 답이 정확히 $2!$배 차이 나는 것이 "순서 지우기"의 실물이다.

$(1)$ President and vice-president hold different roles — permutation: $_7\mathrm P_2 = 7 \times 6 = 42$.

$(2)$ Two delegates share one status — combination: $_7\mathrm C_2 = \dfrac{42}{2} = 21$.

Same setting, different question — and the answers differ by exactly $2!$: "erasing order" in the flesh.

묶음 기법: 두 사람을 한 덩어리로 묶으면 배열할 대상은 덩어리 $1$ + 나머지 $3$명 = $4$개 — $4! = 24$가지. 덩어리 안에서 두 사람의 순서가 $2! = 2$가지:

검산(여사건): 전체 $5! = 120$, 이웃하지 않는 경우는 $120 - 48 = 72$ — 나머지 $3$명을 먼저 세우고($3! = 6$) 그 사이·양끝 $4$자리에서 둘의 자리를 고르면 $_4\mathrm P_2 = 12$, $6 \times 12 = 72$ ✓ — 두 길이 만난다.

Gluing: bind the two into one block — now $4$ objects (the block + $3$ others) arrange in $4! = 24$ ways, with $2! = 2$ orders inside the block:

Check (complement): total $5! = 120$, so non-adjacent should be $72$ — seat the other $3$ first ($3! = 6$), then place the two into the $4$ gaps and ends: $_4\mathrm P_2 = 12$, giving $6 \times 12 = 72$ ✓ — two roads meet.

$n$개 중 $r$개를 뽑는 각 선택 $S$에, 뽑히지 않은 $n - r$개의 집합 $S^c$(여집합)를 짝지어 준다.

• 서로 다른 선택은 서로 다른 여집합을 가지므로 짝짓기는 일대일이고,
• 크기 $n-r$의 어떤 부분집합도 어떤 선택의 여집합이므로($S =$ 그 여집합) 빠짐이 없다.

즉 "$r$개 뽑기"들과 "$n-r$개 뽑기"들이 완전한 짝을 이룬다 — 개수가 같다:

공식 $\frac{n!}{r!(n-r)!}$의 대칭으로도 한 줄에 보이지만, 대응 논증은 이유를 준다 — 뽑는 행동과 남기는 행동이 같은 정보라는 것. 계산 없이 개수의 일치를 밝히는 이 수법(전단사 논증)은 조합론의 두 번째 주력 무기다.

채점 기준 (논리가 맞는 다른 풀이도 만점)

• 여집합 대응 설정 (1점)
• 일대일·빠짐없음 확인 (1점)
• 결론 (1점)

To each choice $S$ of $r$ objects from $n$, assign the set $S^c$ of the $n - r$ objects not chosen (the complement).

• Distinct choices have distinct complements, so the pairing is one-to-one, and
• every subset of size $n-r$ is some choice's complement (namely of $S =$ its own complement) — nothing is missed.

The "$r$-choices" and "$(n-r)$-choices" thus pair off perfectly — equal in number:

The formula $\frac{n!}{r!(n-r)!}$ shows the symmetry in one line, but the correspondence gives the reason — choosing and leaving carry the same information. Establishing equal counts without computing (a bijection argument) is combinatorics' second main weapon.

Rubric (any logically correct proof earns full credit)

• The complement correspondence (1 pt)
• One-to-one and onto verified (1 pt)
• Conclusion (1 pt)

꼭짓점 $2$개를 잇는 선분은 $_n\mathrm C_2$개 — 그중 이웃한 꼭짓점을 잇는 $n$개는 변이지 대각선이 아니다:

$n = 10$: $_{10}\mathrm C_2 - 10 = 45 - 10 = 35$.

검산(다른 세기): 각 꼭짓점에서 자신·이웃 둘을 뺀 $n - 3$개로 대각선을 그을 수 있고, 각 대각선이 두 번 세어지므로 $\frac{n(n-3)}2$ ✓ — 이중 세기가 또 한 번 두 길을 만나게 한다.

Segments joining $2$ vertices number $_n\mathrm C_2$ — but the $n$ joining adjacent vertices are sides, not diagonals:

$n = 10$: $_{10}\mathrm C_2 - 10 = 45 - 10 = 35$.

Check (another count): each vertex sends diagonals to all but itself and its two neighbors — $n-3$ of them — and each diagonal gets counted twice: $\frac{n(n-3)}2$ ✓ — double counting brings two roads together again.

경로 하나는 R 네 개와 U 세 개의 나열이다.

Each path is a string of four R's and three U's.

어떤 최단 경로든 오른쪽(R) $4$번, 위(U) $3$번 — 총 $7$걸음의 나열이고, 경로는 $7$자리 중 U가 설 $3$자리의 선택으로 완전히 결정된다:

같은 글자가 있는 순열로 읽어도 같다: $\dfrac{7!}{4!\,3!} = 35$ ✓.

기하의 경로가 문자열의 조합으로 번역되는 것 — "센다"는 것은 종종 "대응시킨다"는 것이다.

Every shortest path takes $4$ rights (R) and $3$ ups (U) — a string of $7$ steps, determined completely by choosing which $3$ of the $7$ positions hold U:

Reading it as a repeated-letter arrangement agrees: $\dfrac{7!}{4!\,3!} = 35$ ✓.

A geometric path translated into a combination of letters — to count is, often, to correspond.

L 둘과 E 둘이 각각 서로 같다. 다섯 글자가 모두 다르다면 $5! = 120$이지만, 같은 L끼리의 자리바꿈($2!$)과 같은 E끼리의 자리바꿈($2!$)은 구별되지 않는다:

조합 유도와 같은 원리 — 구별되지 않는 중복을 나눠 지운다. 검산: V의 자리 $5$가지 × 남은 $4$자리에서 L 두 자리 고르기 $_4\mathrm C_2 = 6$ → $30$ ✓ (E는 자동).

The two L's are identical, as are the two E's. Five distinct letters would give $5! = 120$, but swaps within the L's ($2!$) and within the E's ($2!$) are indistinguishable:

The same principle as the combinations derivation — divide out indistinguishable redundancy. Check: $5$ spots for V $\times$ $_4\mathrm C_2 = 6$ ways to place the L's among the rest → $30$ ✓ (the E's fill in automatically).

일렬이라면 $6!$이지만, 원탁에서는 모두가 한 자리씩 도는 회전 $6$가지가 같은 배치다:

같은 답의 다른 유도: 한 사람을 기준으로 고정해 회전을 없애면, 나머지 $5$명을 그 사람 기준의 자리에 배열하는 $5!$가지.

"대칭으로 나눈다"와 "대칭을 고정한다" — 같은 아이디어의 두 표현이고, 원순열 $(n-1)!$의 정체다.

In a row it would be $6!$, but at a round table the $6$ rotations of any arrangement are one seating:

Another derivation of the same answer: pin one person as the reference, killing rotation — then the other $5$ arrange relative to them in $5!$ ways.

"Divide by the symmetry" and "fix the symmetry" — two phrasings of one idea, and the identity of the circular-permutation count $(n-1)!$.

"적어도 하나"의 정면 돌파는 세 갈래 — 여사건은 한 갈래다.

Head-on, "at least one" splits three ways — the complement is one way.

여사건으로: 전체에서 "여학생 $0$명"(전원 남학생)을 뺀다.

검산(정면 돌파): 여 $1$·남 $2$: $4 \times 10 = 40$, 여 $2$·남 $1$: $6 \times 5 = 30$, 여 $3$: $4$ — 합 $74$ ✓.

세 갈래 셈과 한 번의 뺄셈이 같은 답 — "적어도"라는 말이 보이면 여사건부터 저울질하라.

Complement: subtract the all-boys selections from the total.

Check (head-on): $1$ girl·$2$ boys: $4 \times 10 = 40$; $2$·$1$: $6 \times 5 = 30$; $3$ girls: $4$ — total $74$ ✓.

Three cases versus one subtraction, same answer — when "at least" appears, weigh the complement first.

$n$명이 서로 한 번씩 악수하면 악수 수는 두 사람의 조합:

— $n > 0$이므로 $n = 12$.

검산: $_{12}\mathrm C_2 = \dfrac{12 \times 11}{2} = 66$ ✓.

세기가 만든 방정식을 인수분해가 푼다 — 조합론과 대수가 맞잡는 표준 장면이고, 대각선 공식($_n\mathrm C_2 - n$)과 함께 $_n\mathrm C_2$가 "쌍의 개수"의 보편 문법임을 보여 준다.

Among $n$ people, handshakes are pairs:

— and $n > 0$ gives $n = 12$.

Check: $_{12}\mathrm C_2 = \dfrac{12 \times 11}{2} = 66$ ✓.

Counting builds the equation; factoring solves it — a standard scene of combinatorics and algebra joining hands, and with the diagonal formula ($_n\mathrm C_2 - n$) it shows $_n\mathrm C_2$ as the universal grammar of "number of pairs."