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)?
Show answer
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)?
Show answer
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!).
Show answer
The product of all positive integers from 1 to n. By convention, 0! = 1.- What is a permutation?
Show answer
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?
Show answer
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).
Show answer
P(n,r) = n! / (n-r)!- Write the formula for C(n,r).
Show answer
C(n,r) = n! / (r!(n-r)!) or equivalently, binomial coefficient "n choose r".- When should you use permutations instead of combinations?
Show answer
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?
Show answer
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?
Show answer
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?
Show answer
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?
Show answer
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?
Show answer
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) = ?
Show answer
C(n,k) = C(n, n-k)- What is Pascal's Triangle?
Show answer
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.
FlashKeepers