Questions and Answers
What is a k-selection?
A choice of k elements taken from a set of n elements such that the order does not matter and repetitions are allowed.
What is the formula to calculate the number of k-selections from a set of n elements?
C(k+n−1, k)
What is the number of ways 30 batteries can be distributed among 10 different types?
211915132
How many ways can 30 batteries be distributed if at least 4 are of type A76?
Signup and view all the answers
What is an unordered partition?
Signup and view all the answers
How many ways can 9 toys be divided among 4 children given specific toy allocations?
Signup and view all the answers
What is the method for determining the number of unordered partitions?
Signup and view all the answers
How many distinct permutations can be formed from the letters of the word 'BENZENE'?
Signup and view all the answers
How many different signals can be formed using 4 identical red flags and 2 identical blue flags?
Signup and view all the answers
What is the number of permutations of the letters in 'ELEVEN'?
Signup and view all the answers
How many permutations can be formed from the letters of 'BASEBALL'?
Signup and view all the answers
Study Notes
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.
- k-selections are also called k-combinations with repetition allowed or multisets of size k.
- 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, k).
Exercises on K-Selections
- In a camera shop, there are 10 different types of batteries. The number of ways to distribute a total inventory of 30 batteries among the 10 different types is C(30+10-1, 30) = C(39, 30) = 211915132.
- If one of the types of batteries is A76, the number of ways to distribute a total inventory of 30 batteries among the 10 different types, such that the inventory must include at least four A76 batteries, is C(26+10-1, 26) = C(35, 26) = 70607460.
Ordered and Unordered Partitions
- An unordered partition of a finite set S is a collection [A1, A2, …, Ak] of disjoint (nonempty) subsets of S (called cells) whose union is S.
- The partition is ordered if the order of the cells in the list counts.
- Example: Let S = {1, 2, 3, …, 7}. The collections P1 = [{1,2}, {3,4,5}, {6,7}] and P2 = [{6,7}, {3,4,5}, {1,2}] determine the same partition of S but are distinct ordered partitions.
Theorem on Ordered Partitions
- Let S contain n elements and let n1, n2, …, nk be positive integers with n1+n2+…+nk = n. Then there exist n! / (n1!n2!n3!…nk!) different ordered partitions of S of the form [A1, A2, …, Ak], where A1 contains n1 elements, A2 contains n2 elements, …, Ak contains nk elements.
Exercises on Ordered Partitions
- The number of ways to divide 12 students into 3 groups with 4 students in each group so that one group studies English, one History, and one Mathematics is 12! / (4!4!4!) = 34650.
- The number of ways to divide 12 students into 3 groups with 4 students in each group so that all the groups study Mathematics is 12! / (4!4!4!) / 3! = 1730.
Generalized Permutation or Permutations with Repetitions
- The number of permutations of n elements of which n1 are alike, n2 are alike, …, nk are alike is n! / (n1!n2!…nk!).
- This number is often called a multinomial coefficient, and is denoted by the symbol (n; n1, n2, …, nk).
Exercises on Generalized Permutations
- The number of distinct permutations that can be formed using the letters of the word “BENZENE” is 7! / (3!2!) = 420.
- The number of different signals that can be formed from four identical red flags and two identical blue flags is 6! / (4!2!) = 15.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
This quiz covers ordered and unordered partitions, permutations with repetitions, and k-selections in discrete mathematics. Learn about the definitions and concepts of these topics in set theory.