Combination Counting: Binomial Coefficients, Repetition, and Grouping

All flashcards

How many ways are there to choose $k$ distinct items from $n$ items?

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

What is Pascal's recurrence for an interior binomial coefficient?

$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ for $0<k<n$.

How many ways are there to choose $k$ items from $n$ types when repetition is allowed and order is ignored?

$\binom{n+k-1}{k}$.

What does a multinomial coefficient count?

Allocations of distinct objects to labeled bins with specified bin sizes.

When is the probability of one particular selection equal to $1/\binom{n}{k}$?

When one of the $\binom{n}{k}$ possible selections is chosen uniformly at random.

Quiz questions

1. How many 3-person committees can be chosen from 8 people when order does not matter?Answer: $56$
2. What is the coefficient of $X^2$ in the expansion of $(1+X)^5$?Answer: $10$
3. Using complement symmetry, what is the value of $\binom{9}{7}$?Answer: $36$
4. A 4-card hand is selected uniformly at random from a standard 52-card deck. What is the probability of one specified hand?Answer: $\frac{1}{\binom{52}{4}}$
5. In how many ways can 6 distinct objects be placed into 3 labeled bins with exactly 2 objects in each bin?Answer: $90$