Discrete Mathematics: Ordered and Unordered Partitions

Questions and Answers

A choice of k elements taken from a set of n elements such that the order does not matter and repetitions are allowed.

C(k+n−1, k)

211915132

70607460 Signup and view all the answers

A collection of disjoint nonempty subsets whose union forms the original set. Signup and view all the answers

2520 Signup and view all the answers

Count the ordered partitions and divide by the appropriate factor to eliminate order. Signup and view all the answers

420 Signup and view all the answers

15 Signup and view all the answers

120 Signup and view all the answers

5040 Signup and view all the answers

Study Notes

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).

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.

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.

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.

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.

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).

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.