Mobius Inversion Formula - Study Guide

MÖBIUS INVERSION FORMULA 1. Introduction Many problems in mathematics, specifically in combinatorics, can be simplified by a simple change of perspective. Often a difficult counting problem can be solved when the sets are counted in different ways [3]. One tool for proving difficult theorems is the Möbius Inversion Formula, as shown below. To begin, we’ll review some important definitions and theorems from Set Theory. These are used in the definition and proof of the Principle of Inclusion and Exclusion (or PIE). The PIE is fairly commonly used, most obviously in problems such as that in Section 3.1.1, where, given the number of people in a room with certain characteristics, we use the PIE to compute the number of people who don’t share those characteristics. The PIE can be proved by induction using oly the Set Theory explained in Section 2. Alternatively, the Möbius Inversion Formula gives a more elegant proof. In sections 5 through 8, we’ll focus on the Möbius Inversion Formula and Möbius Functions in general. Möbius Functions are piecewise functions defined on any set, partially ordered by some relation. We’ll derive Möbius Functions for a set consisting of sets ordered by inclusion, a set of arborescences ordered, and the set of integers ordered by division. We’ll then examine the Upside-Down Möbius Function, where the relation is defined backwards; that is, if x ≤ y, we would say y ≤∗ x. Finally, we’ll prove the Möbius Inversion Formula by induction. The Möbius Inversion Formula states that given any function f (x), if we define g(x) as follows: X g(x) = f (z), z≤x then f (x) = X g(z)µ(z, x). z≤x Date: 4 April. 1 2 ERIN STUHLSATZ Figure 1. A “union” B, A ∪ B By appropriately defining f (x), we can use the Möbius Inversion Formula to prove the Principle of Inclusion and Exclusion. 2. Very Basic Review 2.1. Definitions. A set is a collection of objects. These objects can be anything from numbers to letters to chickens. The number of objects within a set is the size of the set. If some object x is a member of the set A, we write x ∈ A. The size of the set A is denoted |A|. Some sets, such as the set of whole numbers, are infinite; however, the sets used in this paper are finite. The set with size 0, or the empty set, is denoted ∅. Set Theory requires its own set of operations to define how sets interact. In Figures 1-5, we denote the elements in sets A and B by the points inside the circles labeled A and B respectively. The set consisting of all the elements that are members of A, B, or both is called the union of the two sets A and B, or “A union B”, and is denoted A ∪ B. In Figure 1, A ∪ B consists of the shaded region. This operation can be generalized to more sets. The union of n sets A1 , A2 , ..., An , denoted A1 ∪ A2 ∪ · · · ∪ An is the set consisting of all elements x where x ∈ Ai for at least one i ≤ n. The set of all the elements that are members of both A and B is called the intersection of A and B, or “A intersect B” and is denoted A ∩ B. The shaded region in Figure 2 is the intersection between the sets. Intersection can also be generalized to more sets. The intersection of n sets A1 , A2 , ..., An , denoted A1 ∩ A2 ∩ · · · ∩ An is the set consisting of all elements that are in every Ai . We say a set A is a subset of another set B, or A ⊆ B, if every element in A is also a member of B. In Figure 3 the set A is a subset of the set B, since A is completely contained within B. MÖBIUS INVERSION FORMULA 3 Figure 2. A “intersect” B, A ∩ B Figure 3. A is a subset of B, A ⊆ B Two sets A and B are equal (A = B) if they have all the same elements. This implies that every element of A is also an element of B, and every element of B is also an element of A; that is, both sets are subsets of each other. Where A is a subset of some other set S, the complement of set A, denoted A0 , is the set of all points in S that are not in A. A0 is shown as the shaded section in Figure 4. The set of elements that are in A but not in B, shown as the shaded section in Figure 5, is the difference of the two sets A and B, denoted A − B. A − B is also the intersection of the sets A and B 0 , denoted A ∩ B 0 . Consider A and B to be subsets of the set S={1,2,3,...,10} with A={1,2,3,4} and B={2,4,6,8}. 4 ERIN STUHLSATZ Figure 4. “Compliment” of A, A0 Figure 5. A − B, A ∩ B 0 Then A ⊆ S, A∪B A∩B A0 S−A A0 = = = = = {1, 2, 3, 4, 6, 8}, {2, 4}, {5, 6, 7, 8, 9, 10}, {5, 6, 7, 8, 9, 10}, and S − A. 2.2. Laws. When dealing with operations on the real numbers, there are some basic laws that we take for granted, such as the Associative Law, which states that for any real numbers x, y, and z, we have (x + y) + z = x + (y + z). Two important laws for operations on sets are the Associative and Distributive Laws. Associative Law for Union. The order in which unions are calculated doesn’t affect the final result. (A ∪ B) ∪ C = A ∪ (B ∪ C). MÖBIUS INVERSION FORMULA 5 Proof In order to prove that two sets are equal, we need to show that each set is a subset of the other. If some element x is a member of the first set, it must also be a member of the second, and vice versa. First, assume that x ∈ (A ∪ B) ∪ C. From the definition of the union, either x ∈ A ∪ B or x ∈ C. If the former is true, then either x ∈ A or x ∈ B. This means x is a member of at least one of the sets A, B, or C. Suppose x ∈ B or x ∈ C. Then x ∈ B ∪ C, since this set consists of every element that is a member of B, C, or both. Since x ∈ B ∪ C, then x ∈ A ∪ (B ∪ C). Suppose x ∈ A, then x ∈ A ∪ (B ∪ C). Thus, x ∈ (A ∪ B) ∪ C implies x ∈ A ∪ (B ∪ C), and we have shown (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C). Now, assume y ∈ A ∪ (B ∪ C). Thus, either y ∈ A or y ∈ B ∪ C. Suppose y ∈ B ∪ C. Then either y ∈ B or y ∈ C. So once again, we have that y is a member of at least one of the sets A, B, or C. If y is in A or B, then it will be a member of A ∪ B, and therefore a member of (A ∪ B) ∪ C. If y ∈ C, then we know y ∈ (A ∪ B) ∪ C. Thus, y ∈ A ∪ (B ∪ C) implies y ∈ (A ∪ B) ∪ C, and A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C. Since the two sets are subsets of each other, they must be equal. Therefore, A ∪ (B ∪ C) = (A ∪ B) ∪ C. Since the order in which we compute unions doesn’t affect the final result, the notation A1 ∪ A2 ∪ · · · ∪ An is not ambiguous. Associative Law for Intersection. The order in which intersections are computed doesn’t affect the final set; that is, (A ∩ B) ∩ C = A ∩ (B ∩ C). Proof We’ll proceed by the same method for this law. First, assume x ∈ (A ∩ B) ∩ C. Since this is an intersection, this means x is a member of both A ∩ B and C. Since x is a member of A ∩ B, it must be a member of both A and B as well. So the following are all true: x ∈ A, 6 ERIN STUHLSATZ x ∈ B, and x ∈ C. Since x is a member of both B and C, we have x ∈ B ∩ C. Since it’s a member of A as well, x ∈ A ∩ (B ∩ C). Therefore, any x that is a member of the first set is also a member of the second set, and (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C). Now suppose that y is a member of A∩(B ∩C). Thus, y is a member of both A and B∩C. Since y is a member of B∩C, it must be a member of both B and C. So, we have that y is a member of all three sets A, B, and C. Since y is a member of both A and B, y ∈ A ∩ B. Since y ∈ C as well, y ∈ (A ∩ B) ∩ C. Therefore, any y that is a member of the second set is also a member of the first set, and A ∩ (B ∩ C) ⊆ (A ∩ B) ∩ C. The two sets are subsets of each other, and (A ∩ B) ∩ C = A ∩ (B ∩ C). The Distributive Law for algebra states that x(y + z) = xy + xz. The Distributive Law for sets uses “intersection” and “union” instead of multiplication and addition, but the result is similar. Distributive Law. Given any sets A, B, and C, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Proof First, suppose that x ∈ A ∩ (B ∪ C). So, x ∈ A and x ∈ B ∪ C. Since x ∈ B ∪ C, either x ∈ B or x ∈ C. If x ∈ B, then x is a member of both sets A and B, and x ∈ A ∩ B. If x is a member of C, then it is a member of A ∩ C. So, either x ∈ A ∩ B or x ∈ A ∩ C. Thus, x ∈ (A ∩ B) ∪ (A ∩ C). Therefore, A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C). Now, suppose that y ∈ (A ∩ B) ∪ (A ∩ C). Either y ∈ A ∩ B or y ∈ A ∩ C. If y ∈ A ∩ B, then y is in A and y is in B. If y ∈ A ∩ C, then y ∈ A and y ∈ C. So y is definitely in the set A, and either y ∈ B or y ∈ C. Since y is in either B or C, we have y ∈ B ∪ C. Since it’s in both A and B ∪ C, thus y ∈ A ∩ (B ∪ C). Therefore, (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C). MÖBIUS INVERSION FORMULA 7 Figure 6. |A ∪ B| Since these two sets are subsets of each other, they must be equal. Therefore, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 3. Principle of Inclusion and Exclusion The Principle of Inclusion and Exclusion (PIE) is used to calculate the size of the union of finite sets. We will use the notation PIEn to denote the Principle of Inclusion and Exclusion on n sets. 3.1. PIE2 : The Principle of Inclusion and Exclusion for two sets. In a very simple example, we examine the union of two sets A and B. We can’t calculate the size of the union by simply adding the sizes of the two sets, since they may have elements in common. In Figure 6, if we were to add the sizes of the two sets, the lightly shaded sections would each be counted once. However, the darker section would be counted twice, once as a part of each set. Thus, to ensure that the repeated terms are only counted once, the PIE2 states that given finite sets A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. The following example, which demonstrates an application of the PIE2 , comes from Introduction to Discrete Mathematics [1]. 3.1.1. Example. There are 100 people in a room. In this group, 60 are men, 30 are young, and 10 are young men. How many are old women? Let P be the set of people in the room: |P | = 100. Let M be the set of all men in the room, |M | = 60, and let Y be the set of all young people in the room,|Y | = 30. Then the set of young men will be the set M ∩ Y , and |M ∩ Y | = 10. We want to know the size of M 0 ∩ Y 0 , or the set of all people who are both not young and not men. Thus, we could either count the set of all old women, or we could count the number of 8 ERIN STUHLSATZ people who are either men or young, and subtract that from the total number of people. This is the same as calculating |P | − |M ∪ Y |. By the Principle of Inclusion and Exclusion, |M ∪ Y | = |M | + |Y | − |M ∩ Y |, So, |S| − |M ∪ Y | = |S| − |M | − |Y | + |M ∩ Y | = 100 − 60 − 30 + 10 = 20 There are 20 old women in the room. 3.2. PIE3 . The proof for the Principle of Inclusion and Exclusion with three sets introduces the principles used to prove the general case of the PIE (PIEn ). Principle of Inclusion-Exclusion for 3 sets. Given finite sets A, B, and C |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| Proof Suppose we want to calculate the size of the union of three sets A, B, and C. By the Associative Law, we can calculate the union of three sets in any order we wish, so A ∪ B ∪ C = A ∪ (B ∪ C). Thus, |A ∪ B ∪ C| = |A ∪ (B ∪ C)|. The PIE2 gives the size of the union of any two sets, so |A ∪ (B ∪ C)| = |A| + |B ∪ C| − |A ∩ (B ∪ C)| We can use the PIE2 to find the size of B ∪ C, and we can use the Distributive Law to expand A ∩ (B ∪ C). |A ∪ (B ∪ C)| = |A| + |B| + |C| − |B ∩ C| − |(A ∩ B) ∪ (A ∩ C)|. This last term is another instance of a union between two sets, so we can use the PIE2 once again. |(A ∩ B) ∪ (A ∩ C)| = |A ∩ B| + |A ∩ C| − |(A ∩ B) ∩ (A ∩ C)|. By the Distributive Law, the very last term is equal to A ∩ B ∩ C. Therefore, we can reorganize to find |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. MÖBIUS INVERSION FORMULA 9 3.3. PIEn . We can prove the generalized Principle of Inclusion and Exclusion using induction. We’ve already proved the base case, for PIE2 . To begin, assume that the PIE holds true for n finite sets. Principle of Inclusion-Exclusion for n sets. Given any n sets B1 , B2 , ..., Bn , we assume by induction that |B1 ∪ B2 ∪ · · · ∪ Bn | = |B1 | + |B2 | + · · · |Bn | −(|B1 ∩ B2 | + |B1 ∩ B3 | + · · · + |Bn−1 ∩ Bn |) + |B1 ∩ B2 ∩ B3 | + · · · + |Bn−2 ∩ Bn−1 ∩ Bn | .. . +(−1)n−1 |B1 ∩ B2 ∩ · · · ∩ Bn |. We want to show that the PIE will also be true for n + 1 finite sets; that is, given A1 , A2 ,..., An+1 , |A1 ∪ · · · ∪ An ∪ An+1 | = |A1 | + |A2 | + · · · |An | + |An+1 | −(|A1 ∩ A2 | + |A1 ∩ A3 | + · · · + |An ∩ An+1 |) + |A1 ∩ A2 ∩ A3 | + · · · |An−1 ∩ An ∩ An+1 | .. . +(−1)n |A1 ∩ A2 ∩ · · · ∩ An ∩ An+1 |. By the Associative Law, A1 ∪ A2 ∪ · · · ∪ An+1 = (A1 ∪ A2 ∪ · · · ∪ An ) ∪ An+1 . If we consider A1 ∪ A2 ∪ · · · ∪ An to be one set and An+1 another, then |(A1 ∪A2 ∪· · · An )∪An+1 | = |A1 ∪A2 ∪· · ·∪An |+|An+1 |−|(A1 ∪A2 ∪· · ·∪An )∩An+1 |. To expand the last term, we can use the Distributive Law repeatedly. (A1 ∪A2 ∪· · ·∪An )∩An+1 = (A1 ∩An+1 )∪(A2 ∩An+1 )∪· · ·∪(An ∩An+1 ) We define Bi to be the intersection of Ai and An+1 ; B1 = B2 = .. . A1 ∩ An+1 A2 ∩ An+1 Bn = An ∩ An+1 . Therefore, (A1 ∪ A2 ∪ · · · ∪ An ) ∩ An+1 = B1 ∪ B2 ∪ · · · ∪ Bn . 10 ERIN STUHLSATZ Since the union of all the sets Bi is the union of n sets, we have assumed |B1 ∪ B2 ∪ · · · ∪ Bn | = |B1 | + |B2 | + · · · |Bn | −(|B1 ∩ B2 | + |B1 ∩ B3 | + · · · + |Bn−1 ∩ Bn |) + |B1 ∩ B2 ∩ B3 | + |B1 ∩ B2 ∩ B4 | + · · · |Bn−2 ∩ Bn−1 ∩ Bn | .. . +(−1)n−1 |B1 ∩ B2 ∩ · · · ∩ Bn |. Thus, |A1 ∪ A2 ∪ · · · ∪ An+1 | = |A1 | + |A2 | + · · · |An | + |An+1 | −(|A1 ∩ A2 | + |A1 ∩ A3 | + · · · + |An−1 ∩ An |) + |A1 ∩ A2 ∩ A3 | + · · · |An−2 ∩ An−1 ∩ An | .. . +(−1)n−1 |A1 ∩ A2 ∩ · · · ∩ An | + |B1 | + |B2 | + · · · |Bn | −(|B1 ∩ B2 | + |B1 ∩ B3 | + · · · + |Bn−1 ∩ Bn |) + |B1 ∩ B2 ∩ B3 | + · · · |Bn−2 ∩ Bn−1 ∩ Bn | .. . +(−1)n−1 |B1 ∩ B2 ∩ · · · ∩ Bn |. If we substitute Ai ∩ An+1 back in for Bi and reorganize, we’re left with |A1 ∪ A2 ∪ · · · ∪ An ∪ An+1 | = |A1 | + |A2 | + · · · |An | + |An+1 | −(|A1 ∩ A2 | + |A1 ∩ A3 | + · · · + |An ∩ An+1 |) + |A1 ∩ A2 ∩ A3 | + · · · + |An−1 ∩ An ∩ An+1 | .. . +(−1)n |A1 ∩ A2 ∩ · · · ∩ An ∩ An+1 |. Since the PIEn+1 holds true when we assume PIEn , we’ve proven the generalized Principle of Inclusion and Exclusion for n sets by induction. The following example from Lovász shows how the PIE can be used to solve more complicated problems [2]. 3.3.1. Example. Find a formula for φ(n), the number of integers between 1 and n coprime to n. Any number n can be written as the product of its prime factors. Let n = pα1 1 pα2 2 · · · pαr r . First, we look at a simple case, where n = pα1 1 pα2 2 . Our universal set S consists of the numbers between 1 and n, so |S| = n. We can construct MÖBIUS INVERSION FORMULA 11 two subsets, A1 consisting of all the numbers between 1 and n that have p1 as a factor and A2 consisting of all the numbers between 1 and n that have p2 as a factor. To find the number of integers between 1 and n coprime to n, we can subtract the number of integers that are not coprime to n (the ones that share a common divisor, be it p1 , p2 , or both, p1 p2 ). By the PIE2 , |S − A1 ∩ A2 | = |S| − |A1 | − |A2 | + |A1 ∩ A2 |. The size of the set Ai is pni . Further, A1 ∩ A2 will consist of all the numbers between 1 and n that are divisible by both p1 and p2 , and |A1 ∩ A2 | = p1np2 . Thus, n n n φ(n) = n − − + . p1 p2 p1 p2 Factoring gives: φ(n) = n 1 − = n 1− 1 − 1 + p11p2 p1
p2
1 1 − p12 . p1
Similarly, when n has three prime factors, p1 , p2 , and p3 , let S be the set of numbers between 1 and n, let A1 be the numbers with p1 as a factor, let A2 be the numbers with p2 as a factor, and let A3 be the numbers with p2 as a factor. Then, the intersection of the two sets A2 and A3 is the set of numbers with p2 p3 as a factor, and the intersection of all three sets is the set of numbers with p1 p2 p3 as a factor. So by the PIE3 ,   φ(n) = n 1 − p11 − p12 − p13 + p11p2 + p11p3 + p21p3 − p1 p12 p3     1 1 1 = n 1 − p1 1 − p2 1 − p3 . This can be generalized for n = pα1 1 pα2 2 · · · pαr r . Let S = {1, 2, ..., r}, and let Ai = {k ≤ r| pi divides k}. Thus, φ(n) = |S| ∪ A2 ∪ ·  ··∪A  − |A1 n | = n 1 − p11 1 − p12 · · · 1 − or, using product notation: φ(n) = n r  Y i=0 1− 1 . pi 1 pr  , 12 ERIN STUHLSATZ 4. Principle of Inclusion and Exclusion the Second The former definition of the PIE, while straightforward, has the rather serious drawback that it rarely fits on one LATEXpage. An alternate definition given in Lovász’ book, is much shorter. As before, given some finite set S, let A1 , A2 , ..., An be subsets of S. For any I that is a subset of {1, 2, ..., n}, let \ AI = Ai i∈I A∅ = S. So, the set AI consists of the intersection of all the subsets Ai , where i is an element of I. Some examples of sets under the new definition are as follows: A{1} = A1 A{1,2} = A1 ∩ A2 A{5,12,22} = A5 ∩ A12 ∩ A22 . To define the PIE for these intersections, first assume S has three subsets: A1 , A2 , and A3 . Recall the PIE3 states that: |A1 ∪A2 ∪A3 | = |A1 |+|A2 |+|A3 |−|A1 ∩A2 |−|A1 ∩A3 |−|A2 ∩A3 |+|A1 ∩A2 ∩A3 |. Each of the sets on the right side of the equation can be described by AI , where I ⊆ {1, 2, 3}. A1 = A{1} A2 = A{2} A3 = A{3} A1 ∩ A2 = A{1,2} A1 ∩ A3 = A{1,2} A2 ∩ A3 = A{2,3} A1 ∩ A2 ∩ A3 = A{1,2,3} By the PIE3 , we know |A1 ∪ A2 ∪ A3 | = |A{1} | + |A{2} | + |A{3} | −|A{1,2} | − |A{1,3} | − |A{2,3} | +|A{1,2,3} |. While this doesn’t look any simpler than the previous definition, we can group each of the new subsets according to the size of I. The size of the union of A1 , A2 and A3 is: (1) |A1 ∪ A2 ∪ A3 | = X |I|=1 |AI | − X |I|=2 |AI | + X |AI |. |I|=3 Often, the PIE is applied to a set to calculate how much of the set S lies outside of its subsets. So, we’d like to be able to apply this definition to the problem S − (A1 ∪ A2 ∪ A3 ). Since we’ve defined MÖBIUS INVERSION FORMULA 13 Figure 7. The shaded region is the set S − (A1 ∪ A2 ∪ A3 ). The size of this set can be written either as |S − (A1 ∪ A2 ∪ A3 )| or as |S| − |A1 ∪ A2 ∪ A3 | . A∅ = S, this won’t be exceptionally difficult. By inspecting Figure 4, we can see that . (2) |S − (A1 ∪ A2 ∪ A3 )| = |S| − |A1 ∪ A2 ∪ A3 |. Writing Equation 2 in summation form is even simpler than in the above Equation 1, since the inclusion of the set A∅ guarantees that we’re using all possible subsets of {1, 2, 3}. Thus, (3) |S − A1 ∪ A2 ∪ A3 | = X (−1)|I| |AI |. I⊆{1,2,3} Equation 3 can be generalized quite easily to a set S with n subsets A1 , A2 , ...An , X (4) |S − A1 ∪ A2 ∪ · · · ∪ An | = (−1)|I| |AI |. I⊆{1,2,...,n} 4.1. Example. We can use the new PIE to calculate the number of onto functions with domain of size k and range or size n. Let the domain be the set {1, 2, ..., k} and the codomain be the set {1, 2, ..., n}. First, let the set S refer to the total number of functions with the domain and codomain assigned above. Since there are k elements in the domain and n members of the codomain, there are nk possible functions between them. 14 ERIN STUHLSATZ In order to use the PIE, we need to assign the elements of subsets. Let Ai be the set of functions with domain {1, 2, ..., k} and codomain the set {1, 2, ..., n} without the element i, in other words: {1, 2, .., i − 1, i + 1, ..., n}. So, A5 would be the functions with codomain {1, 2, 3, 4, 6, ...n}. Then the set A2 ∩ A4 is the set of functions with codomain {1, 3, 5, 6, ..., n}. To find the number of onto functions, we’ll subtract the number of functions that miss at least one element of the set {1, 2, ..., n}, so we want to find a formula for |S − (A1 ∪ A2 ∪ · · · ∪ An )|. Recall Equation 4 gives the following formula for the PIE: X |S − (A1 ∪ A2 ∪ · · · ∪ An )| = (−1)|I| |AI |. I⊆{1,2,...,n} Each of the sets A1 , A2 ,..., An will have the same size, since there are equal numbers of sets with the same size domain and codomain, regardless of which element of {1, 2, ..., n} is missing. Thus, every set AI with |I| = 1 has the same size. There will be n sets with |I| = 1, and each set will have size (n − 1)k , since there are n possible choices to remove an element of {1, 2, ..., n}, and there are (n − 1)k functions with domain of size k and codomain of size n − 1. Similarly, when
we calculate the size of
the sets AI when |I| = 2, there will be n2 sets, since there are n2 ways to choose 2 elements from the set of size n. These functions all have domain of size k and codomain of size n − 2. Each set will have size
(n − 2)k . Thus, for AI when |I| = i, we would have ni sets of size (n − i)k . Thus, the number m of onto functions will be given by n X   n (n − i)k . m= (−1) i i=0

