06 Fundamental Counting Principles Free Online FlashCards

When does the addition principle apply?

Add the counts of mutually exclusive cases. If one case has $a$ outcomes and another has $b$, the total is $a+b$.

When does the multiplication principle apply?

Multiply the numbers of choices at each stage. For stages with $a_1,a_2,\ldots,a_k$ choices, the total is $a_1a_2\cdots a_k$.

What is the definition of $n!$?

For a nonnegative integer $n$, $n!=n(n-1)\cdots2\cdot1$, and $0!=1$.

What formula counts ordered selections of $r$ from $n$?

The number of ordered selections of $r$ distinct objects from $n$ is $P(n,r)=\frac{n!}{(n-r)!}$.

How are arrangements with identical repeated objects counted?

Distinct arrangements of repeated objects are counted by dividing $n!$ by the factorial of each repetition count: $\frac{n!}{r_1!r_2!\cdots r_k!}$.

What formula counts unordered selections?

A combination is an unordered selection. The number of ways to choose $r$ objects from $n$ is $\binom{n}{r}=\frac{n!}{r!(n-r)!}$.

How are permutations and combinations related?

Each combination of $r$ objects has $r!$ orderings, so $P(n,r)=\binom{n}{r}r!$.

What does the pigeonhole principle guarantee?

If more than $m$ objects are placed into $m$ boxes, at least one box contains at least two objects.

What is the generalized pigeonhole bound?

If $n$ objects are distributed among $m$ boxes, some box contains at least $\left\lceil\frac{n}{m}\right\rceil$ objects.

How many 5-digit codes meet the stated no-repeat restriction?

There are $9\cdot9\cdot8\cdot7\cdot6=27{,}216$ such codes: 9 choices for the first digit, then 9, 8, 7, and 6.

How many 4-person committees exclude a particular pair together?

Count all committees and subtract those containing both people: $\binom{10}{4}-\binom{8}{2}=210-28=182$.

How many arrangements keep A and B adjacent?

Treat A and B as one block: $4!$ arrangements of the block with C, D, and E, times $2!$ internal orders. The total is $4!\cdot2!=48$.