From Posets to Derangements An Exploration of the Mobius Inversion Formula

From Posets to Derangements: An Exploration of the Möbius Inversion Formula May 14, 2012 Introduction We are surrounded by partially ordered sets, though we rarely view them as such. We will formally define partially ordered sets, or posets, in the first section of this paper, but for now, consider the following example: a family tree is a set of objects (the family members) together with a relation (pun intended) defined on the elements of the set. For example, you could say that a person a is “≤” a person b if they are a direct descendant of b. Say person a is person b’s sister. Neither is a descendant of the other, so they are not related (according to “≤”). This is a non-numeric partially ordered set. Given the obvious relevance of such sets, it is only natural that we should wish to investigate functions defined on them. In this paper, we begin with a simple seed of an idea, that of a partially ordered set. We proceed by considering properties of compatible matrices, walking through a proof of the existence and uniqueness of what is known as the Möbius function, µ, and subsequently offering a proof of the Möbius inversion formula. The development of the Möbius function and the proof of the Möbius inversion formula lead to results in several branches in mathematics, including combinatorics and number theory. In combinatorics, the Möbius inversion formula implies the principle of inclusion and exclusion, which is a tool used to count the number of elements of a given set in a somewhat inverted way. The Möbius function and inversion formula may also be defined number theoretically and used to prove a plethora of results. For example, we will discuss an explicit formula for counting the number of integers less than a given integer that are relatively prime to that integer. In addition to a certain level of mathematical know-how, we will assume, on the part of our reader, a working knowledge of basic set theory – including familiarity with set unions and intersections – as well as a firm understanding of basic operations on matrices. 1 Partially Ordered Sets When asked to imagine an ordered set, most moderately informed students of mathematics would picture a set with a total ordering relation. That is, if we chose any two elements in their set, they would be related by the ordering relation on the set. For instance, consider the integers with the 1 ordering relation ≤. Given any two integers a and b, either a ≤ b or b ≤ a. Suppose, instead, that we have an ordered set where it is not guaranteed that two given elements will be related at all. Such sets, called partially ordered sets, or posets, will be essential to our discussion, and are defined formally below. 1.1 Definitions and Examples Definition 1.1. [3, p.353] A relation ≤ on a set S is called a partial order, or a partial ordering relation, if ≤ is reflexive, antisymmetric, and transitive. As a quick review, recall that a relation ≤ on S is said to be reflexive if x ≤ x for all x ∈ S, antisymmetric if exactly one of x ≤ y or y ≤ x is true for distinct x, y ∈ S, and transitive if x ≤ y ∧ y ≤ z implies that x ≤ z for x, y, z ∈ S. Definition 1.2. [3, p.372] The pair (S, ≤) is called a partially ordered set, or poset, if the relation ≤ on the set S is a partial ordering relation. Partially ordered sets can take numerous forms. For example, we could have a partially ordered set comprised of the set S = {2, 3, 6, 7}, and the partial ordering relation “divides,” so that d1 ≤ d2 if d1 |d2 for d1 , d2 ∈ S. Clearly, 2|6, but 3 and 7 are not related. In order to visualize partially ordered sets, we may use what are called Hasse diagrams, which are defined as follows: Definition 1.3. [3, p.373] If ≤ is a partial order on a finite set V , we construct a Hasse diagram for ≤ on V by drawing a line segment from x up to y if x, y ∈ V with x ≤ y and if there is no other element z ∈ V such that x ≤ z and z ≤ y. (So there is nothing “in between” x and y.) For example, Figure 1 helps us to see the partial ordering relation ⊆ on P({a, b, c}). Note that P({a, b, c}) denotes the power set of {a, b, c}, which is the set of all subsets of the set {a, b, c}. We may travel (strictly “vertically”) between {a} and {a, b, c}, and so, sure enough, {a} ⊆ {a, b, c}. However, we may not travel in this fashion between {a, b} and {c}. So, {a, b} and {c} are not related. 1.2 A Nice Property of Partially Ordered Sets Let V = {x1 , x2 , . . . , xn }, together with the partial ordering relation ≤, be a partially ordered set. We propose that we may take the elements of V and create an ordered list so that if, for integers i and j between 1 and n, xi falls to the left of xj in our list, then xj  xi . 2 Figure 1: The Hasse diagram for the partially ordered set (V, ⊆), where V = P({a, b, c}). To show that we may do this, we use the principle of mathematical induction on the number of elements in our partially ordered set. Proof. As our base case, consider a partially ordered set defined by a set containing two elements and the partial ordering relation ≤. Then, these two elements, call them a and b, either have no relation, or exactly one of a ≤ b, b ≤ a is true. Notice that we may write our two elements in list form as [a, b] (or [b, a]) if they have no relation, [a, b] if a ≤ b, or [b, a] if b ≤ a. It is easy to see that these listings satisfy the necessary condition. Next, suppose that we may list the elements as desired for a partially ordered set defined by a set containing k elements and the partial ordering relation ≤. Call the set of k elements Vk . Then, we will add one more element to the set. We claim that we can place this element so that the resulting list of k + 1 elements has the desired properties. Consider the sets: S = {xi : xi ∈ Vk , xi ≤ xk+1 } T = {xi : xi ∈ Vk , xk+1 ≤ xi } . Notice that the union of these two sets is comprised of all elements in Vk which are related to k + 1, and that this union is a (not necessarily proper) subset of Vk . If either S or T is the empty set, place xk+1 at the far left or right end of the list, respectively. It is clear that this new list of k + 1 elements satisfies our conditions, and we are done. 3 Otherwise, there are finitely many elements in each set, so there exists an element of S that is farthest to the right in our ordered list of Vk , and, similarly, there exists an element of T that is farthest to the left in our list. Call these elements xs and xt , respectively. We claim that xs is to the left of xt on our list of Vk , and that we may place xk+1 anywhere between xs and xt to obtain a list of Vk+1 with the desired properties. Because xs ≤ xk+1 and xk+1 ≤ xt by our definitions of S and T , and the partial ordering relation ≤ is transitive by definition, we find that xs ≤ xt . Since it cannot be the case that xs is to the right of xt , it follows that xs must be to the left of xt . We can thus place xk+1 between xs and xt . We claim that this is an ordered list of Vk+1 . (Aside: Because this is a rather abstract argument, we will give a brief example of how this inductive step might work. Let Vk = {∅, {a}, {a, c}, {b}, {a, b, c}}, and let ⊆ be the partial ordering relation on Vk . Then, we may order Vk in the desired way as: ∅, {a}, {b}, {a, c}, {a, b, c} or ∅, {b}, {a}, {a, c}, {a, b, c}. If we want to introduce the element {c}, we note that the set S, as defined above, is equal to {∅}, and the set T , also as defined above, is equal to {{a, c}, {a, b, c}}. So, we may place {c} anywhere between ∅ and {a, c} in either of our above ordered lists and have a new ordered list that includes {c} and satifies our desired properties. For example, ∅, {b}, {c}, {a}, {a, c}, {a, b, c} is one such final ordering.) We will now show that we have created an ordered list of Vk+1 with the desired properties. Suppose that xk+1 ≤ xm for some integer m between 1 and k. Then, xm ∈ T . Since xt is the leftmost of the elements of T , xm is to the right of xt and, by our choice of xk+1 ’s location, xm is to the right of xk+1 . By contraposition, we find that if xm is to the left of xk+1 , then xk+1  xm . So, our ordered list of Vk+1 has the desired properties, and, by the principle of mathematical induction, we find that we may create such an ordered list of a partially ordered set of any size. Actually, a permutation that places the elements of a partially ordered set so that xi ≤ xj implies that xi falls to the left of xj is called a linear extension of the partially ordered set. 2 Compatible Matrices In our later proof of Möbius inversion, we will make use of what are called compatible matrices and several of their properties. We will begin our discussion of compatible matrices with their definition. Note that a matrix is said to be compatible in relation to a specific partially ordered set. 4 2.1 Definition and Example Definition 2.1. An n × n matrix A is compatible with respect to the partially ordered set (V, ≤), where V = {x1 , x2 , . . . , xn }, if Aij 6= 0 implies that xi ≤ xj . For example, consider the partially ordered set (V, ⊆), where V = P({a, b, c}) (see Figure 1). Define the following: x1 = ∅ x3 = {b} x5 = {a, b} x7 = {b, c} x2 = {a} x4 = {c} x6 = {a, c} x8 = {a, b, c} Then, the reader may verify that the following are all compatible matrices relative to the partially ordered set (V, ⊆), with the last of the three having a 1 in every entry that may be nonzero (we will later define this particular matrix as the “complete” compatible matrix of (V, ⊆)):  6 0  0  0  0  0  0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 7 0  1 0  0  0  0  0  0 0  1 0  0  0  0  0  0 0   0 0.65 0 6 0 0 500 1   0 0 0 3 π 0 1  0  0 20 0 0 0 0 0   0  0 0 0 0 0 4 0   0  0 0 0 5 0 0 2   0  0 0 0 0 1 0 2   0 0 0 0 0 0 0 3  0 0 0 0 0 0 0 5 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0  1 1  1  1  1  1  1 1 We may note that the 8 × 8 matrix comprised of all zeros is also compatible with respect to (V, ⊆). That the zero matrix satisfies the necessary conditions for being compatible in reference to any partially ordered set is clear. 2.2 Several Properties From the properties of a partial ordering relation, several properties of compatible matrices are immediately evident. First, note that if Aij (the ijth entry of the matrix A) is nonzero for distinct i and j, then Aji = 0. This follows directly from the antisymmetric property established in Definition 1.1. Furthermore, Aii may always be nonzero, and if Aij and Ajk are nonzero, then Aik may be nonzero. In these cases, we are using the reflexive and transitive properties, respectively, of Definition 1.1. Some other, perhaps less obvious, properties of compatible matrices follow. Theorem 2.1. Let A and B be n × n matrices that are compatible with respect to the partially ordered set (V, ≤), where V = {x1 , x2 , . . . , xn }, and ≤ is a partial ordering relation on V . Then A + B = C is also compatible with respect to (V, ≤). 5 Proof. Consider two n × n matrices, A and B, which are compatible with respect to the partially ordered set (V, ≤), where V = {x1 , x2 , . . . , xn }, and ≤ is a partial ordering relation on V . Because A is compatible, if Aij is nonzero for positive integers i and j less than or equal to n, then xi ≤ xj . Since B is also compatible, Bij can be either nonzero or zero. Then, Aij + Bij is nonzero or zero (the latter is the case in which Aij = −Bij ) and the property “Cij 6= 0 implies xi ≤ xj ” is preserved in such entries of the matrix C = A + B. Note that the same argument can be made for the case in which Bij is nonzero and Aij is zero. In the case in which both Aij and Bij are zero, Cij = Aij + Bij = 0 + 0 = 0, and so the conditional statement “Cij 6= 0 implies xi ≤ xj ” is certainly preserved in such entries of the matrix C = A + B. Thus, by definition, if A and B are compatible matrices with respect to (V, ≤), C = A + B is also compatible with respect to (V, ≤). Before we state and prove the next property of compatible matrices, it is important to first note that we may multiply two n × n matrices using the standard method of matrix multiplication. Theorem 2.2. If A and B are n × n matrices that are compatible with respect to the partially ordered set (V, ≤), where V = {x1 , x2 , . . . , xn } and ≤ is a partial ordering relation on V , then their product, AB, is also compatible with respect to (V, ≤). Proof. Consider a partially ordered set (V, ≤) with V = {x1 , x2 , . . . , xn }, and take n × n matrices A and B that are compatible with respect to (V, ≤). Let C = AB. To show that C is also compatible with respect to (V, ≤), we must prove that if Cij is nonzero for positive integers i and j less than or equal to n, then xi ≤ xj . If this is the case, Aij must have been nonzero or what I will call a “secret zero,” which will denote an entry Aij that is zero while xi ≤ xj . (Recall that our definition for compatible matrices is not a biconditional.) We find that, for C to be compatible, it is necesssary and sufficient to show that the following is satisfied: if Cij is nonzero, then Aij is either nonzero or a “secret zero”. (Note that this is equivalent to the statement: if Cij is nonzero, then Bij is either nonzero or a “secret zero”.) Suppose that Cij is nonzero, and recall that Cij = Ai1 B1j + Ai2 B2j + . . . + Ain Bnj . Then, it is clear that at least one of the terms in this sum must be nonzero. Call this term Aik Bkj . If the product of Aik and Bkj is nonzero, then each is separately nonzero and we have the following relations: xi ≤ xk and xk ≤ xj . Because our partial ordering relation is, by definition, transitive, we find that xi ≤ xj , and so Aij is either nonzero or a “secret zero”. 6 Therefore, if Cij is nonzero, then Aij is either nonzero or a “secret zero,” and we are done. 2.3 Groundwork for the Final Property The next property of compatible matrices is in no way self-evident. It states that if the inverse of a compatible matrix exists, then it is also compatible. However, we do not yet have the tools necessary to prove this property, and so will need to work up to its statement and proof. Consider a matrix A that is compatible with respect to the partially ordered set (V, ≤), where V = {x1 , x2 , . . . , xn }. From our findings in Section 1.2, we know that we may order the elements of V such that for any pair xi and xj where xi falls to the left of xj in our list, xj  xi . For the sake of notation, let this list be: y1 , y2 , . . . , yn , where y1 is the element of V that is farthest to the left in this list, y2 is second from the left, etc. up to yn , which is the rightmost element of V in our ordered list. So if, for example, the beginning of our ordered listing of x’s is x7 , x4 , x2 , x13 , . . ., then, y1 = x7 , y2 = x4 , y3 = x2 , y4 = x13 , etc. If we think of a compatible matrix as an n × n matrix whose rows and columns are labeled x1 , x2 , . . . , xn , we may also consider the matrix whose rows and columns are labeled by y1 , y2 , . . . , yn . It then becomes clear that another important concept in our discussion will be that of a permutation matrix, which is simply the n × n identity matrix with its rows reordered so that, when multiplied by any other n × n matrix on the left or right, it reorders that matrix’s rows or columns, respectively. Note that in discussing permutation matrices, we are moving outside of the realm of compatible matrices: that is, a given permutation matrix is not necessarily compatible. So, using two permutation matrices, we may reorder the rows and columns of A so that it is a compatible matrix corresponding to the relationship between the y’s rather than the x’s. Call this matrix T . In order to define these permutation matrices more explicitly, recall that: Definition 2.2. [4, p.114] Given an m × n matrix A, the transpose of A is the n × m matrix, denoted by AT , whose columns are formed from the corresponding rows of A. We say that T = P AQ for permutation matrices P and Q; P is defined as a permutation matrix where Pij is 1 if xj is in the ith position in our ordered listing of V . Otherwise, Pij is zero. Q is simply the transpose of P . To illustrate this concept, consider the following example: Example 2.1. Suppose our ordered listing of {x1 , x2 , x3 , x4 } is [x1 , x4 , x2 , x3 ]. Then our permutation matrix P would be:  1 0  0 0 0 0 1 0 0 0 0 1 7  0 1  0 0 Multiplied on the left, this matrix will take a compatible matrix, B, of the partially ordered set defined on the set {x1 , x2 , x3 , x4 }, and will reorder its rows so that the first row of B becomes the first row of B 0 , the second row of B becomes the third row of B 0 , the third row of B becomes the fourth row of B 0 , and the fourth row of B becomes the second row of B 0 . Q, then, is the transpose of P :  1 0  0 0 0 0 0 1 0 1 0 0  0 0  1 0 Q will rearrange the columns of B 0 in a similar fashion in order to create TB . It is not too difficult to see that T will always be an upper triangular matrix. Consider the entry Tij . If i is greater than j (in the traditional sense of ordered integers), then Tij must be zero by Definition 2.1, since, by our creation of the y’s as an ordered listing of the x’s, we have established that yi  yj . We have concluded that, given a matrix that is compatible with respect to a partially ordered set (V, ≤), where V = {x1 , x2 , . . . , xn }, we may create a corresponding upper triangular matrix, T , that is compatible with respect to the partially ordered set (V ?, ≤), where V ? = {y1 , y2 , . . . , yn } is comprised of the elements of V relisted so that if xm ≤ xn , then xm falls to the left of xn on our list. For notational simplicity, we then re-label the x’s as y’s, in sequential order. Note that if the inverse of T is compatible with respect to V ?, then the inverse of our original matrix A is compatible with respect to V . Recall the following properties of matrices: Theorem 2.3. If A is a triangular matrix, then det A is the product of the entries on the main diagonal of A. Theorem 2.4. A square matrix A is invertible if and only if det A 6= 0. Definition 2.3. The n × n identity matrix is the matrix with 1’s on the diagonal and 0’s elsewhere. So, T is invertible if and only if the entries on its main diagonal are all nonzero. It will also be helpful to be aware of a few additional properties of T −1 before we begin to work with it in earnest: • T −1 is an upper triangular matrix. To see that this is true, consider deriving T −1 by row reducing the augmented matrix [T I]. If T −1 , exists, [T I] is row equivalent to [I T −1 ] [4, p.124]. Since T is upper triangular, to reduce T to I, for each given row we need only subtract rows that fall below that given row. When we consider what is happening to I, on the right, while we do this, we see that I only gains entries above the diagonal as it becomes T −1 . 8 • The entries on the main diagonal of T −1 are all nonzero. Recall that an n × n matrix is invertible if and only if its determinant is nonzero, and that the determinant of an upper triangular matrix is the product of the entries on its main diagonal. Then, if any of the entries on the diagonal of T −1 were zero, T −1 would not be invertible. However, T −1 is clearly invertible, as it is the inverse of T . −1 So, all entries Tij−1 where i > j are equal to zero, and all entries Tjj are nonzero. We can see that both properties are allowed in a compatible matrix. So, in our proof that T −1 is compatible, we need only look at entries Tij−1 of T −1 where i < j, and ensure that if Tij−1 6= 0, then yi ≤ yj . 2.4 The Final Property Now, we may move on to the final property of compatible matrices that we will explore in this paper. Theorem 2.5. If the inverse of an upper triangular matrix T that is compatible with respect to the partially ordered set (V ?, ≤) exists, then T −1 is also compatible with respect to (V ?, ≤). Proof. We will use the principle of strong induction to show that for all entries that lie above the diagonal in the jth (where 2 ≤ j ≤ n) column of an n × n matrix T −1 (where T −1 is the inverse of a compatible upper triangular matrix T ), the following property holds: If the entry Tij−1 is nonzero, then yi ≤ yj . −1 In other words, we will prove that T −1 is a compatible matrix by considering the entries T(j−k)j −1 for 1 ≤ k ≤ (j − 1). In particular, in each step of our induction on k, we will prove that T(j−k)j 6= 0 ⇒ yi ≤ yj by contraposition. −1 As our base case, let k = 1 and suppose yj−1  yj . Then we are considering the entry T(j−1)j . Recall that T T −1 = I(= T −1 T ), where I is the n × n identity matrix. The (j − 1)jth entry of I is equal to zero by definition, and so, from standard matrix multiplication, −1 −1 −1 −1 −1 T(j−1)1 T1j + T(j−1)2 T2j + . . . + T(j−1)(j−1) T(j−1)j + T(j−1)j Tjj + . . . + T(j−1)n Tnj = 0. (1) However, because T and T −1 are both upper triangular matrices, we see that T(j−1)1 , T(j−1)2 , T(j−1)2 , . . . , −1 −1 −1 −1 T(j−1)(j−2) and T(j+1)j , T(j+2)j , T(j+3)j , . . . , Tnj are all equal to zero. So, our sum on the left in equation (1) reduces to 9 −1 −1 T(j−1)(j−1) T(j−1)j + T(j−1)j Tjj = 0. Since T is a compatible matrix and yj−1  yj , we see that T(j−1)j = 0 by definition. Then, we have −1 T(j−1)(j−1) T(j−1)j = 0. Because T is an invertible upper triangular matrix, and T(j−1)(j−1) is an entry on its diagonal, −1 T(j−1)(j−1) is nonzero. Then, T(j−1)j must be equal to zero. We have now shown that, for k = 1, if yj−k  yj , then b(j−k)j = 0. By contraposition, if b(j−k)j 6= 0, then yj−k ≤ yj . −1 Next, suppose this holds true for all k up to k = l − 1. Thus, if T(j−k)j 6= 0 for 1 ≤ k ≤ (l − 1), then yj−k ≤ yj . Suppose yj−l  yj . We will look at the (j − l)jth entry of the identity matrix. This entry will be equal to zero, since (j − l) 6= j. From the product of T and T −1 , it is clear that the following equation holds −1 −1 −1 −1 −1 T(j−l)1 T1j + T(j−l)2 T2j + . . . + T(j−l)(j−l) T(j−l)j + . . . + T(j−l)j Tjj + . . . + T(j−l)n Tnj = 0. As was the case before, this reduces down to −1 −1 −1 T(j−l)(j−l) T(j−l)j + T(j−l)(j−l+1) T(j−l+1)j + . . . + T(j−l)j Tjj = 0. Since T is a compatible matrix and yj−l  yj , we see that T(j−l)j = 0. Then: −1 −1 −1 T(j−l)(j−l) T(j−l)j + T(j−l)(j−l+1) T(j−l+1)j + . . . + T(j−l)(j−1) T(j−1)j = 0. (2) −1 Suppose, by way of contradiction, that T(j−l)(j−l) T(j−l)j 6= 0. Then, in order for equation (2) to −1 −1 hold, it must be the case that T(j−l)(j−l+1) T(j−l+1)j + . . . + T(j−l)(j−1) T(j−1)j 6= 0. Clearly, at least one of the terms must be nonzero. Without loss of generality, call this nonzero term T(j−l)t Ttj−1 , where (j − l + 1) ≤ t ≤ (j − 1). Note that t = j − m for 1 ≤ m ≤ (l − 1) and that T(j−l)t and Ttj−1 are both nonzero. From our induction step, we know that if Ttj−1 is nonzero, then yt ≤ yj . T is compatible relative to (V ?, ≤), and so T(j−l)t 6= 0 implies that yj−l ≤ yt . Because our partial ordering relation is transitive, we see that: yj−l ≤ yt ∧ yt ≤ yj ⇒ yj−l ≤ yj . 10 However, this contradicts our assumption that yj−l  yj . Then what we assumed is false, and −1 T(j−l)(j−l) T(j−l)j = 0. We know that T(j−l)(j−l) 6= 0, since it is an entry on the diagonal of T , −1 −1 so we conclude that T(j−l)j = 0. In summary, yj−l  yj implies that T(j−l)j = 0, and so, by −1 contraposition, T(j−l)j 6= 0 implies that yj−l ≤ yj . −1 We have shown that the statement “if T(j−k)j 6= 0, then yj−k ≤ yj ” holds for k = 1, and that if it holds for all k up to k = l − 1 then it holds for k = l. Thus, by the principle of strong induction, −1 “if T(j−k)j 6= 0, then yj−k ≤ yj ” holds for all positive integers k. Note, however, that this does not make sense for k > (j − 1), so we limit our conclusion to encompass only the integers k such that 1 ≤ k ≤ (j − 1). Finally, recall that our choice of column j was completely arbitrary. Thus, we have effectively shown that if any entry Tij−1 that lies above the main diagonal is nonzero, then yi ≤ yj . This is sufficient to show that T −1 is compatible with respect to the partially ordered set (V ?, ≤). As mentioned earlier, this implies that the inverse of our original matrix A, from which T was derived, is compatible with respect to (V, ≤). So, we have shown the following: Theorem 2.6. If the inverse of a matrix A that is compatible with respect to the partially ordered set (V, ≤) exists, then A−1 is also compatible with respect to (V, ≤). 2.5 Complete Compatible Matrices Earlier, we mentioned that there are infinitely many matrices that are compatible with respect to a given partially ordered set (V, ≤). In order to take away the most information about a partially ordered set from one of its compatible matrices, we would like that matrix to have a nonzero entry in each position it is allowed to have a nonzero entry by definition. The concept of a complete compatible matrix addresses this desire by defining a particular (and quite tidy) “ideal” compatible matrix of (V, ≤). Definition 2.4. A matrix Z, which is compatible with respect to the partially ordered set (V, ≤), is said to be the complete compatible matrix of (V, ≤) when ( 1 if xi ≤ xj , Zij = 0 otherwise, where xi , xj ∈ V = {x1 , x2 , . . . , xn }. Note that the complete compatible matrix of a given partially ordered set is unique up to the labeling of the elements. For example, we may use permutation matrices to create a matrix that 11 is the complete compatible matrix with respect to any linear extension of a given partially ordered set (See the Section 2.3). This complete compatible matrix is not necessarily equal to the complete compatible matrix generated by the original labeling of the partially ordered set. However, assuming a fixed labeling of the elements of our partially ordered set, its corresponding complete compatible matrix is, indeed, unique. In considering M , the inverse of a complete compatible matrix Z, we note that, if M exists, then it is also compatible with respect to (V, ≤) (see Theorem 2.5). In fact, M always exists, which brings us to the following result: Theorem 2.7. If Z is the complete compatible matrix of a partially ordered set (V, ≤), then Z −1 = M exists. Proof. For a given partially ordered set, we may label the elements of the set in any way we choose. Specifically, label the elements such that if xm ≤ xn , then m ≤ n. Then, Z is an upper triangular matrix (see Sections 1.2 and 2.3), and all diagonal entries of Z are equal to 1 by definition. Since the determinant of an upper triangular matrix is the product of its diagonal entries by Theorem 2.3 (in the case of the complete compatible matrix, det Z = 1), and an n × n matrix is invertible if and only if its determinant is nonzero by Theorem 2.4, we find that Z is invertible. Therefore, Z −1 = M exists. 3 The Möbius Function In order to work up to the concept of Möbius inversion, we must first define what is known as the Möbius function. In this section, we will state the definition of the Möbius function, prove its existence, and explicitly define the function in the context of several common structures of partially ordered sets. These last definitions will be useful as we begin to look at applications of the Möbius inversion formula in later sections. Definition 3.1. [6] The Möbius function µ is defined on (V, ≤) × (V, ≤) by the following properties for xi , xj , xk ∈ V : µ(xi , xj ) = 0 if xi  xj , µ(xi , xi ) = 1 , X µ(xi , xj ) = 0 if xi < xk . xi ≤xj ≤xk (Note that “xi < xk ” is defined as “xi ≤ xk and xi 6= xk .”) 12 3.1 Establishing Existence We will show that µ(xi , xj ) = Mij , where M is the inverse of the complete compatible matrix Z of (V, ≤), satisfies each of these properties and so is, by definition, the Möbius function. Lemma 3.1. Mij = 0 if xi  xj . Proof. As was previously noted, M , as the inverse of the compatible matrix Z, is also compatible with respect to (V, ≤) (see Theorem 2.5). By the definition of a compatible matrix (see Definition 2.1), if Mij 6= 0, then xi ≤ xj . By the contrapositive of this conditional statement, if xi  xj , then Mij = 0. We will review several results from linear algebra before we show the validity of the next property of the Möbius function. Definition 3.2. [4, p.187] For any square matrix A, let Ãij denote the submatrix formed by deleting the ith row and jth column of A. Definition 3.3. [4, p.203] The adjugate, or classical adjoint, of a matrix A is denoted by adjA, and is given by:   C11 . . . C1n  .. ..  , ..  . . .  Cn1 . . . Cnn Where Cij = (−1)i+j det Ãij . Theorem 3.1. [4, p.203] Let A be an invertible n × n matrix. Then A−1 = 1 adjA . det A Now we may move on to a proof that the second property of the Möbius function holds for µ(xi , xj ) = Mij . Lemma 3.2. Mii = 1. Proof. By Theorem 3.1, Z −1 = 1 det Z adjZ where ‘adj’ denotes the adjugate of Z. So,  Z −1 = 1 det Z C11  ..  . Cn1 where Cij = (−1)i+j det Z̃ij . 13  . . . C1n ..  , .. . .  . . . Cnn Since det Z = 1,   . . . C1n ..  , .. . .  . . . Cnn C11  .. = . Z −1 Cn1 So, Mii = Cii = (−1)2i det Z̃ii = det Z̃ii . Note that det Z̃ii = 1, since Z̃ii is simply the matrix Z defined on (V \ {xi }, ≤), and all arguments we have made regarding the determinant apply to the matrix Z regardless of the size of the partially ordered set from which Z is formed. Therefore, Mii = 1. Lemma 3.3. X Mij = 0 if xi < xk . xi ≤xj ≤xk Proof. Since M Z = I, where I is the n × n identity matrix, we see that for xi < xk (and thus i 6= k), Mi1 Z1k + Mi2 Z2k + . . . + Min Znk = Iik = 0. Since Z is compatible, the only Zjk ’s that will be nonzero are those for which xj ≤ xk . Furthermore, these entries will be equal to 1 by the definition of Z. Then, our sum reduces to a sum of all Mij ’s where xj ≤ xk . Note that, because M is also compatible, the only terms of this simplified sum that will be nonzero are those for which xi ≤ xj . In summary, X Mij = 0. xi ≤xj ≤xk Therefore, because µ(xi , xj ) = Mij satifies the necessary and sufficient properties outlined in Definition 3.1, it is a representation of the Möbius function. Now that we have proven its existence, we will prove the uniqueness of the Möbius function. Note that M is unique up to the labeling of the elements of the partially ordered set (See Section 2.5 for further discussion of uniqueness). As we develop our proof, we will assume a fixed labeling. Regardless of how we label, however, the Möbius function’s uniqueness holds: we are claiming that specific entries of M define the Möbius function, not the structure of M itself. 3.2 Establishing Uniqueness Lemma 3.4. The Möbius function is unique. 14 Proof. To prove that the Möbius function is unique, consider a function γ defined on (V, ≤)×(V, ≤), where V = {x1 , x2 , x3 , . . . , xk }, such that γ satisfies all the properties necessary to be deemed the Möbius function. Build a k × k matrix N such that Nij = γ(i, j), and let Z be the complete compatible matrix of (V, ≤). We established in earlier in this section that Z −1 = M is the Möbius function. To show the uniqueness of the Möbius function, it is sufficient to show that N = M , or, alternatively, that ZN = I, where I is the k × k identity matrix. To do so, consider the product ZN . We must show that each diagonal entry of this product is equal to 1, and that each entry not on a diagonal is equal to zero. Consider (ZN )ii , an arbitrary diagonal entry of the product. Performing basic matrix multiplication, we find that: (ZN )ii = k X Zij Nji . j=1 Note that because Z is the complete compatible matrix of (V, ≤), Zij is nonzero exactly when xi ≤ xj , and that when this is true, Zij = 1. We may, then, simplify our sum: X (ZN )ii = Nji . 1≤j≤k, xi ≤xj However, by the first property of the Möbius function (see Definition 3.1), Nji = 0 when xj  xi . Thus, the only nonzero term of our sum is Nii , which, from the second property of the Möbius function, is equal to 1. So, (ZN )ii = 1. Next, consider an entry (ZN )il of the matrix ZN , where i 6= l. As before, we may rewrite this entry in summation notation: (ZN )il = k X Zij Njl . (3) j=1 As in the first case, note that Zij = 1 when xi ≤ xj , and is equal to zero otherwise. Then, rewriting again: (ZN )il = X Njl . 1≤j≤k, xi ≤xj By our definition of N , the only nonzero terms of this sum are those j’s for which xj ≤ xl . Then, 15 (ZN )il = X Njl = X µ(j, l) . xi ≤xj ≤xl xi ≤xj ≤xl By the third property of the Möbius function, (ZN )il = 0 when xi < xl . (Note that if xi ≮ xl , either xi ≮ xj or xj ≮ xl for each 1 ≤ j ≤ k since the partial ordering relation is transitive, and so the terms of Equation 3 are all equal to zero, and thus the entire sum is equal to zero.) Thus, we have shown that ZN = I, or N = M , and so the Möbius function is unique. 3.3 Several Examples Next, we will look at partially ordered sets that are made up of the subsets of a set paired with the partial ordering relation ⊆, and the divisors of a positive integer paired with the partial ordering relation “divides” (|). By looking at several specific examples, we will develop the general form of the Möbius function for similarly constructed partially ordered sets. 3.3.1 Sets Our first example will be the partially ordered set consisting of all subsets of the set {a, b, c} together with the partially ordering relation ⊆. Recall that we discussed this particular partially ordered set in Section 1.1. We will refer to the Hasse diagram in that section throughout this example. Example 3.1. The relationships between elements of the partially ordered set V defined by P({a, b, c}), ⊆ may be seen in its corresponding Hasse diagram (Figure 1). Building the Möbius function of this poset from the ground up, we first note that, by definition, if A * B for A, B ∈ S, then µ(A, B) = 0. Furthermore, µ(A, A) = 1 for each A ∈ V . We will start by looking at any two elements A and B that are consecutive in Figure 1. By consecutive, we mean to say that two elements are directly connected by a single line segment. For example, {a} and {a, b} are consecutive elements, while {a} and {a, b, c} are not. By the third property of the Möbius function (see Definition 3.1), X µ(A, X) = 0. A⊆X⊆B However, because A and B are consecutive, there are no elements of the poset that are strictly “between” them. So we find that: 16 X µ(A, X) = µ(A, A) + µ(A, B) = 0. (4) A⊆X⊆B As discussed, µ(A, A) = 1. Then, it is clear that: µ(A, B) = −1. This argument takes care of much of our work: µ(∅, {a}) = µ(∅, {b}) = µ(∅, {c}) = −1 µ({a}, {a, b}) = µ({a}, {a, c}) = −1 µ({b}, {a, b}) = µ({b}, {b, c}) = −1 µ({c}, {a, c}) = µ({c}, {b, c}) = −1 and, µ({a, b}, {a, b, c}) = µ({a, c}, {a, b, c}) = µ({b, c}, {a, b, c}) = −1. The only µ’s we have left to define are µ(∅, {a, b}), µ(∅, {a, c}), µ(∅, {b, c}), µ(∅, {a, b, c}), µ({a}, {a, b, c}), µ({b}, {a, b, c}), and µ({c}, {a, b, c}). Again using the third property of the Möbius function, we find that this is relatively straightforward: X µ({a}, X) = µ({a}, {a}) + µ({a}, {a, b}) + µ({a}, {a, c}) + µ({a}, {a, b, c}) = 0. (5) {a}⊆X⊆{a,b,c} So, 1 − 1 − 1 + µ({a}, {a, b, c}) = 0, and µ({a}, {a, b, c}) = 1. By similar arguments, µ({b}, {a, b, c}) = µ({c}, {a, b, c}) = µ(∅, {a, b}) = µ(∅, {a, c}) = µ(∅, {b, c}) = 1, and, µ(∅, {a, b, c}) = −1. We have thus explicitly defined the Möbius function for all elements of (V, ⊆) × (V, ⊆). Generalizing our results, we arrive at the following: Theorem 3.2. Suppose A and B are elements of the partially ordered set defined by P(S) for some set S and the partial ordering relation ⊆, such that A ⊆ B. Then, µ(A, B) = (−1)|B|−|A| . 17 Proof. Suppose A and B are elements of the partially ordered set defined by P(S) for some set S and the partial ordering relation ⊆, such that A ⊆ B. We will prove Theorem 3.2 using the principle of strong induction on k = |B| − |A|. As our base case, suppose k = 0. Then, |B| = |A|. Since A ⊆ B, we find that A = B. By definition, µ(A, B) = µ(A, A) = 1 = (−1)0 = (−1)|B|−|A| , and we have shown that Theorem 3.2 holds for k = 0. Suppose k = 1. Then, B = A ∪ {b1 } for some b1 not in A. So, A and B are consecutive subsets, and we know from a generalization of our argument in Example 3.1 (specifically, Equation 4) that µ(A, B) = −1 = (−1)1 = (−1)|B|−|A| . So, Theorem 3.2 holds for k = 1. Suppose Theorem 3.2 holds for all k up to k = n − 1. Consider the case in which k = n. We note that B = {b1 , b2 , . . . , bn } ∪ A, where b1 , b2 , . . . , bn are distinct and are not elements of A. Note that we may remove b1 , b2 , . . ., bn−1 , or bn from the set B to produce the subsets {b2 , b3 , . . . , bn }∪
A, {b1 , b3 , . . . , bn } ∪ A, . . ., {b1 , b2 , . . . , bn−2 , bn } ∪ A, and {b1 , b2 , . . . , bn−1 } ∪ A. Thus, there are n1 subsets of B of order (n − 1) + |A|. Note that, by our induction hypothesis, µ(A, C), where C is one of these subsets, is equal to (−1)|C|−|A| .
Similarly, there are n2 subsets of order (n − 2) + |A|, etc, all the way down to
order (1) + |A|, and finally, nn = 1 subset of order |A| (namely, A itself). n n−1
subsets of Then, from the third property of the Möbius function, and because Theorem 3.2 holds for all k up to k = n − 1, X A⊆S⊆B         n n n n n−1 n−2 1 µ(A, S) = (−1) + (−1) + ... + (−1) + (−1)0 + µ(A, B) = 0. 1 2 n−1 n Simplifying and rearranging, we see that:   n   n   X X n n n n−j n−j (−1) + µ(A, B) = (−1) − (−1)n + µ(A, B) = 0. j j 0 j=1 j=0 By noticing that the sum may be rewritten using the binomial theorem, we see that:     n n n (1 − 1) − (−1) + µ(A, B) = 0 − (−1)n + µ(A, B) = 0. 0 0 n And so, n 0
(−1)n = (−1)n = (−1)|B|−|A| = µ(A, B), and we have shown that Theorem 3.2 holds 18 Figure 2: The Hasse diagram for the partially ordered set (V, |), where V is the set of all divisors of 12. for k = n. Thus, by the principle of strong induction, Theorem 3.2 holds for all positive integers k and thus µ(A, B) = (−1)|B|−|A| for all sets A and B such that A ⊆ B. 3.3.2 Divisors Our definition of the Möbius function in the case of a partially ordered set made up of the divisors of an integer and the partial ordering relation “divides” is similar to the definition for the subsets case. Consider that, by the fundamental theorem of arithmetic, we may express any integer greater than 1 uniquely as a product of primes. So, we may express each integer in our partially ordered set as a set made up of its prime divisors. For example, 14 = 2 × 7 would be expressed as {2, 7}. Note, however, that these primes are not necessarily distinct, and so we may have multisets such as {2, 2, 2}, which is the set form of 8 = 2 × 2 × 2, and is not the same as {2, 2} or {2}, which are the set forms of 4 = 2 × 2 and 2 = 2, respectively. It is clear, then, that we must revise Theorem 3.2 in some way in order to apply it to this new partially ordered set. First, consider as an example the integer 12 and its prime divisors together with the partial ordering relation “divides.” Example 3.2. The Hasse diagram of the partially ordered set defined by the set of divisors of 12 and the partial ordering relation “divides” is shown in Figure 2. As was the case in Example 3.1, if d is a divisor of 12, then µ(d, d) = 1. Also as in our previous 19 example, we see that for two “consecutive” divisors d1 and d2 of 12, µ(d1 , d2 ) = −1. Thus, µ(1, 3) = µ(1, 2) = µ(2, 4) = µ(2, 6) = µ(3, 6) = µ(4, 12) = µ(6, 12) = −1. What remains to be defined are the following: µ(1, 4), µ(1, 6), µ(1, 12), µ(2, 12), and µ(3, 12). Note, however, that from the third property of the Möbius function, X µ(1, d) = µ(1, 1) + µ(1, 2) + µ(1, 4) = 0, 1|d|4 X µ(1, d) = µ(1, 1) + µ(1, 2) + µ(1, 3) + µ(1, 6) = 0, 1|d|6 X µ(1, d) = µ(1, 1) + µ(1, 2) + µ(1, 3) + µ(1, 4) + µ(1, 6) + µ(1, 12) = 0, 1|d|12 X µ(2, d) = µ(2, 2) + µ(2, 4) + µ(2, 6) + µ(2, 12) = 0, 2|d|12 and, X µ(3, d) = µ(3, 3) + µ(3, 6) + µ(3, 12) = 0. 3|d|12 So, µ(1, 4) = 0, µ(1, 6) = 1, µ(1, 12) = 0, µ(2, 12) = 1, and µ(3, 12) = 0. We may state a generalization of our findings: Theorem 3.3. Suppose a and b are elements of some partially ordered set defined by the set of divisors of some integer c and the partial ordering relation “divides,” such that a|b. Then, ( (−1)k if ab = p1 p2 . . . pk for distinct primes p1 , p2 , . . . pk , µ(a, b) = 0 if some prime in the prime decomposition of ab has multiplicity ≥ 2. Proof. Suppose a and b are elements of the partially ordered set as described in Theorem 3.3. We will prove the theorem using the principle of strong induction on k, the number of (not necessarily distinct) primes in the unique prime factorization of the quotient ab . 20 Suppose, first, that k = 0. Then there are no primes in the quotient ab . In other words, b = a. Then, by our definition of the Möbius function, µ(a, b) = µ(a, a) = 1 = (−1)0 . Thus, we have shown that the proposition holds for k = 0. Next, consider the case where k = 1. Then b = ap for some prime p. By the third property of the Möbius function (see Definition 3.1), X µ(a, d) = µ(a, a) + µ(a, b) = 1 + µ(a, b) = 0, a|d|b so µ(a, b) = −1 = (−1)1 , which proves Theorem 3.3 for k = 1. Suppose k = 2. Here, we begin to see the reasoning behind the extra caveat of Theorem 3.3. When k = 2, we have two cases. Either b = ap2 for some prime p, or b = apq for distinct primes p and q. In the first case, by the third property of the Möbius function, X µ(a, d) = µ(a, a) + µ(a, ap) + µ(a, b) = 1 − 1 + µ(a, b) = 0, a|d|b and so µ(a, b) = 0. In the second case, the same property of the Möbius function yields: X µ(a, d) = µ(a, a) + µ(a, ap) + µ(a, aq) + µ(a, b) = 1 − 1 − 1 + µ(a, b) = 0, a|d|b and so µ(a, b) = 1 = (−1)2 . From this and the first case, we have shown that Theorem 3.3 holds for k = 2. Suppose, next, that the proposition holds for k = (n − 1). Consider the case in which k = n. Then b = ap1 p2 · · · pn for not necessarily distinct p1 , p2 , . . . , pn . If p1 , p2 , . . . , pn are distinct, then we may simply revert back to our idea of integers as sets and our proof of Theorem 3.2 to show that µ(a, b) = (−1)n . Suppose, instead, that p1 , p2 , . . . , pn are not distinct, and consider µ(a, d), where d 6= b and a|d|b. Since there must be fewer than n primes in the prime decomposition of ad , Theorem 3.3 holds for all µ(a, d) by our induction hypothesis. So, we know that if t is a divisor of b such that t 6= b and at has a prime divisor with multiplicity greater than 1, µ(a, t) = 0. Otherwise, the divisor of b divides c = aq1 q2 · · · qm , where the qi s are exactly the distinct elements of {p1 , p2 , . . . , pn }. Again drawing on the third property of the Möbius function, X µ(a, d) = 0. a|d|c Then, X a|d|b µ(a, d) = X µ(a, d) + a|d|c 21 X µ(a, t) + µ(a, b) = 0, where c is defined as above and the t’s are such that t 6= b and at has a prime in its prime decomposition with multiplicity greater than 1. Simplifying, X X X µ(a, d) + µ(a, t) + µ(a, b) = 0 + 0 + µ(a, b) = 0. µ(a, d) = a|d|b a|d|c Thus, we have shown that Theorem 3.3 holds for k = n, and so, by the principle of strong induction, Theorem 3.3 holds for every possible choice of primes in the prime decomposition of ab , and so holds for all a and b, where a and b are elements of the partially ordered set described in Theorem 3.3, and a|b. 4 The Möbius Inversion Formula In Section 3.1, we established that µ(xi , xj ) = Mij , where M is the inverse of the complete compatible matrix Z, satisfies the properties necessary to be defined as the Möbius function. From this, showing the validity of what is known as the Möbius inversion formula, which is stated below, is straightforward. 4.1 Definition Theorem 4.1. [6] Suppose that f is any function on the partially ordered set (V, ≤), xi and xj ∈ V , and X g(xj ) = f (xi ) . xi ≤xj Then, f (xj ) = X g(xi )µ(xi , xj ) . xi ≤xj Proof. Suppose that f is any function on (V, ≤), xi and xj ∈ V , and X g(xj ) = f (xi ) . xi ≤xj Let Z be the complete compatible matrix on (V, ≤), and let M = Z −1 . Since Zij is equal to 1 exactly when xi ≤ xj , we may rewrite this as:   g(xj ) = the jth entry of the product f (x1 ) f (x2 ) . . . f (xn ) Z 22 Consider the sum: X g(xi )µ(xi , xj ) = xi ≤xj X g(xi )Mij . xi ≤xj Since Mij is nonzero only if xi ≤ xj , we may rewrite this as:   the jth entry of the product g(x1 ) g(x2 ) . . . g(xn ) M .   As P we found above, g(xi ) is the ith entry of the (1×n) matrix  f (x1 ) f (x2 ) . . . f (xn ) Z. Then, xi ≤xj g(xi )Mij = the jth entry of f (x1 ) f (x2 ) . . . f (xn ) ZM . Since ZM is the n × n identity   matrix, we find that this product is simply f (x1 ) f (x2 ) . . . f (xn ) . The jth entry, then, is f (xj ). Therefore, X g(xi )Mij = f (xj ) , xi ≤xj and we have proven Theorem 4.1. 5 The Principle of Inclusion and Exclusion The combinatorially invaluable principle of inclusion and exclusion is a tool used to indirectly count the number of elements in some universal set that satisfy a given condition. Essentially, we count the number of things that do not satisfy our given condition, and subtract that number from the size of the universal set. Certainly it is sometimes easier to directly count how many things satisfy the condition. However, in many cases, the principle of inclusion and exclusion provides a vastly expedited method. Though the proof of the principle of inclusion and exclusion typically follows a combinatorial argument, we will provide an alternate method of proving its validity using the Möbius inversion formula (see Theorem 4.1). 5.1 A Bit of an Aside In order to prove the principle of inclusion and exclusion using the Möbius inversion formula, we first must establish several properties of set unions and intersections. While the results of this section are necessary to our later proof of the principle of inclusion and exclusion, their proofs, though interesting in and of themselves, become a bit tedious. The squeamish reader may accept the final result of the section without proof and pass on to Section 5.2. We will begin by letting A1 , A2 , . . . , Aj be subsets of some set S, and letting J = {1, 2, . . . , j}. 23 Lemma 5.1. Suppose K is a set of positive integers such that K ⊆ J. Then, # " [ \ \ \ c Ai = Ai . Ai ∩ I⊆K i∈K / i∈I i∈I / Proof. We will prove equality by showing that the two sets are subsets of one another. T  T  S T T c∩ c∩ First, let m ∈ A A . Then, m ∈ A A for some I0 ⊆ K and i i i i I⊆K i∈I i ∈I / i∈I i ∈I / 0 0 T so m ∈ i∈I / 0 Ai . T T T Note that i∈I / 0 Ai ⊆ i∈K / Ai . We may see this by noting that if k ∈ i∈I / 0 Ai , then k ∈ Ak1 , Ak2 , Ak3 , . . . , and Ak|J|−|I0 | , where the ki ’s are exactly the elements of the complement of I0 . Some of these ki ’s belong to K. Remove these and notice that the A’s that remain are exactly T those Ai ’s such that i ∈ / K. Then, k ∈ i∈K A i. / Therefore, since m ∈ T i∈I / 0 Ai and T i∈I / 0 Ai ⊆ T i∈K / Ai , it is clear that m ∈ T i∈K / Ai . Thus, " Next, suppose that m ∈ T i∈K / # [ \ I⊆K i∈I Aci ∩ \ Ai ⊆ i∈I / \ Ai . (6) i∈K / Ai . Consider each i ∈ K. If m ∈ / Ai , place i in the set I0 . Otherwise, leave it out. Clearly, I0 ⊆ K. Then, since m is an element of both T i∈K / Ai and T i∈I / 0 , i∈K Ai , it is clear that m ∈ T i∈I / 0 Ai . FromTour definition of I0 , we know that m ∈ / Ai for any i ∈ I0 . So, m ∈ Aci for all i ∈ I0 . Then c m ∈ i∈I0 Ai . Therefore, m ∈ T i∈I0 Aci ∩ T i∈I / 0  T  S T c Ai and so, m ∈ I⊆K / Ai . i∈I Ai ∩ i∈I We have shown that: " \ i∈K / Ai ⊆ # [ \ I⊆K i∈I Aci ∩ \ Ai . i∈I / From Equations 6 and 7, we may conclude that: " # \ [ \ \ Ai = Ai . Aci ∩ i∈K / I⊆K i∈I 24 i∈I / (7) Lemma 5.2. # " [ X \ \ Ai | = | | Aci ∩ I⊆K i∈I I⊆K i∈I / \ Aci ∩ i∈I \ Ai | . i∈I / Proof. Note that it is sufficient to show that the sets in the union on the right-hand side are pairwise disjoint. We will show this by way of contradiction. Suppose m is an element of both T i∈H Aci ∩ T i∈H / Ai and T i∈I Aci ∩ T i∈I / Ai for H, I ⊆ K, H 6= I. We now have several cases: H ⊂ I, I ⊂ H, or H and I are not subsets of one another. Without loss of generality, suppose I ⊂ H or H and I are not subsets of one another. In either of these two cases, there exists l such that l ∈ H but l ∈ / I. Because m ∈ Ai for all i ∈ / I, it is clear that m ∈ Al . Similarly, because m ∈ Aci for all i ∈ H, it is clear that m ∈ Acl . However, this contradicts the fact that m cannot be an element TAl and T of both c∩ A what we assumed is false, and m cannot be an element of both Acl . Therefore, i∈H / Ai i∈H i T T A . and i∈I Aci ∩ i∈I i / Thus, the sets in the union on the right side of the equation in Lemma 5.2 are pairwise disjoint, and so the size of their union is equal to the sum of their individual sizes. We may now easily prove the following: Theorem 5.1. Let A1 , A2 , . . . , Aj be subsets of some set S, let J = {1, 2, . . . , j}, and suppose K is a set of positive integers such that K ⊆ J. Then, \ X \ \ | Ai | = | Aci ∩ Ai | . I⊆K i∈I i∈K / i∈I / Proof. From Lemma 5.1, we know that " | \ Ai | = | i∈K / # [ \ I⊆K i∈I Aci ∩ \ Ai | . i∈I / Substituting in our result from Lemma 5.2, we see that | \ i∈K / Ai | = X \ \ | Aci ∩ Ai | . I⊆K i∈I 25 i∈I / Figure 3: A Venn diagram illustrating the structure of the sets described in Example 5.1. The entire set S is the large box enclosing the Aδ ’s. We mentioned at the beginning of this section that the proof of Theorem 5.1 is a bit galling. As a concrete illustration of the theorem’s worth, consider the following example: Example 5.1. Suppose we know 7 people, whose names are Caleb, Eve, Blake, Kenneth, Scott, Hannah, and Abbey. Our set S is the set of all 7 people, and the subset Aδ of S is the set of people who have at least one “δ” in their first name. Let J = {a, b, c, e, v}, and K ⊆ J be equal to {a, b, c}. A visual description of this setup may be found in Figure 3. Theorem 5.1 tells us that: | \ Aδ | = \ X \ | Acδ ∩ Aδ | . I⊆K δ∈I δ ∈K / δ ∈I / The expression on the left tells us how many of these 7 people have both e’s and v’s in their first name. From simply counting, we see that the size of the set on the left is 1 (only Eve fits into this category). The expression on the right is a bit more cryptic. To understand what it is saying, we must evaluate | \ Acδ ∩ \ Aδ | δ ∈I / δ∈I for each subset I of K. In particular, we have I = ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, or {a, b, c}. T For I = ∅, we have δ∈∅ Acδ representing the T complement of the emptyset (which is the union of all of the Aδ ’s, and thus all 7 people), and δ∈∅ / Aδ representing the intersection of all of the Aδ ’s, where δ ∈ {a, b, c, e, v} (that is, the emptyset). So, their intersection is the emptyset: 26 | \ Acδ ∩ \ Aδ | = |{Caleb, Eve, Blake, Kenneth, Scott, Hannah, Abbey} ∩ ∅| = 0. δ ∈∅ / δ∈∅ T For I = {a}, we see that T δ∈{a} Acδ represents the complement of Aa (which includes exactly Scott, Kenneth, and Eve), and δ∈{a} Aδ represents the intersection of all of the Aδ ’s where δ ∈ {b, c, e, v} / (that is, again, the emptyset). So, their intersection is the emptyset: \ | \ Acδ ∩ Aδ | = |{Eve, Kenneth, Scott} ∩ ∅| = 0. δ ∈{a} / δ∈{a} We may evaluate this intersection for the other subsets of {a, b, c} in a similar fashion, yielding the following. For I = {b}, \ | \ Acδ ∩ Aδ | = |{Eve, Kenneth, Scott, Hannah} ∩ ∅| = 0. δ ∈{b} / δ∈{b} For I = {c}, \ | \ Acδ ∩ Aδ | = |{Eve, Blake, Kenneth, Hannah, Abbey} ∩ ∅| = 0. δ ∈{c} / δ∈{c} For I = {a, b}, | \ \ Acδ ∩ Aδ | = |{Eve, Kenneth, Scott} ∩ ∅| = 0. δ ∈{a,b} / δ∈{a,b} For I = {a, c}, \ | \ Acδ ∩ Aδ | = |{Eve, Kenneth} ∩ ∅| = 0. δ ∈{a,c} / δ∈{a,c} For I = {b, c}, \ | Acδ ∩ δ∈{b,c} \ Aδ | = |{Hannah, Eve, Kenneth} ∩ ∅| = 0. δ ∈{b,c} / For I = {a, b, c}, | \ δ∈{a,b,c} \ Acδ ∩ Aδ | = |{Eve, Kenneth} ∩ {Eve}| = 1. δ ∈{a,b,c} / Adding all of these up, we find that P I⊆K | T δ∈I Acδ ∩ 27 T δ ∈I / Aδ | = 1, as Theorem 5.1 foretold. 5.2 Proof Using Möbius Inversion Theorems 4.1, 5.1 and 3.2 (that is, the Möbius inversion formula, our previous theorem, and the definition of the Möbius function on subsets of a set) allow us to prove the principle of inclusion and exclusion, which is stated below. Theorem 5.2. Let A1 , A2 , . . . , An ⊆ S where S is a finite set, and let [n] = {1, 2, 3, . . . , n}. Then, \ X \ (−1)|I| | Ai | . Aci | = | i∈I I⊆[n] i∈[n] Proof. Let K ⊆ {1, 2, 3, . . . , n} = [n]. By Theorem 5.1, we know that: \ | I⊆K i∈I i∈K / Then, define g(K) = | | \ T i∈K / Aci ∩ i∈K X \ \ | Aci ∩ Ai | . Ai | = i∈I / Ai |. By Theorems 4.1 and 3.2, \ Ai | = X µ(I, K)| I⊆K i∈K / \ Ai | = X (−1)|K|−|I| | I⊆K i∈I / \ Ai | . i∈I / Letting K = [n] and simplifying, | \ i∈[n] Aci ∩ \ \ Ai | = | i∈[n] / Aci | = i∈[n] X (−1)|[n]|−|I| | \ Ai | . i∈I / I⊆[n] We find that the right-hand side of this equation is, in fact, the following sum, with the terms rearranged: X (−1)|I| | \ Ai | . i∈I I⊆[n] Then, | \ i∈[n] Aci | = X (−1)|I| | I⊆[n] 28 \ i∈I Ai | . 5.3 Derangements As was mentioned at the beginning of this section, the principle of inclusion and exclusion is a tool for counting the number of objects that satisfy a given condition. Suppose we would like to count the number of derangements of a sequence. A derangement is defined as follows: Definition 5.1. A derangement of the set [n] = {1, 2, 3, . . . , n} is a permutation π : [n] → [n] such that π(i) 6= i for each 1 ≤ i ≤ n. For example, the only two derangements of {1, 2, 3} are {3, 1, 2} and {2, 3, 1}. The permutation {1, 3, 2}, for example, is not a derangement because 1 appears in its natural place (the first position). We will denote by Dn the set of all derangements of a set of n objects. Unsurprisingly, we find the size of Dn using the principle of inclusion and exclusion. Brualdi [1] offers the following theorem, and we will provide a proof. Theorem 5.3. [1, p.168] For n ≥ 1,   1 1 n 1 Dn = n! 1 − + − . . . + (−1) . 1! 2! n! Proof. Let S be the set of all possible permutations of the set {1, 2, . . . , n}, and let si , where i ∈ {1, 2, . . . , n}, be the set of all permutations such that i falls in the ith position. Then, |Dn | = |S \ (s1 ∪ s2 ∪ . . . ∪ sn ) | = |sc1 ∩ sc2 ∩ . . . ∩ scn | . From the principle of inclusion and exclusion (Theorem 5.2), we see that |Dn | = X (−1)|I| | I⊆{1,2,...,n} \ si | . (8) i∈I This may seem a bit dense, but may be thought of in a very intuitive way. Starting with the set S, we notice that to find Dn we must remove all permutations where any element of {1, 2, . . . , n} is in its “natural” position. In other words, we will subtract the sizes of all of the si ’s. Note that |S| = n! and that if i is in its proper position, the other
elements of the set have (n − 1)! ways of being arranged. So, |S| − |s1 | − |s2 | − . . . − |sn | = n! − n1 (n − 1)! . However, we have now subtracted some permutations several times. For instance, consider a permutation in which the 1st and the 5th elements are both in their “natural” positions. This permutation is in both the set s1 and the set s5 , so we have subtracted it from S at least two times. To rectify this, we add the intersections of any two si ’s back in.

Our new sum is: n! − n1 (n − 1)! + n2 (n − 2)! . Following similar logic, however, and noticing that we continue to add and subtract “too much,” we eventually arrive at the sum: 29 Dn = n! −         n n n n (n − 1)! + (n − 2)! − . . . + (−1)n−1 (1)! + (−1)n (0)! . 1 2 n−1 n The last term of this sum is simply the identity permutation, as we have chosen all n elements to be fixed in their “natural” positions. Note that this equality also comes directly from our application of the principle of inclusion and exclusion in Equation 8. Simplifying, we see that: Dn = n! − n! n! n! (n − 1)! + (n − 2)! − . . . + (−1)n (0)! . 1!(n − 1)! 2!(n − 2)! n!0! And so,   1 1 n 1 Dn = n! 1 − + − . . . + (−1) . 1! 2! n! Example 5.2. Ms.Nomer is a high school math teacher. Whenever she creates a new seating chart for her 5 honors students, she makes sure that no student remains in the desk assigned to them by the previous seating chart. If there are only 5 desks in the classroom, in how many different ways can she create a new seating chart? In other words, we would like to find the number of derangements of {1, 2, 3, 4, 5}. Viewed in the context of the principle of inclusion and exclusion and Theorem 5.3, this problem becomes relatively straightforward:  1 1 1 1 1 D5 = 5! 1 − + − + − 1! 2! 3! 4! 5!  . Simplifying, D5 = 5! − 5! 5! 5! 5! 5! + − + − = 120 − 120 + 60 − 20 + 5 − 1 = 44. 1! 2! 3! 4! 5! Therefore, there are 44 different ways to create a new seating chart for Ms.Nomer’s 5 students so that no student remains in the same desk. 5.3.1 Probability Brualdi [1] goes on to note that because e−1 = P∞ n=0 30 (−1)n n! , e−1 = Dn 1 1 + (−1)n+1 + (−1)n+2 + ... n! (n + 1)! (n + 2)! Recall that: P k Theorem 5.4. [2, p.225] If S is the sum of the convergent alternating series ∞ k=0 (−1) ak , and sn is the nth partial sum of the series, then |S − sn | ≤ an+1 for each positive integer n. 1 In the context of derangements, we see that |e−1 − Dn!n | ≤ (n+1)! . For the first few values of n, 1 1 1 1 = 0.0416, 120 = 0.0083, the right-hand side of the inequality is equal to 2 = 0.5, 6 = 0.16, 24 1 720 = 0.00138. Clearly, the error quickly becomes negligible. Since Dn!n is exactly the probability of choosing a derangement from the set of all permutations of {1, 2, . . . , n}, we see that, for large enough n, this probability is essentially equal to 1e ≈ 0.3679. Example 5.3. A professor is handing homework assignments back to his 30 students. If he does not look at the names on the papers, but hands them back at random, what is the probability that no student will receive his or her own paper? Essentially, we are asking what the probability is that we will create a derangement of a set of 30 objects. From our discussion above, we know that this probability is approximately equal to 1e . Thus, there is about a 37 percent chance that no student will receive his or her own paper. 6 Number Theory In addition to having combinatorial applications, there is a number theoretic concept of Möbius inversion. Though its form is slightly altered, we will see that the version of the theorem found in number theory is parallel to our original statement of the Möbius inversion formula (see Theorem 4.1). Recall from Theorem 3.3 that, in the context of divisors of an integer, µ(a, b) depends only on the quotient ab . So, we may understand the Möbius function evaluated at a single integer: µ(a, b) = µ( ab ). We will use this notation for the remainder of our discussion. 6.1 The Möbius Inversion Formula We will make use of the following definition in our subsequent statement of the theorem: Definition 6.1. A number-theoretic function is a function whose domain is the set of positive integers. 31 LeVeque [5] provides the following theorem. Note that it is merely a form of Theorem 4.1. We will include LeVeque’s proof, but it may clearly be proven as a simple corollary of Theorem 4.1. Theorem 6.1. [5, p.128] If f is any number-theoretic function and X f (d) , F (n) = d|n then f (n) = X d|n X n X n F (d)µ( ) = F ( )µ(d) = µ(d1 )F (d2 ) . d d d1 d2 =n d|n Proof. Suppose that f is any number-theoretic function and X f (d) . F (n) = d|n Then, if d = d1 and n d = d2 , d1 d2 = n and X X n F ( )µ(d) = µ(d1 )F (d2 ) . d d1 d2 =n d|n From our definition of F (n), we see that: X µ(d1 )F (d2 ) = d1 d2 =n X µ(d1 ) d1 d2 =n X f (d) . d|d2 Since d|d2 is equivalent to d| dn1 , we see that the following is true: X d1 d2 =n µ(d1 ) X f (d) = d|d2 X µ(d1 )f (d) = d1 d|n X d|n f (d) X µ(d1 ) . d1 | n d The second and third properties of the Möbius function µ (see Definition 3.1) state that: X d|n ( 1 µ(d) = 0 if n = 1, if n > 1. So, X d|n f (d) X µ(d1 ) = f (n) d1 | n d 32 since the only nonzero term of 6.2 P d1 | n d µ(d1 ) occurs when d = n. Results Möbius inversion in the context of number theory leads to several interesting results. Before we examine one such result, we need the following definition: Definition 6.2. The Euler φ-function evaluated at an integer m (written φ(m)) is the number of positive integers a ≤ m which are relatively prime to m. Recall that two integers are relatively prime if they have no common divisors. We will also make use of the following theorem: Theorem 6.2. [5, p.56] For n > 0, X φ(d) = n . d|n LeVeque [5] asserts the following: Theorem 6.3. φ(n) = n X µ(d) d|n d . Proof. Let F (n) = n for n ∈ Z. Then, from Theorem 6.2, we have: X φ(d) = n = F (n) . d|n Applying Theorem 6.1, it is clear that: φ(n) = X d|n Xn X µ(d) n F ( )µ(d) = µ(d) = n . d d d d|n d|n  Q  LeVeque [5] notes that the usual explicit formula for φ(n), n p|n 1 − p1 , may also be used to derive Theorem 6.3. However, Theorem 6.2 and the Möbius inversion formula give us a rather elegant alternative. LeVeque [5] goes on to provide several exercises for his readers. We will walk through solutions to two such exercises as examples in order to further illustrate the relevance of the Möbius inversion formula. 33 Example 6.1. In this example, we will show that P d2 |n µ(d) = |µ(n)|. Let n be a positive integer. We have two cases: either n is divisible by some square greater than 1, or it is not. In the first case, |µ(n)| = 0, by Theorem 3.3. We may write n = n21 n2 , where n2 is square-free (that is, no square greater than 1 divides n2 ). Suppose d2 divides n for some integer d. We may write d2 uniquely as a product of primes, mk mi 1 m2 d2 = pm 1 p2 · · · pk , where each of the mi ’s is even. Then pi divides n for each 1 ≤ i ≤ k. i i −1 Let 1 ≤ i ≤ k, and suppose pm does not divide n21 . Then pm must divide n21 , since n2 is only i i divisible by, at most, pi . So, the power on pi in the prime decomposition of n21 is odd. However, this contradicts the fact that n21 is a square, and so must have even powers on all of its prime divisors. i Thus, what we assumed is false, and pm divides n21 . So, d2 |n21 . Clearly, the converse is also true: i 2 2 2 if d |n1 , then d |n. Then, we see that the following equality holds, where n1 and n2 are defined as above: X X µ(d) = d2 |n µ(d) . d2 |n21 Note that d2 |n21 if and only if d|n1 , and so: X µ(d) = d2 |n21 X µ(d) . d|n1 But, by the third property of the Möbius function, for n1 > 1, X µ(d) = 0. d|n1 If n1 = 1, then we have moved on to the instance in which n is square-free. There are no d2 ’s, where d > 1, that divide n, and so it is true that |µ(n)| = 1, and X µ(d) = µ(1) = 1. d2 |n In either case, we find that X µ(d) = |µ(n)| . d2 |n 34 Example 6.2. This example focuses on an application of the Möbius inversion formula to classical algebra. We will begin with several definitions to bring our reader up to speed. Definition 6.3. A complex number z = cos(α) + i sin(α) = eiα is called an nth root of unity if z n − 1 = 0, and is a primitive nth root of unity if, in addition, z k − 1 6= 0 for 1 ≤ k < n. Definition 6.4. The nth cyclotomic polynomial, Φn (x), is the monic polynomial of which the zeros are the distinct primitive nth roots of unity. Let n > 1 and ζn = e2πi/n .
n We note that ζn is a primitive nth root of unity. To see that this is true, note that e2πi/n − 1 =
k

2πk e2πi −1 = 1−1 = 0, but that for 1 ≤ k < n, e2πi/n −1 = cos 2πk n +i sin n −1 = (α − 1)+βi, where α 6= 1. So, ζnk − 1 6= 0. Consider, now, ζnj , where 1 ≤ j ≤ n and j and n are relatively prime (denoted by (j, n) = 1). We claim that the ζnj s are exactly the distinct primitive nth roots of unity. We will begin by showing that a given ζnj is an nth root of unity: ζnj
n  n − 1 = e2πij/n − 1 = e2πij − 1 = cos(2πj) + i sin(2πj) − 1 = 1 − 1 = 0. To see that ζnj is a primitive nth root of unity, let 1 ≤ k < n, and consider:
k ζnj  −1= e 2πij/n k −1=e 2πijk/n  − 1 = cos 2πjk n   + i sin 2πjk n To show that the above sum is not equal to zero, we need only show that cos   − 1. 2πjk n  6= 1. To do jk n so, it is sufficient to show that is not an integer. By way of contradiction, suppose that this quotient is, indeed, an integer. Then, n|jk. Since n and j are relatively prime, it must be the case that n|k. However, this contradicts the fact that k < n. Thus, what we assumed is false, and jk n is j not an integer. Then, ζn is a primitive nth root of unity. Next, we must show that the ζnj ’s are distinct. Suppose j and m are distinct 1  integers between  j 2πj 2πj 2πij/n and n, and that each is relatively prime to n. Then, ζn = e = cos n + i sin n and

ζnm = e2πim/n = cos 2πm + i sin 2πm . n n Looking only at the real parts of these two complex numbers, it is clear that cos 2π n  2πj n  6= cos 2πm n
, 2πm n and lie in the same period of the sine function (namely, they are both in the interval since  2π j m n , 2π ). Then, ζn 6= ζn , and we have established uniqueness. Lastly, to see that these are all of the primitive nth roots of unity, suppose t > n or (t, n) = 6 1. In the first case, ζnt = ζnn ζnn−t = ζnn−t (recall that ζn is an nth root of unity). Then, we may 35 restrict our attention to t’s such that (t, n) 6= 1 but 1 ≤ t ≤ n. Suppose (t, n) = b > 1. Then,
n/b ζnt − 1 = e2πit/b − 1. Since bt is an integer, e2πit/b − 1 = 0. But nb < n and so, by Definition 6.3, ζnt is not a primitive root of unity. We have shown that the ζnj ’s are exactly the distinct primitive nth roots of unity. By Definition 6.4, we see that: Y Φn (x) = (x − ζnj ) . 1≤j≤n, (j,n)=1 Q Next, we would like to show that xn − 1 = d|n Φd (x). We know, from the fundamental theorem of algebra, that xn − 1 may be uniquely factored asQa product of (x − zt )’s, where the zt ’s are the distinct nth roots of unity. So, if we can show that d|n Φd (x) is exactly this product, we are done. We just showed that (x − ζdj ) , Y Φd (x) = 1≤j≤d, (j,d)=1 where ζd = e2πi/d . So, Y d|n Φd (x) = Y (x − ζdj ) . Y (9) d|n (1≤j≤d, (j,d)=1) We must show that the ζdj ’s are exactly the n distinct nth roots of unity. First, we will show that if (x − ζdj ) is a divisor of the product on the right in Equation 9, then ζdj is an nth root of unity. Suppose (x−ζdj ) is a divisor of the product in Equation 9. Then, d|n, and ζdj = e2πij/d is a primitive
d
d(n/d) dth root of unity, from our earlier findings. So, it is clear that 1 = e2πij/d = e2πij/d =
n j 2πij/d e , and so ζd is, by definition, an nth root of unity. Next, we must show that all of the nth roots of unity show up in the product, and that each “(x − zt )” occurs only once. Consider zt , an arbitrary nth root of unity. We have two cases: either zt is a primitive nth root of unity, or it is not. In the first case, since n|n, we know that the product Q 1≤j≤n, (j,n)=1 (x − ζnj ) divides the right hand side of Equation 9, where the ζnj ’s are exactly the primitive nth roots of unity (see our earlier discussion). So, (x − zt ) clearly divides our product. In the second case, there exists 1 ≤ k < n such that (ztk − 1) = 0. Choose the minimum such k. 36 Then, zt is a primitive kth root of unity. We claim that k divides n, and will prove our assertion by way of contradiction: suppose k does not divide n. Then, 1 = ztn = ztmk zts = zts , where m is some positive integer and 1 ≤ s < k. However, this contradicts the fact that our chosen k is the smallest integer such that zt is a kth root of unity. Then, what we assumed is false, and k must divide n. Then, (x − zt ) is a divisor of the right-hand side of Equation 9 since k|n and zt is a primitive kth root of unity. From these two cases, we see that all nth roots of unity show up in Equation 9. All that is left to show, then, is that “(x − zt )” occurs only once for each distinct nth root zt . As we saw earlier, each of the ζdj ’s is distinct for a given d. So, suppose that we have zt = ζdj11 = ζdj22 for d1 , d2 |n, d1 6= d2 , 1 ≤ j1 ≤ d1 , 1 ≤ j2 ≤ d2 , (j1 , d1 ) = 1 and (j2 , d2 ) = 1. Then, z is a primitive d1 st root of unity, and is also a primitive d2 nd root of unity. Without loss of generality, suppose d1 < d2 . Then, z d1 − 1 = 0, which contradicts the fact that z is a primitive d2 nd root of unity. Then, what we assumed is false and d1 = d2 . For each distinct nth root Q of unity zt , “(x − zt )” occurs only once in the product of Equation 9. Thus, we have shown that d|n Φd (x) is exactly the product of the distinct (x − zt )’s, where the zt ’s are the n distinct nth roots of unity. Thus, xn − 1 = Y Φd (x) . (10) d|n We may apply the Möbius inversion formula (see Theorem 6.1) to Equation 10. Let F (n) = log(xn − 1) and let f (d) = log (Φd (x)), and note that  log(xn − 1) = log   Y Φd (x) = d|n X log (Φd (x)) d|n implies, by the Möbius inversion formula, that log (Φn (x)) = X d|n X n log(xd − 1)µ( ) = log(xn/d − 1)µ(d) . d d|n Simplifying and rewriting using properties of logarithms, log (Φn (x)) = log Y (xn/d − 1)µ(d) . d|n So, (Φn (x)) = Y (xn/d − 1)µ(d) . d|n 37 Note that the product on the right-hand side is the product of polynomials with integer coefficients. Thus, Φn (x) is a polynomial with integer coefficients. In other words, Φn (x) ∈ Z[x]. 7 Conclusion We have moved from the basic concept of partially ordered sets up through compatible matrices and the Möbius function, arriving at long last at the principle of Möbius inversion and several resulting concepts in combinatorics, number theory, and classical algebra. Our discussion of compatible matrices was really only relevant in reference to the proofs of the existence and uniqueness of the Möbius function, and that of the Möbius inversion formula. While the Möbius function and the Möbius inversion formula are interesting in and of themselves, we have seen them used primarily as a stepping stones in proofs of other results. We see this, for example, in a nontraditional proof of the combinatorially significant principle of inclusion and exclusion. Möbius inversion lies in the intersection of several branches of mathematics. Arguing for its inherent beauty is an irrelevant endeavor, as the reader’s apparent interest in the subject has propelled them as far as this point, but do take a moment to ponder the satisfaction to be found in such a broadly applicable result. In more than a semester’s work of thirty-six pages, this paper could go on to examine further implications of the Möbius inversion formula. Most unfortunately, we must, instead, halt our exploration at this point. However, the end of our narrative should not signal an end to the reader’s curiosity: go forth and invert! References [1] R. A. Brualdi, Introductory Combinatorics, 2nd ed., Prentice Hall, 1992. [2] R. A. Gordon, Real Analysis: A First Course, 2nd ed., Addison-Wesley, 2002. [3] R. P. Grimaldi, Discrete and Combinatorial Mathematics: an Applied Introduction, 3rd ed., Addison-Wesley, 1994. [4] D. C. Lay, Linear Algebra and its Applications, 3rd ed., Addison-Wesley, 2006. [5] W. J. LeVeque, Fundamentals of Number Theory, Dover Publications, Inc., 1977. [6] L. Lovász, Combinatorial Problems and Exercises, North-Holland Publishing Co., 1979. 38