n n Because i = n−i , we can revise the sum to show (5) m= n X (−1) i i=0  i    n X n k n+i n (n − i) = (−1) ik . n−i i i=0 If k < n, then obviously m = 0, since no onto functions can exist. If n = k, then any onto funciton is one-to-one and m = n!. Thus, (6) n X    n k 0 0≤k n, we have that the codomain of the function is greater than its domain. Though it’s not easy to use, Equation 6 is the simplest way to count these onto functions. 5. Möbius Functions Before we go on, we define what it means for a set to be partially ordered by some relation. Given a set X, any subset of the product R ⊆ X × X is called a relation. We sometimes write aRb to represent (a, b) ∈ R. A relation is a partial ordering if it has all of the following three properties [1]. (1) Reflexivity: Given x ∈ X, we have xRx or (x, x) ∈ R. That is, every element is related to itself. (2) Antisymmetry: if xRy and yRx, then x = y. If any two elements are each related to each other, then they must be equal. (3) Transitivity: if xRy and yRz, then xRz. Given any relation, we can determine whether it is a partial ordering by checking it against the above properties. Let’s look at an example on the non-negative integers. Suppose xRy whenever x|y, so R contains all the pairs (x, y) where x|y, or whenever there exists some integer k such that xk = y. (1) Reflexivity: Since any number divides itself, x|x, so (x, x) ∈ R. (2) Antisymmetry: Suppose x|y and y|x. Thus there exist integers k and l such that kx = y and ly = x. We can combine these equatinos to find that klx = x. Either x = 0, which is a trivial solution, or kl = 1. Since k and l are both non-negative integers, k = l = 1, so x = y. (3) Transitivity: Suppose x|y and y|z. Then there exist k and l such that kx = y and ly = z. Thus, klx = z. Since k and l are both integers, kl will also be an integer, so x|z. The Möbius Function of V , a finite set {x1 , ..., xn } partially ordered by the relation ≤, is the function µ defined on V × V such that [2]. µ(x, y) = 0 if x 6≤ y µ(x, x) = 1 P x≤y≤z µ(x, y) = 0 (x < z) An easy way of examining relations is to think of them as lines connecting dots. An example is shown in Figure 8, which illustrates the Möbius Function of V = {a, b, c, d}. In this case, a dot x is related 16 ERIN STUHLSATZ Figure 8. A partial ordering of the set {a, b, c, d} to another dot y, or x ≤ y, if they are connected and x is not above y. Therefore, every dot is related to itself and a≤b a≤d b≤d c ≤ d. To determine the Möbius Function for Figure 8, we need to find µ(x, y) for every possible combination of x and y. From the definition of the Möbius Function, we know that for all x ∈ V µ(x, x) = 1, so µ(a, a) = µ(b, b) = µ(c, c) = µ(d, d) = 1. Also, µ(x, y) will be zero whenever x is not related to y. Since d is the maximum point, it isn’t related to any other points, so µ(d, a) = µ(d, b) = µ(d, c) = 0. Similarly, since b and c are both above a, we have µ(b, a) = µ(c, a) = 0. There is no line connecting b and c or a and c, so µ(a, c) = µ(b, c) = µ(c, b) = 0. We’re now left with unknowns for µ(a, b), µ(a, d), µ(b, d), and µ(c, d). We first look at µ(a, b). Recall from the definition of Möbius Functions that given any x and z ∈V, X µ(x, y) = 0. x≤y≤z Since a ≤ a and a ≤ b and there is no other x such that a ≤ x ≤ b, we have µ(a, a) + µ(a, b) = 0. We know already that µ(a, a) = 1, so MÖBIUS INVERSION FORMULA 17 Figure 9. A partial ordering of the set {a, b, c, d, e} µ(a, b) = −1. We can calculate µ(b, d) and µ(c, d) the same way. We know µ(b, b) + µ(b, d) = 0 and µ(b, b) = 1, so µ(b, d) = −1. Also, µ(c, c) + µ(c, d) = 0 and µ(c, c) = 1, so µ(c, d) = −1. Calculation of µ(a, d) is slightly more complicated. There are three elements x that have a ≤ x ≤ d: a≤a≤d a≤b≤d a≤d≤d Since 0= X µ(a, x), a≤x≤d we have 0 = µ(a, a) + µ(a, b) + µ(a, b) = 1 + (−1) + µ(a, d) Therefore, µ(a, d) = 0. This method of piecewise calculating µ for each combination of elements in a set can be used for more complicated relations as well. In Figure 9, µ(a, b) = µ(a, c) = µ(a, d) = µ(b, e) = µ(c, e) = µ(d, e) = −1. In this figure, µ(a, e) is the most interesting to calculate, since there will be five terms included in the sum. 18 ERIN STUHLSATZ Because a is related to every other point, and every point is also related to e, a≤a≤e a≤b≤e a≤c≤e a≤d≤e a ≤ e ≤ e, Thus, X µ(a, x) = µ(a, a) + µ(a, b) + µ(a, c) + µ(a, d) + µ(a, e) = 0 a≤x≤e Recall that µ(a, a) = 1. Note that b, c, and d are each only one step above a; that is, there are no other points x for which a ≤ x ≤ b. Therefore, µ(a, b) = µ(a, c) = µ(a, d) = −1. So, µ(a, e) = 0 − 1 − 3(−1) = 2. Even for the most complicated relations, determining µ(x, y) for any x and y is a simple process. The relation between x and y can be broken down into small steps, each of which we can calculate. Let’s examine the Möbius Functions of some specific relations on various sets V . 5.1. Subsets. First let’s consider the subsets of some set S, which are ordered by inclusion. Since they’re ordered by inclusion, we say A ≤ B if and only if A ⊆ B. We’ll begin with a short example. Given the set S = {1, 2, 3}, we can construct a diagram as shown in Figure 10. Whenever two sets are connected, that means the lower set is a subset of the higher one. Note that there is a top set, the maximum, located at the top, back, right corner of the cube; each subset is related to the set S. Also, the empty set, located at the front, bottom, left corner, is a subset of every other set. The Möbius Function in this case will be µ(A, A) = 1 µ(A, B) = 0 if A 6⊆ B P A⊆C⊆B µ(A, C) = 0 if A ⊆ B The Möbius Functions of each subset with itself will be equal to 1, and then when |A| − |B| = 1, we have µ(A, B) = −1. Now we examine a pair of subsets whose sizes differ by 2. We’ll find µ(A, B) where A = {1} and B = {1, 2, 3}. According to the third part of the formula for constructing a Möbius Function, MÖBIUS INVERSION FORMULA 19 Figure 10. The partial ordering with respect to set inclusion of the set S = {1, 2, 3} X µ({1}, X) = 0. {1}⊆X⊆{1,2,3} Thus, µ({1}, {1}) + µ({1}, {1, 2}) + µ({1}, {1, 3}) + µ({1}, {1, 2, 3}) = 0. We know µ({1}, {1}) = 1, and µ({1}, {1, 2}) = µ({1}, {1, 3}) = −1. Thus, µ({1}, {1, 2, 3}) = 1. Therefore, the Möbius Function of any two subsets with a difference in size of 2 is 1. It now appears that we have a formula for the Möbius Function of subsets ordered by inclusion: µ(A, A) = 1 µ(A, B) = 0 if A 6⊆ B µ(A, B) = (−1)|B|−|A| if A ⊆ B We can prove this result by induction. Let n be the difference in size between sets A and B. So, n = |B| − |A|. We want to show that µ(A, B) = (−1)n . For the base case, let n = 1. Since set B has only one element more than B, there are no other sets C such that A ⊆ C ⊆ B. Therefore, µ(A, A) + µ(A, B) = 0. Since µ(A, A) = 1, we find that µ(A, B) = −1, which is the same as (−1)1 = (−1)n . Assume that our formula holds true for all k < n. So, assume that when |B| − |A| = k, we have µ(A, B) = (−1)k . We want to show that when |B| − |A| = n, we have µ(A, B) = (−1)n . Since A ⊂ B, we know B consists of all the elements of A as well as n extra elements. Recall 20 ERIN STUHLSATZ (7) X µ(A, C) = 0 A⊆C⊆B There exist sets C such that for all x < n, |C| = |A| + x. So, for x = 1, C has one element more than A, and that one
element is one of the extra n elements in B. There are therefore n1 , or n, sets C. Similarly, for |C| = |A| + 2, C consists of A and two other
elements that are two of the n extra elements in B, so there are n2 sets C. So, for Ci defined as any set with |Ci | = |A| + i, we could rewrite Equation 7: 0 = (8) P A⊆C⊆B µ(A, C) n 1 = µ(A, A) +
µ(A, C1 ) + n 2
µ(A, C2 ) + · · · + n n
µ(A, B) Because of our initial assumption, the µ(A, C) is known for all C smaller than B, and µ(A, Ci ) = (−1)i . Thus, (9)           X n n n n n n−1 0= µ(A, C) = − + +· · ·+(−1) + ·µ(A, B) 0 1 2 n−1 n A⊆C⊆B


