07 Advanced Counting Methods Free Online FlashCards

What does $\binom{n}{k}$ count?

a binomial coefficient

$\binom{n}{k}$

counts the unordered $k$-element subsets of an $n$-element set, where $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

State the symmetry identity for binomial coefficients.

Symmetry gives $\binom{n}{k}=\binom{n}{n-k}$, because choosing the selected objects is equivalent to choosing the objects left out.

What is Pascal's identity?

Pascal's identity is $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. It separates selections according to whether a distinguished object is chosen.

How many selections with repetition are possible?

The number of ways to select $k$ objects from $n$ types when repetition is allowed is $\binom{n+k-1}{k}$.

State the binomial theorem.

The binomial theorem states $(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k$ for nonnegative integer $n$.

How do you extract a coefficient from $(x+y)^n$?

The coefficient of $x^{n-k}y^k$ in $(x+y)^n$ is $\binom{n}{k}$. For example, the coefficient of $x^5y^3$ in $(x+y)^8$ is $\binom{8}{3}=56$.

What is inclusion-exclusion for two sets?

For two finite sets, $|A\cup B|=|A|+|B|-|A\cap B|$. The intersection is subtracted because it was counted twice.

What sign pattern does three-set inclusion-exclusion use?

For three sets, add single-set sizes, subtract pairwise intersections, then add the triple intersection: $|A\cup B\cup C|=\sum|A|-\sum|A\cap B|+|A\cap B\cap C|$.

How does inclusion-exclusion count objects avoiding all restrictions?

If $A_i$ is the set violating restriction $i$, then valid objects number $|S|-|\bigcup_i A_i|$, equivalently $|\bigcap_i A_i^c|$.

What formula counts derangements?

The number of derangements of $n$ objects is $D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$, and approximately $\frac{n!}{e}$.

What makes a recurrence-based counting argument complete?

A complete recurrence description needs initial conditions, a recurrence relation, and a justification based on an exhaustive, disjoint case partition.

What recurrence counts binary strings with no consecutive 1s?

For binary strings with no consecutive 1s, $a_n=a_{n-1}+a_{n-2}$, with $a_0=1$ and $a_1=2$. The cases end in 0 or in 01.