Counting principles, permutations, and combinations from an intro discrete mathematics course.
34 cards · basic cards · AI-written, checked twice. Edit anything.
- What is the addition principle (rule of sum)?
- If two tasks are mutually exclusive, the number of ways to do one or the other is the sum of the number of ways to do each task.
- What is the multiplication principle (rule of product)?
- If task A can be done in m ways and task B can be done in n ways (independently), the number of ways to do both A and B is m times n.
- Define n factorial (n!).
- The product of all positive integers from 1 to n. By convention, 0! = 1.
- What is a permutation?
- An arrangement of objects where order matters. The number of permutations of n distinct objects taken r at a time is P(n,r) = n! / (n-r)!.
- What is a combination?
- A selection of objects where order does not matter. The number of combinations of n distinct objects taken r at a time is C(n,r) = n! / (r!(n-r)!).
- Write the formula for P(n,r).
- P(n,r) = n! / (n-r)!
- Write the formula for C(n,r).
- C(n,r) = n! / (r!(n-r)!) or equivalently, binomial coefficient "n choose r".
- When should you use permutations instead of combinations?
- Use permutations when the order of selection matters (e.g., arranging people in a line, assigning positions). Use combinations when order does not matter (e.g., selecting a committee).
- What is a permutation with repetition?
- An arrangement where elements may be repeated. The number of permutations of n objects taken r at a time with repetition allowed is n to the power r.
- What is the formula for permutations with repetition?
- n^r, where n is the number of available objects and r is the number of positions to fill.
- What is a combination with repetition?
- A selection where elements may be chosen more than once and order does not matter. Also called multicombination or combination with replacement.
- What is the formula for combinations with repetition?
- C(n+r-1, r) = (n+r-1)! / (r!(n-1)!), where n is the number of available objects and r is the number of objects to choose.
- What is a circular permutation?
- An arrangement of objects in a circle where rotations are considered identical. The number of circular permutations of n distinct objects is (n-1)!.
- State the symmetry property of binomial coefficients: C(n,k) = ?
- C(n,k) = C(n, n-k)
- What is Pascal's Triangle?
- A triangular array of binomial coefficients where each entry is C(n,k). Each row n contains the coefficients of (x+y)^n, and each entry is the sum of the two entries above it.