The numbers n0 n1 · · · nn form the nth row of Pascal’s Triangle, which also gives the coefficients for binomial expansion, as follows: (10) n n (a + b) = a + na n−1     n n n n−1 2 b a b +··· b+ n 2 If we choose a = 1 and b = 1, then Equations 10 and 11 are the same, and we have         n n n n n 0 = (1 − 1) = − + − · · · + (−1) . 0 1 2 n n Since Equations 9 and 10 both add to 0, and every term up until the last is also equal, it follows that     n n · µ(A, B) = (−1)n . n n Therefore, µ(A, B) = (−1)n , and so for all A ⊆ B, where n = |B| − |A|, we have µ(A, B) = (−1)n . MÖBIUS INVERSION FORMULA 21 Figure 11. An Arborescence Figure 12. Another Arborescence 5.2. Arborescences. An arborescence is a partial ordering with a least element where there is a unique path between any two elements. The set in Figure 8 is not an arborescence because it has two minimal elements, a and c. Figure 9 also doesn’t demonstrate an arborescence. Even though a is a least element, there are three paths from a to e. Figures 11 and 12 both represent arborescences. In each case, a is the least element and there is only one possible path to any of the other points. To define the Möbius Function for arborescences, let’s start with a, the least element shown in Figure 11. We know µ(a, a) = 1. The next point, b, will have µ(a, b) = −1, so that µ(a, a) + µ(a, b) = 0. Since there’s only one possible path between any two points, µ(a, c) = µ(a, d) = 0, since it must be true both that µ(a, a) + µ(a, b) + µ(a, c) = 0 22 ERIN STUHLSATZ and µ(a, a) + µ(a, b) + µ(a, c) + µ(a, d) = 0. If we start at b, we find that µ(b, b) = 1, then µ(b, c) = −1, and it follows that µ(c, d) = 0. Similarly, in Figure 12, µ(a, b) = µ(a, c) = −1, since both b and c are only one step away from a. Then µ(a, d) = µ(a, e) = 0, since in both cases there is only one possible way to get from a to d or from a to e, and so µ(a, a) + µ(a, b) + µ(a, d) = 0 and µ(a, a) + µ(a, c) + µ(a, e) = 0. Therefore, for an arborescence V that contains some elements x, y, and z, if we’re finding µ(x, z) and there is no y other than x and z such that x ≤ y ≤ z, then µ(x, z) = −1. Since every path is unique, every z after that, where there is at least one y such that x ≤ y ≤ z will have µ(x, z) = 0. 5.3. Integers. Now let’s examine the Möbius Function for the set of integers 1, ..., n, and we say x ≤ y whenever x|y. Since there are many combinations of integers a and b such that a|b, it would be nice if we could find some way to simplify the problem. We’re going to show that µ(a, b) = µ(1, ab ) by induction. Given any a, we know µ(1, 1) = µ(a, a). Now suppose that µ(1, ac ) = µ(a, c) for all c < b such that a|c and c|b. Note that X µ(a, b) = − µ(a, c). a≤c 1. 6. Upside-Down Möbius Function Before we can examine the Möbius Inversion Formula, there’s one very important Möbius Function to consider. The Upside-Down Möbius Function acts on V ordered by ≤∗ , where x ≤∗ y whenever y ≤ x. We define the Upside-Down Möbius Function as follows: P x≤∗ y≤∗ z µ∗ (x, y) = 0 if x 6≤∗ y µ∗ (x, x) = 1 µ∗ (x, y) = 0 (x <∗ z) This form only illustrates that the Upside-Down Möbius Function is indeed a Möbius Function. To relate it to the previous sections, we’d like to show that µ∗ (x, y) = µ(y, x). 6.0.3. Example. To begin, let’s look at an example. We’ll calculate the Möbius Function and the Upside-Down Möbius Function acting on the set shown in Figure 14. As was shown earlier, µ(a, d) can be calculated by adding up the Möbius Functions of all the elements below d. Recall that X µ(a, x) = 0. a≤x≤d MÖBIUS INVERSION FORMULA 25 Figure 14. A relation on the set {a, b, c, d} So, µ(a, a) + µ(a, b) + µ(a, c) + µ(a, d) = 0. To obtain a formula strictly for µ(a, d), we subtract everything except µ(a, d) to get µ(a, d) = −(µ(a, P a) + µ(a, b) + µ(a, c)) = − a≤x