Home › GATE CSE › computerscience › Discrete Mathematics › $\binom{n}{k} = \binom{n}{n-k}$. This identity r…
$\binom{n}{k} = \binom{n}{n-k}$. This identity reflects
APascal's identity
Bthe symmetry of binomial coefficients
Cthe multiplication principle
Dthe inclusion-exclusion principle
Answer & Solution
Correct answer: B. the symmetry of binomial coefficients
1. SYMMETRY of binomial coefficients: choosing $k$ from $n$ to INCLUDE is equivalent to choosing $n-k$ to EXCLUDE.
2. So both sides count the same thing — they must be equal.
3. Algebraic verification: $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$ and $\binom{n}{n-k} = \dfrac{n!}{(n-k)!\,k!}$. Identical.
4. Pascal's identity (option A) is the different statement $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$.
5. Options C, D refer to other counting principles.
_Source: Oscar Levin, "Discrete Mathematics: An Open Introduction", §1.2 (Binomial Coefficients — Pascal's Triangle and symmetry)._
Related questions
A PREDICATE $P(x)$ isHow many ways to put 10 IDENTICAL balls into 4 DISTINCT boxes (each box can hold 0 or moreHow many DIFFERENT subsets of size 3 can be selected from a set of 7 elements?In how many ways can 7 people sit in a ROW?How many DIFFERENT 5-bit binary strings are there?The PIGEONHOLE PRINCIPLE states that if $n$ pigeons are placed into $m$ holes with $n > m$A function $f: A \to B$ is INJECTIVE (one-to-one) if$|A \cup B|$ (size of union) equals