Questions and Answers
What is a k-combination?
A choice of k elements taken from a set of n elements where the order does not matter and elements cannot be repeated.
What does the symbol C(n, k) represent?
The number of k-combinations that can be chosen from a set of n elements.
With k-combinations, repetition of elements is allowed.
False
Compute C(5, 3).
Signup and view all the answers
How many ways can a student choose 8 questions from 10?
Signup and view all the answers
How many ways can a group of seven be chosen from 14 members?
Signup and view all the answers
How many k-selections can be made from a set of n elements?
Signup and view all the answers
How many groups of 7 can be chosen containing at least one man from 8 women and 6 men?
Signup and view all the answers
How many different 16-bit strings contain exactly 9 1s?
Signup and view all the answers
In the example of a student answering questions from sections A and B, how many total ways can they answer?
Signup and view all the answers
Study Notes
K-Combinations
- A k-combination of a set of n elements is a choice of k elements taken from the set of n elements such that the order of the elements does not matter and elements can't be repeated.
- The symbol C(n, k) denotes the number of k-combinations that can be chosen from a set of n elements.
- C(n, k) can also be written as nCk or n /k / .
- With k-combinations of a set of n elements, repetition of elements is not allowed, therefore, k must be less than or equal to n, i.e., k ≤ n.
Examples of K-Combinations
- Let X = {a, b, c}. Then 2-combinations of the 3 elements of the set X are: {a, b}, {a, c}, and {b, c}. Hence C(3,2) = 3.
- Let X = {a, b, c, d, e}. Then 3-combinations of the 5 elements of the set X are: {a, b, c}, {a, b, d}, {a, b, e}, ..., {c, d, e}. Hence C(5,3) = 10.
Permutations and Combinations
- The number of k-permutations of a set of n elements is P(n, k) = C(n, k) · k!
- P(n, k) can also be written as n! / (n-k)!
- C(n, k) can be computed using the formula: C(n, k) = n! / (k! · (n-k)!)
Some Important Results
- C(n, 0) = 1
- C(n, n) = 1
- C(n, 1) = n
- C(n, 2) = n(n-1)/2
- C(n, k) = C(n, n – k)
- C(n, k) + C(n, k + 1) = C(n + 1, k + 1)
K-Selections
- A k-selection of a set of n elements is a choice of k elements taken from a set of n elements such that the order of elements does not matter and elements can be repeated.
- The number of k-selections that can be selected from a set of n elements is C(k+n-1, k) or C(k+n-1, n-1).
- k-selections are also called k-combinations with repetition allowed or multisets of size k.
Exercises
- A student is to answer eight out of ten questions on an exam. Find the number of ways that the student can choose the eight questions. (Answer: C(10, 8) = 45)
- An examination paper consists of 5 questions in section A and 5 questions in section B. A total of 8 questions must be answered. In how many ways can a student select the questions if he is to answer at least 4 questions from section A. (Answer: 35)
- A computer programming team has 14 members. How many ways can a group of seven be chosen to work on a project? (Answer: C(14, 7) = 3432)
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Learn about k-combinations in discrete mathematics, including the definition and properties of selecting k elements from a set of n elements where order doesn't matter.
