Approach of the value of a rent when non-central moments of the capitalization factor are known: an R application with interest rates following normal and beta distributions Ratio Mathematica Volume 36, 2019, pp. 43-52 43 The inclusion and exclusion principle in view of number theory Viliam Ďuriš* Tomáš Lengyelfalusy † Abstract The inclusion and exclusion (connection and disconnection) principle is mainly known from combinatorics in solving the combinatorial problem of calculating all permutations of a finite set or other combinatorial problems. Finite sets and Venn diagrams are the standard methods of teaching this principle. The paper presents an alternative approach to teaching the inclusion and exclusion principle from the number theory point of view, while presenting several selected application tasks and possible principle implementation into the Matlab computing environment. Keywords: inclusion, exclusion, number theory, combinatorics, Matlab 2010 AMS subject classification: 11B75.‡ * Department of Mathematics, Faculty of Natural Sciences Constantine the Philosopher University in Nitra, Tr. A. Hlinku 1, 949 74 Nitra, Slovakia; vduris@ukf.sk. † Department of Didactics, Technology and Educational Technologies, DTI University Sládkovičova 533/20, 018 41 Dubnica nad Váhom, Slovakia; lengyelfalusy@dti.sk. ‡Received on May 2nd, 2019. Accepted on June 3rd, 2019. Published on June 30th, 2019. doi: 10.23755/rm.v36i1.465. ISSN: 1592-7415. eISSN: 2282-8214. ©Ďuriš, Lengyelfalusy. This paper is published under the CC-BY licence agreement. V. Ďuriš, T. Lengyelfalusy 44 1 Introduction In traditional secondary school mathematics (in combinatorics, number theory or even in probability theory), the notion of factorial and combinatorial numbers is introduced [1]. If n and k are two natural numbers with 𝑛 ≥ 𝑘, then we call a combinatorial number the following notation ( 𝑛 𝑘 ) = 𝑛! (𝑛 − 𝑘)! 𝑘! = 𝑛(𝑛 − 1) … (𝑛 − 𝑘 + 1) 1 ∙ 2 ∙ … ∙ 𝑘 while (factorial of the number n) 𝑛! = 1 ∙ 2 ∙ ⋯ ∙ 𝑛, where 𝑛 > 1, 0! = 1, 1! = 1. For combinatorial numbers, the basic properties apply: ( 𝑛 1 ) = 𝑛 ( 𝑛 0 ) = 1 ( 0 0 ) = 1 ( 𝑛 𝑘 ) = ( 𝑛 𝑛 − 𝑘 ) ( 𝑛 𝑘 ) + ( 𝑛 𝑘 + 1 ) = ( 𝑛 + 1 𝑘 + 1 ) The relation ( 𝑛 𝑘 ) + ( 𝑛 𝑘 + 1 ) = ( 𝑛 + 1 𝑘 + 1 ) is the basis for placing combinatorial numbers in the plane in the shape of a triangle (a so-called Pascal’s triangle) [2], in which combinatorial numbers can be gradually calculated using the fact that ( 𝑛 0 ) = ( 𝑛 𝑛 ) = 1 for each n. ( 0 0 ) ( 1 0 ) ( 1 1 ) ( 2 0 ) ( 2 1 ) ( 2 2 ) ( 3 0 ) ( 3 1 ) ( 3 2 ) ( 3 3 ) ⋯ If n is a natural number, and if a, b are arbitrary complex numbers, then the binomial theorem can be applied by using the form: (𝑎 + 𝑏)𝑛 = ( 𝑛 0 ) 𝑎𝑛 + ( 𝑛 1 ) 𝑎𝑛−1𝑏 + ⋯ + ( 𝑛 𝑛 − 1 ) 𝑎𝑏𝑛−1 + ( 𝑛 𝑛 ) 𝑏𝑛 The special cases of the binomial theorem are as follows: The Inclusion and Exclusion Principle in View of Number Theory 45 a) if 𝑎 = 1, 𝑏 = −1: 1 − ( 𝑛 1 ) + ⋯ + (−1)𝑛−1 ( 𝑛 𝑛 − 1 ) + (−1)𝑛 = 0 b) if 𝑎 = 1, 𝑏 = 1: (1 + 1)𝑛 = ( 𝑛 0 ) + ( 𝑛 1 ) + ⋯ + ( 𝑛 𝑛 − 1 ) + ( 𝑛 𝑛 ) = 2𝑛 Let us consider now N given objects and K properties 𝑎1, … , 𝑎𝐾. Let us denote 𝑁(0) as the number of objects that do not have either of these properties, 𝑁(𝑎𝑖 ) as the number of those that have the property 𝑎𝑖, 𝑁(𝑎𝑖 𝑎𝑗 ) as the number of those that have the property 𝑎𝑖 as well as 𝑎𝑗 etc. Then 𝑁(0) = 𝑁 − ∑ 𝑁(𝑎𝑖 ) + ∑ 𝑁(𝑎𝑖 𝑎𝑗 ) − ∑ 𝑁(𝑎𝑖 𝑎𝑗 𝑎𝑠) + ⋯ + (−1)𝐾 𝑁(𝑎1𝑎2 … 𝑎𝐾 ), where, in the first addition, we sum up using numbers 𝑖 = 1, 2, … , 𝐾, in the second addition, using all pairs of these numbers, in the third addition, using all threesomes of these numbers, etc. We call this relationship the inclusion and exclusion principle [3]. The validity of the inclusion and exclusion principle can be shown from the number theory point of view the way that if an object has no property from the properties 𝑎𝑖 , 𝑖 = 1, ⋯ , 𝐾, so it contributes by the unit value to the left equality, though contributing at the same time to the right side, that is, to the number N (in the following additions it does not reappear). Let an object now have t properties (𝑡 ≥ 1). Then, it does not contribute to the left side as there is a number of objects on the left side that do not have any of the properties. Let us calculate the contribution of this object to the right side. In the first addition, it appears t-times. In the second addition, it appears ( 𝑡 2 )–times because from t properties it is possible to choose pairs of the properties in ( 𝑡 2 ) ways. In the third addition, it appears ( 𝑡 3 )–times, etc., so the total contribution to the right side is as follows: 1 − 𝑡 + ( 𝑡 2 )-( 𝑡 3 )+...+(−1)𝑡−1( 𝑡 𝑡−1 ) + (−1)𝑡 = 0, which is a special case of the binomial theorem. Thus, the total contribution of such an object to both sides is zero and the right side is actually equal to the number of objects that do not have any of the given properties. V. Ďuriš, T. Lengyelfalusy 46 2 Selected examples of the inclusion and exclusion principle The first example requires some mathematical concepts to be recalled. By the Cartesian product of sets A, B we mean set 𝐴 × 𝐵 = {[𝑥, 𝑦]: 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐵}, with the symbol |𝐴| we denote the number of elements (so-called cardinality) of the finite set A. If |𝐴| = 𝑎, |𝐵| = 𝑏, the Cartesian product then contains 𝑎 ∙ 𝑏 of ordered pairs. Since the Cartesian product contains ordered pairs, 𝐴 × 𝐵 is not the same set as 𝐵 × 𝐴. [4] The relation f of set A to set B is called a function of set A to set B if ∀𝑥 ∈ 𝐴∃𝑦 ∈ 𝐵: [𝑥, 𝑦] ∈ 𝑓 and simultaneously if [𝑥, 𝑦] ∈ 𝑓 ∧ [𝑥, 𝑧] ∈ 𝑓, so 𝑦 = 𝑧. The symbol 𝐵 𝐴 denotes a set of all functions 𝐴 → 𝐵. If f is a function of set A into set B and ∀𝑥1, 𝑥2 ∈ 𝐴: 𝑥1 ≠ 𝑥2 ⇒ 𝑓(𝑥1) ≠ 𝑓(𝑥2), the function f is called an injective function of set A into set B (or simply an injection; we also say that the function f is ordinary). Let us now consider two finite sets A, B, where |𝐴| = 𝑛 and |𝐵| = 𝑚. Then the number of all injective functions from A into B is 𝑚 ∙ (𝑚 − 1) ∙ ⋯ ∙ (𝑚 − 𝑛 + 1) = ∏ (𝑚 − 𝑖)𝑛−1𝑖=0 . Injections from set 𝐴 = {1,2, ⋯ , 𝑛} into set B, where |𝐵| = 𝑚, are called variations without repetition (or simply variations) of the n-th class from m elements (of the set B). For these functions, the term 𝑉𝑛(𝑚) is used in practice. It is easier to write the expression 𝑚 ∙ (𝑚 − 1) ∙ ⋯ ∙ (𝑚 − 𝑛 + 1) with the following factorial notation 𝑉𝑛(𝑚) = 𝑚! (𝑚−𝑛)! . Variations of the n-th class from n elements of the set B are bijective functions 𝐴 → 𝐵 and their number is 𝑛 ∙ (𝑛 − 1) ∙ ⋯ ∙ 2 ∙ 1 = 𝑛!. They are called permutations (of set B) and denote 𝑃(𝑛) = 𝑛!. Let us now consider basic set A with the cardinality |𝐴| = 𝑛. Combinations (without repetition) of the k-th class (or k-combinations) from n elements are k- element subsets of set A. We denote them as 𝐶𝑘 (𝑛). If A is a finite set, with |𝐴| = 𝑛, then, the number of k-combinations of elements of set A is 𝐶𝑘 (𝑛) = ( 𝑛 𝑘 ) = 𝑛! (𝑛−𝑘)!𝑘! = 𝑛(𝑛−1)⋯(𝑛−𝑘+1) 𝑘(𝑘−1)⋯1 . [5] Example 2.1. A group of N men is to take part in a chess tournament. Before entering the room, they place their coats in the locker room. However, when they are about to leave, they are unable to recognize their coats. What is the probability that none of them will take their own coat? Solution. Let us denote the coats 1,2, ⋯ , 𝑁. Then the distribution of the coats on the chess players can be made 𝑁!, since these are the permutations of the set {1,2, ⋯ , 𝑁}. First, we determine the number 𝑁(0) of permutations, for which there is no coat on the right player. The number of permutations that do not leave The Inclusion and Exclusion Principle in View of Number Theory 47 in place the k-element set of coats is (𝑁 − 𝑘)! The number of k-sets can be chosen in ( 𝑁 𝑘 ) ways. Then, based on the inclusion and exclusion principle, there applies 𝑁(0) = 𝑁 − ( 𝑁 1 ) (𝑁 − 1)! + ( 𝑁 2 ) (𝑁 − 2)! − ⋯ + (−1)𝑁 ( 𝑁 𝑁 ) (𝑁 − 𝑁)! 𝑁(0) = ∑(−1)𝑘 ( 𝑁 𝑘 ) (𝑁 − 𝑘)! 𝑁 𝑘=0 Next, we get 𝑁(0) = ∑(−1)𝑘 𝑁! 𝑘! (𝑁 − 𝑘)! (𝑁 − 𝑘)! = 𝑁 𝑘=0 𝑁! ∑ (−1)𝑘 𝑘! 𝑁 𝑘=0 All permutations of N elements is N!, hence the likelihood that no chess player is wearing his coat when leaving the tournament is 𝑁! ∑ (−1)𝑘 𝑘! 𝑁 𝑘=0 𝑁! = ∑ (−1)𝑘 𝑘! 𝑁 𝑘=0 Example 2.2. A tennis centre has a certain number of players and 4 groups A, B, C, D. Each player trains in at least one group, while some players train in multiple groups at once according to the table. A.............26 AC...........18 ABC...........5 B.............17 AD...........3 ABD...........0 C.............58 BC...........9 ACD...........2 D.............19 BD...........0 BCD...........0 AB...........7 CD...........5 ABCD........0 We will show how many players have a tennis centre. Solution. Let us denote 𝑀1 as the set of all players in group A, 𝑀2 as the set of all players in group B, 𝑀3 as the set of all players in group C and 𝑀4 as the set of all players in group D. Then, set 𝑁 = 𝑀1 ∪ 𝑀2 ∪ 𝑀3 ∪ 𝑀4 is a set of all players in the centre. V. Ďuriš, T. Lengyelfalusy 48 Based on the inclusion and exclusion principle, there applies: 0 = |𝑀1 ∪ 𝑀2 ∪ 𝑀3 ∪ 𝑀4| − (26 + 17 + 59 + 19) + (7 + 18 + 3 + 9 + 5) − (5 + 2) + 0 From which |𝑀1 ∪ 𝑀2 ∪ 𝑀3 ∪ 𝑀4| = 26 + 17 + 59 + 19 − 7 − 18 − 3 − 9 − 5 + 5 + 2 = 85. As a result, the tennis centre has 85 players. Example 2.3. Let 𝑛 > 1 be a natural number. In number theory, the symbol 𝜑(𝑛) denotes the number of natural numbers smaller than n and relatively prime s n, where 𝜑(𝑛) is called Euler’s function [3]. Let 𝑛 = 𝑝1 𝛼1 … 𝑝𝑘 𝛼𝑘 be a canonical decomposition of the number n. We will show that the following relation applies: 𝜑(𝑛) = 𝑛 (1 − 1 𝑝1 ) (1 − 1 𝑝2 ) … (1 − 1 𝑝𝑘 ) Solution. Once more, we will use the inclusion and exclusion principle. Let 𝑛 = 𝑝1 𝛼1 𝑝2 𝛼2 … 𝑝𝑘 𝛼𝑘 is a canonical decomposition of the number n. The natural numbers that are relatively prime with the number n are those that are not divisible by either of the prime numbers 𝑝1, 𝑝2, … , 𝑝𝑘. So, let 𝑎𝑖 mean the property that “the number m is divisible by the prime number 𝑝𝑖 , 𝑖 = 1, … , 𝑘“. The number of numbers that are smaller or equal to the number n and are divisible by the number 𝑝𝑖 is 𝑁(𝑎𝑖 ) = 𝑛 𝑝𝑖 . It is an integer since 𝑝𝑖 ⃓𝑛. Next, we get 𝑁(𝑎𝑖 𝑎𝑗 ) = 𝑛 𝑝𝑖𝑝𝑗 and other members of the notation. Then: 𝜑(𝑛) = 𝑛 − ∑ 𝑛 𝑝𝑖 + ∑ 𝑛 𝑝𝑖 𝑝𝑗 − ∑ 𝑛 𝑝𝑖 𝑝𝑗 𝑝𝑠 + ⋯ + (−1)𝑘 𝑛 𝑝1𝑝2 … 𝑝𝑘 This expression can be simplified to the form: 𝜑(𝑛) = 𝑛 (1 − 1 𝑝1 ) (1 − 1 𝑝2 ) … (1 − 1 𝑝𝑘 ) Several other interesting tasks and applications of the inclusion and exclusion principle can be found e.g. in the resources [6], [7]. The Inclusion and Exclusion Principle in View of Number Theory 49 3 Implementation of the inclusion and exclusion principle in the Matlab computing environment When solving various practical tasks with pupils, it is possible and appropriate to use some computing environment, e.g. Matlab. We will now solve a simple task of divisibility. Example 3.1. We will show how many numbers there are up to 1000 that are not divisible by three, five, or seven. Solution. Before proceeding to the solution of the task, we will use divisibility relations to determine the number of all natural numbers smaller than 1000, each of which can be divided simultaneously by three, five, and seven. First, we will generally show that if 3|𝑎, 5|𝑎, then 3 ∙ 5 = 15|𝑎, being valid if 3|𝑎, so 𝑎 = 3𝑏, if 5|𝑎, so 𝑎 = 5𝑐. The left sides are equal, so the right sides must be equal, too. Then 3𝑏 = 5𝑐 Since (3,5) = 1 ⇒ 3|c ⇒ 𝑐 = 3𝑑. Then 𝑎 = 5𝑐 = 15𝑑 ⇒ 15|𝑎. Now, we will show that if 15|𝑎, 7|𝑎, then 15 ∙ 7 = 105|𝑎 is valid if 15|𝑎, so 𝑎 = 15𝑒, if 7|𝑎, so 𝑎 = 7𝑓. Since 𝑎 = 𝑎, it holds true that 15𝑒 = 7𝑓 From the relation (15,7) = 1 ⇒ 15|f ⇒ 𝑓 = 15𝑔. Then 𝑎 = 7𝑓 = 105𝑔 ⇒ 105|𝑎. We will do the division 1000 105 = 9 + 55 105 and we see that there exist 9 numbers with the required property. Let us get back to our basic task. There, we have 𝑁 = 1000. Let 𝑎1 be the property that “the number n is divisible by three“, property 𝑎2 stand for “the number n is divisible by five“, property 𝑎3 stand for “the number n is divisible by seven“. At the same time, 𝑁(0) is the number of searched numbers not divisible by any of the numbers 3, 5, 7. Every third natural number is divisible by three since 1000 = 3 ∙ 333 + 1. We have the number 𝑁(𝑎1) = 333, that is 333 numbers up to 1000 are divisible by three. By similar consideration, we determine 𝑁(𝑎2) = 200, 𝑁(𝑎3) = 142. V. Ďuriš, T. Lengyelfalusy 50 Based on the previous considerations, we determine the number 𝑁(𝑎1𝑎2). It holds true that if a number is divisible by three and five, it is also divisible by its product, i.e. by the number 15 (inasmuch as the numbers 3 and 5 are relatively prime). Hence, 𝑁(𝑎1𝑎2) equals the number of numbers up to 1000 divisible by 15 and 𝑁(𝑎1𝑎2) = 66. Similarly, we determine 𝑁(𝑎2𝑎3) = 28 and 𝑁(𝑎1𝑎3) = 47. For the number 𝑁(𝑎1𝑎2𝑎3) it is valid that it will be equal to the number of numbers up to 1000 that are divisible by the product 3 ∙ 5 ∙ 7 = 105, hence 𝑁(𝑎1𝑎2𝑎3) = 9. Then, based on the inclusion and exclusion principle, we have in total 𝑁(0) = 1000 − (333 + 200 + 142) + (66 + 28 + 47) − 9 = 457 Now we implement the given task into the Matlab computing environment to verify the result. First we create the function “count_the_divisors”, which is the application of the inclusion and exclusion principle: function cnt = count_the_divisors(N, a, b, c) cnt_3 = floor(N / a); %counts of numbers divisible by a cnt_5 = floor(N / b); %counts of numbers divisible by b cnt_7 = floor(N / c); %counts of numbers divisible by c cnt_3_5 = floor(N / (a * b)); %counts of numbers divisible by a and b cnt_5_7 = floor(N / (b * c)); %counts of numbers divisible by b and c cnt_3_7 = floor(N / (a * c)); %counts of numbers divisible by a and c cnt_3_5_7 = floor(N / (a * b * c)); %counts of numbers divisible by a, b and c %and now inclusion-exclusion principle applied cnt = N - (cnt_3 + cnt_5 + cnt_7) + (cnt_3_5 + cnt_5_7 + cnt_3_7) - cnt_3_5_7; We will call the function from the command line: >> N = 1000; >> count_the_divisors(N, 3, 5, 7) The Inclusion and Exclusion Principle in View of Number Theory 51 ans = 457 When creating functions or scripts solving various problems based on the inclusion and exclusion principle, it is possible to use various set operations (functions) built directly in Matlab without the need to create one’s own structures. [8] 4 Conclusion The principle of inclusion and exclusion is a “set problem“ that falls within the field of discrete mathematics with different applications in combinatorics. However, this principle also plays a significant role in number theory when defining the so-called Euler’s function or Fermat’s theorem, or in clarifying and exploring the fundamental problems of number theory, such as expressing the distribution of prime numbers among natural numbers on the numerical axis and many other questions still open today. The paper offered something different than just a set view of the inclusion and exclusion principle and its definition using number theory knowledge and the properties of combinatorial numbers. Our work is a guideline for solving selected practical tasks in which the involvement of the principle might not be expected at first sight. We also showed the possible application of ICT and the Matlab computing environment in solving computational problems in the field of number theory, which can be concurrently involved in mathematics teaching. In conclusion, the inclusion and exclusion principle has much more application than we allege in our short contribution and can be used to solve more difficult tasks, e.g. in algebra to solve specific systems of equations or to solve various problems in combination with the Dirichlet principle. Some research shows that the ability to solve problems also depends on the substitution thinking, which makes possible to use mathematical knowledge effectively in various areas of number theory [9]. V. Ďuriš, T. Lengyelfalusy 52 References [1] J. Sedláček. Faktoriály a kombinační čísla. Praha, Mladá fronta, 1964. [2] A. Vrba. Kombinatorika. Praha: Mladá fronta, 1980. [3] Š. Znám. Teória čísel. Bratislava, SPN, 1975. [4] M.T. Keller, W.T. Trotter. Applied Combinatorics. American Institute of Mathematics, 2017. [5] M. Škoviera. Úvod do diskrétnej matematiky. Bratislava, Katedra informatiky FMFI UK, 2007. [6] K. H. Rosen. Discrete mathematics and its applications. 4th ed., WCB/McGraw Hill, Boston, 1999. [7] M.J. Erickson. Introduction to Combinatorics. John Wiley & Sons, New York, ISBN: 0-471-15408-3, 1996. [8] Mathwork. Online documentation. 2019. Available at: https://www.mathworks.com/help/matlab/set-operations.html, Accessed 15th of April 2019. [9] D. Gonda: The Elements of Substitution Thinking and Its Impact On the Level of Mathematical Thinking. In: IEJME — MATHEMATICS EDUCATION, vol. 11, no. 7, p. 2402-2417, Look Academic Publishers, 2016.