Counting Principles: Permutations, Combinations, and Binomial Coefficients TODO
Concept
Counting rests on two rules: mutually exclusive choices add (the sum rule), and independent sequential steps multiply (the product rule). The number of ways to pick k items from n, order-sensitive, is the permutation count n!/(n-k)!, and order-insensitive, it's the binomial coefficient C(n,k) = n!/(k!(n-k)!). The binomial coefficients are exactly the expansion coefficients of (x+y)^n, and Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) falls straight out of a combinatorial argument splitting on "cases that include a particular element vs. cases that don't." When repetition is allowed or conditions overlap, this extends to combinations with repetition and inclusion-exclusion, and counting problems are usually half-solved just by first defining what counts as "the same."
Real-world calculations like counting an algorithm's cases, estimating hash collision probability, or designing random sampling all rest on these basic rules, and getting them wrong throws off the entire probability estimate.
Code & Formula
# 카운팅 원리(순열·조합·이항계수) — nPr, nCr 을 직접 구현해 math.perm/math.comb 와 대조하고,
# 파스칼 항등식 C(n,k) = C(n-1,k-1) + C(n-1,k) 도 조합적으로 검증.
import math
from itertools import permutations, combinations
def n_perm(n, r):
return math.factorial(n) // math.factorial(n - r)
def n_comb(n, r):
return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
n, r = 8, 3
my_perm, my_comb = n_perm(n, r), n_comb(n, r)
print(f"P({n},{r}) 직접계산={my_perm} math.perm={math.perm(n, r)} 일치? {my_perm == math.perm(n, r)}")
print(f"C({n},{r}) 직접계산={my_comb} math.comb={math.comb(n, r)} 일치? {my_comb == math.comb(n, r)}")
# 실제로 나열해서 개수를 세어도 같은지 확인 (작은 n으로).
items = list(range(5))
listed_perm = len(list(permutations(items, 3)))
listed_comb = len(list(combinations(items, 3)))
print(f"\n{items} 에서 3개 뽑기: 나열해서 센 순열 수={listed_perm} (공식={n_perm(5,3)}), "
f"조합 수={listed_comb} (공식={n_comb(5,3)})")
# 파스칼 항등식: 특정 원소를 포함하는 경우(C(n-1,k-1)) + 포함하지 않는 경우(C(n-1,k))
for n in (6, 9, 12):
for k in range(1, n):
lhs = math.comb(n, k)
rhs = math.comb(n - 1, k - 1) + math.comb(n - 1, k)
assert lhs == rhs, f"파스칼 항등식 불일치: n={n}, k={k}"
print("\n파스칼 항등식 C(n,k)=C(n-1,k-1)+C(n-1,k) 모든 표본에서 성립 확인 완료.")
Exercise
Implement C(n,k) two ways — as DP on Pascal's identity, and via the multiplicative formula — compare how overflow and precision diverge for large n, and prove the identity by hand with a combinatorial argument.
Practical Connection
This is the most basic tool for counting outcome combinations in a prediction market, computing the probability that a set of nodes reaches quorum, or working the hash-collision birthday problem.
Where it lands in Jayverse
- Verex: compute multi-outcome market payout and outcome counts with the exact permutation and C(n,k) formulas here, not an approximation. An off-by-one in outcome counting directly misprices a market.
- Bridge: size relayer quorum thresholds, and OFA solver-set quorum, as a direct binomial-coefficient calculation. Not by picking a round number.
- CI: apply the birthday-problem bound from this page to any ID or hash scheme — market IDs, session-key nonces. This sizes the space needed for negligible collision probability.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| falls straight out of | ~에서 바로 도출된다 · "Pascal's identity ... falls straight out of a combinatorial argument" |
| split on | (경우를) ~ 기준으로 나누다 · "splitting on 'cases that include a particular element vs. cases that don't'" |
| half-solved | 절반은 해결된 것이나 다름없는 · "counting problems are usually half-solved just by first defining what counts as 'the same'" |
| throw off | (계산·추정을) 틀어지게 하다 · "getting them wrong throws off the entire probability estimate" |
| diverge | (값이) 서로 벌어지다, 갈라지다 · "compare how overflow and precision diverge for large n" |
| mutually exclusive | 상호 배타적인(동시에 일어날 수 없는) · "mutually exclusive choices add" |
| rest on | ~에 기반을 두다 · "Counting rests on two rules" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.