Discrete Mathematics: Ordered and Unordered Partitions

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.