{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "+ This Jupyter notebook[1] is part of the Klopper Letures on Discrete Matheamtics and covers *the inclusion-exclusion principle*\n", "+ Created by me, Dr Juan H Klopper\n", " + Head of Acute Care Surgery\n", " + Groote Schuur Hospital\n", " + University Cape Town\n", " + Email me with your thoughts, comments, suggestions and corrections \n", "\"Creative
The Klopper Lectures on Discrete Mathematics study notes is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.\n", "\n", "+ [1] Fernando Pérez, Brian E. Granger, IPython: A System for Interactive Scientific Computing, Computing in Science and Engineering, vol. 9, no. 3, pp. 21-29, May/June 2007, doi:10.1109/MCSE.2007.53. URL: http://ipython.org" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.core.display import HTML\n", "#css_file = 'numericalmoocstyle.css'\n", "#css_file = \"custom.css\"\n", "css_file = 'style.css'\n", "HTML(open(css_file, 'r').read())" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import sympy as sym\n", "import numpy as np\n", "from array import array" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "sym.init_printing(use_latex = \"mathjax\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Inclusion-exclusion principle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## In this lesson" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Follow these links\n", "- [Recap of the counting principle](#Recap-of-the-counting-principle)\n", "- [Counting principles of disjoint sets](#Counting-principles-of-disjoint-sets)\n", "- [The inclusion-exclusion principle](#The-inclusion-exclusion-principle)\n", "- [The applications of the inclusion-exclusion principle](#The-applications-of-the-inclusion-exclusion-principle) (for those interested in number theory)\n", " - [Sieve of Eratosthenes](#Sieve-of-Eratosthenes)\n", " - [Euler's phi function](#Euler's-phi-function)\n", " - [Derangements](#Derangements)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Recap of the counting principle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The **modulus**, also referred to as the **cardinality** of a set is the number of elements in a set. Sets can be **finite** (when there modulus is either $ 0 $ or a natural number. **Infinite** sets can be **countable**, that is when their elements can be arranged as a sequence or **uncountable** if not. Finite sets are countable." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Back to the top](#In-this-lesson)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Counting principles of disjoint sets" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Disjoint sets** are sets that have no elements in common. Their intersection is thus $ \\emptyset $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following **lemmas** apply for disjoint sets under set operations (that's some fancy math speak right there)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- $ n \\left( A \\cup B \\right) = n \\left( A \\right) + n \\left( B \\right) $\n", "- If $ S $ is the disjoint union of two finite sets, $ A $ and $ B $, the $ S $ is finite and $ n \\left( S \\right) = n \\left( A \\right) + n \\left( B \\right) $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If $ A $ and $ B $ are finite sets then the following **corollary** applies\n", "- $ n \\left( A - B \\right) = n \\left( A \\right) - n \\left( A \\cap B \\right) $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For any given set, $ A $, the disjoint union of $ A $ and $ {A}^{c} $ is $ \\mathbb{U} $. This gives us another **corollary**\n", "- $ n \\left( {A}^{c} \\right) = n \\left( \\mathbb{U} \\right) - n \\left( A \\right) $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Back to the top](#In-this-lesson)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The inclusion-exclusion principle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This principle applies when finite sets are not disjoint. The **theorem** of the **inlusion-exclusion principle** then states that\n", "- $ n \\left( A \\cup B \\right) = n \\left( A \\right) + n \\left( B \\right) - n \\left( A \\cap B \\right) $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For three sets we have the **corollary**\n", "- $ n \\left( A \\cup B \\cup C \\right) = n \\left( A \\right) + n \\left( B \\right) + n \\left( C \\right) - n \\left( A \\cap B \\right) - n \\left( A \\cap C \\right) - n \\left( B \\cap C \\right) + n \\left( A \\cap B \\cap C \\right) $" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "We have to extend this to an arbitrary number, say $ n $, of finite sets. Remember that they are all finite $ \\left| {A}_{i} \\right| < \\infty $.

\n", "Let's start with a proof for $ n = 2 $. If they are not disjoint and both in some universal set, then we can make up the following disjoint sets: $ \\left( A \\cap {B}^{c} \\right) $, $ \\left( A \\cap B \\right) $ and $ \\left( {A}^{c} \\cap B \\right) $. Together these disjoint sets make up $ A \\cup B $.

\n", "Because they are disjoint we can calculate the modulus then as $$ \\left| A \\cup B \\right| = \\left| A \\cap {B}^{c} \\right| + \\left| A \\cap B \\right| + \\left| {A}^{c} \\cap B \\right| $$

\n", "Now, if we concentrate on $ A $ only we note that it can be written as $ A = \\left( A \\cap {B}^{c} \\right) \\cup \\left( A \\cap B \\right) $ and because they are disjoint we have $ \\left| A \\right| = \\left| A \\cap {B}^{c} \\right| + \\left| A \\cap B \\right| $.

\n", "For the same reasons $ \\left| B \\right| = \\left| {A}^{c} \\cap B \\right| + \\left| A \\cap B \\right| $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With some algebraic rearangment of the last two modulus euqations, we now have three equations $$ \\left| A \\cup B \\right| = \\left| A \\cap {B}^{c} \\right| + \\left| A \\cap B \\right| + \\left| {A}^{c} \\cap B \\right| \\\\ \\left| A \\cap {B}^{c} \\right| = \\left| A \\right| - \\left| A \\cap B \\right| \\\\ \\left| {A}^{c} \\cap B \\right| = \\left| B \\right| - \\left| A \\cap B \\right| $$

\n", "Substituting the last two equation into the first leaves $$ \\left| A \\cup B \\right| = \\left| A \\right| - \\left| A \\cap B \\right| + \\left| B \\right| - \\left| A \\cap B \\right| + \\left| A \\cap B \\right| $$

\n", "Cancellation leaves us with our required equation $$ n \\left( A \\cup B \\right) = n \\left( A \\right) + n \\left( B \\right) - n \\left( A \\cap B \\right) $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When attempting the inevitable word problems that appear in textbooks remember to see **or** as $ \\cup $ and **and** as $ \\cap $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To attempt a proof for $ n = 3 $ we must take note of the concept of **fundametal products**. It states that for any numbers of sets (all part of a universal set) we can make them up by the union of disjoint sets. These disjoint sets are the fundamental products. There are $ {2}^{n} $ fundamental products for the union of $ n $ sets. The last fundamental product is the complement of the union of all the sets. Together all the fundamental products make up the universal set.

\n", "For our proof for $ n = 3 $ we consider all the fundamental products except the last one. So we consider $ {2}^{3} - 1 = 7 $ fundamental products. They are $$ A\\cap B\\cap C\\\\ A\\cap B\\cap { C }^{ c }\\\\ A\\cap { B }^{ c }\\cap C\\\\ A\\cap { B }^{ c }\\cap { C }^{ c }\\\\ { A }^{ c }\\cap B\\cap C\\\\ { A }^{ c }\\cap { B }^{ c }\\cap C\\\\ { A }^{ c }\\cap B\\cap { C }^{ c } $$

\n", "So the modulus of $ A \\cup B \\cup C $ is the sum of the moduli of all of these fundamental products. We need only expand each set as we did for $ n = 2 $ and substitute to get to $$ n \\left( A \\cup B \\cup C \\right) = n \\left( A \\right) + n \\left( B \\right) + n \\left( C \\right) - n \\left( A \\cap B \\right) - n \\left( A \\cap C \\right) - n \\left( B \\cap C \\right) + n \\left( A \\cap B \\cap C \\right) $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here is the general form of the equation we are after $$ \\left| { A }_{ 1 }\\cup{ A }_{ 2 }\\cup\\dots \\cup{ A }_{ n } \\right| =\\left| \\bigcup _{ i=1 }^{ n }{ { A }_{ i } } \\right| =\\sum _{ i=1 }^{ n }{ \\left| { A }_{ i } \\right| } -\\sum _{ i,j|i If you dissect it for resonable values of $ n $ (just so as to spare some paper), you will get to the equations for $ n = 2 $ and $ n = 3 $ above." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Back to the top](#In-this-lesson)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The applications of the inclusion-exclusion principle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This section is for those that are interested in **number theory**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sieve of Eratosthenes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first example comes from counting the number of primes between $ 1 $ and some integer $ n $. This can be implemented as a dynamically growing sieve of Eratosthenes.

\n", "The Eratosthenes procedure follows this path:\n", "- List all positive integers\n", "- Remove all the multiples of $ 2 $, except for $ 2 $\n", "- Keep the next integer after $ 2 $, which is $ 3 $ and remove all multiples of $ 3 $ except $ 3 $\n", "- Keep the next integer after $ 3 $, which is $ 5 $ and remove all multiples of $ 5 $ except $ 5 $\n", "- Keep the next integer after $ 5 $, which is $ 7 $ and ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The primes would be $ \\left\\{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \\dots \\right\\} $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The *Number Theory* library of *sympy* contains the class ```sieve```. It grows a sieve of Eratosthenes." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# 1 is not a prime\n", "1 in sym.sieve" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can create a list of number and check if they are prime." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 \t False\n", "2 \t True\n", "3 \t True\n", "4 \t False\n", "5 \t True\n", "6 \t False\n", "7 \t True\n", "8 \t False\n", "9 \t False\n", "10 \t False\n", "11 \t True\n", "12 \t False\n", "13 \t True\n", "14 \t False\n", "15 \t False\n", "16 \t False\n", "17 \t True\n", "18 \t False\n", "19 \t True\n", "20 \t False\n", "21 \t False\n", "22 \t False\n", "23 \t True\n", "24 \t False\n", "25 \t False\n", "26 \t False\n", "27 \t False\n", "28 \t False\n", "29 \t True\n" ] } ], "source": [ "# Create a for loop using a numpy range of the values 1 to 29\n", "for i in np.arange(1, 30):\n", " print(i, \"\\t\", i in sym.sieve)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 \t 2\n", "2 \t 3\n", "3 \t 5\n", "4 \t 7\n", "5 \t 11\n", "6 \t 13\n", "7 \t 17\n", "8 \t 19\n", "9 \t 23\n", "10 \t 29\n" ] } ], "source": [ "# Printing a list of the primes 1 through 10\n", "for i in np.arange(1, 11):\n", " print(i, \"\\t\", sym.sieve[i])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, what if we want to exclude all the primes numbers between $ 1 $ and $ $, which are divisible by $ 2, 3, 5, 7 $?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python™ has a function ```%``` which returns a remainder. So, $ 3 $ goes into $ 4 $ once with a remainder of $ 1 $." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$1$$" ], "text/plain": [ "1" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Python code\n", "4 % 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So, if we get a remainder of $ 0 $, it means that one number is divisible by another without a remainder, which is what we want. We can create a simple ```for``` loop with an ```if``` and ```else``` conditionals." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "\n", "\n", "11\n", "13\n", "17\n", "19\n", "23\n" ] } ], "source": [ "for i in np.arange(1, 10):\n", " if sym.sieve[i] % 2 == 0:\n", " print()\n", " elif sym.sieve[i] % 3 == 0:\n", " print()\n", " elif sym.sieve[i] % 5 == 0:\n", " print()\n", " elif sym.sieve[i] % 7 == 0:\n", " print()\n", " else:\n", " print(sym.sieve[i])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Sympy* also has the ```sympy.prime``` and ```sympy.isprime``` keywords." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Is 5 a prime?\n", "sym.isprime(5)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$2$$" ], "text/plain": [ "2" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# What is the first prime?\n", "sym.prime(1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We could have created the ```for``` loop and ```if else``` conditionals above with these ```.isprime()``` and ```.prime``` functions." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Now, though what if we want to calculate all the integers between $ 1 $ and a $ 1000 $, which are not divisible by $ 2, 3, 5 $ and $ 7 $?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can make use of the inclusion-exclusion principle. Let's construct four sets taken from the universal set $ \\mathbb{U} = \\left\\{ x \\quad | \\quad 1 \\le x \\le 1000 \\right\\} $\n", "- $ {A}_{1} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 2\n", "- $ {A}_{2} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 3\n", "- $ {A}_{3} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 5\n", "- $ {A}_{4} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 7" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Therefor, we must have complements\n", "- $ {A}_{1}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 2\n", "- $ {A}_{2}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 3\n", "- $ {A}_{3}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 5\n", "- $ {A}_{4}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 7" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we are looking for $ \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap {A}_{3}^{c} \\cap {A}_{4}^{c} \\right| $. By **De Morgan's law** we have $ {A}_{1} \\cap {A}_{2} \\cap {A}_{3} \\cap {A}_{4} = {\\left( {A}_{1} \\cup {A}_{2} \\cup {A}_{3} \\cup {A}_{4} \\right)}^{c} $.

\n", "We also have that $ \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap {A}_{3}^{c} \\cap {A}_{4}^{c} \\right| = \\left| {\\left( {A}_{1} \\cup {A}_{2} \\cup {A}_{3} \\cup {A}_{4} \\right)}^{c} \\right| = \\left| \\mathbb{U} \\right| - \\left| {A}_{1} \\cup {A}_{2} \\cup {A}_{3} \\cup {A}_{4} \\right| $. Let's calculate the right-hand side." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The modulus of the initial sets are\n", "- $ \\left| \\mathbb{U} \\right| = 1000 $\n", "- $ \\left| {A}_{1} \\right| = \\frac{1000}{2} = 500 $\n", "- $ \\left| {A}_{2} \\right| = \\frac{1000}{3} = 333 $ with a remainder of $ 1 $, thus $ \\left\\lfloor \\frac { 1000 }{ 3 } \\right\\rfloor =333 $\n", "- $ \\left| {A}_{3} \\right| = \\frac{1000}{5} = 200 $\n", "- $ \\left| {A}_{4} \\right| = \\frac{1000}{7} = 142 $ with a remainder of $ 6 $, thus $ \\left\\lfloor \\frac { 1000 }{ 7 } \\right\\rfloor =142 $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Remember our equation $$ \\left| { A }_{ 1 }\\cup{ A }_{ 2 }\\cup\\dots \\cup{ A }_{ n } \\right| =\\left| \\bigcup _{ i=1 }^{ n }{ { A }_{ i } } \\right| =\\sum _{ i=1 }^{ n }{ \\left| { A }_{ i } \\right| } -\\sum _{ i,j|i\n", "(the $ \\left\\lfloor \\quad \\right\\rfloor $ symbol is used for floor division)\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3 } \\right\\rfloor =166 $\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 3 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 5 } \\right\\rfloor = 100 $\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 7 } \\right\\rfloor = 71 $\n", "- $ \\left| { A }_{ 2 }\\cap { A }_{ 3 } \\right| = \\left\\lfloor \\frac { 1000 }{ 3\\times 5 } \\right\\rfloor = 66 $\n", "- $ \\left| { A }_{ 2 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 3\\times 7 } \\right\\rfloor = 47 $\n", "- $ \\left| { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 5\\times 7 } \\right\\rfloor = 28 $\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 3 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3\\times 5 } \\right\\rfloor =33 $\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3\\times 7 } \\right\\rfloor = 23 $\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 5\\times 7 } \\right\\rfloor = 14 $\n", "- $ \\left| { A }_{ 2 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 3\\times 5\\times 7 } \\right\\rfloor = 9 $\n", "- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3\\times 5\\times 7 } \\right\\rfloor =4 $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Getting all the signs right and calculating the right-hand side we have $$ 1000 - \\left( 500 + 333 + 200 + 142 - 166 - 100 - 71 - 66 - 47 - 28 + 33 + 23 + 14 + 9 - 4 \\right) = 228 $$

\n", "This then is the number of integeres between $ \\left[ 1, 1000 \\right] $ not divisible by $2, 3, 5, $ and $ 7 $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Just for interest's sake, there are much easier ways using python™ code. Here we will create a *list* with the values $ 1 $ to $ 1000 $. Then we will run through a ```for``` loop $ 1000 $ times starting at $ 1 $. Everytimes the loop runs we have to make sure the number is still in the *list* or else we will run into problems. If it is, we will check to see if the remainder of dividing that number by $ 2, 3, 5 $ or $ 7 $ is $ 0 $. If so, we remove it from the list. Here is the code." ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "collapsed": false }, "outputs": [], "source": [ "answer = []\n", "\n", "for i in range(1, 1001):\n", " answer.append(i)" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": true }, "outputs": [], "source": [ "for i in range(1, 1001):\n", " if i in answer:\n", " if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0:\n", " answer.remove(i)\n", " else:\n", " answer = answer\n", " else:\n", " answer = answer" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$228$$" ], "text/plain": [ "228" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Checking how many numbers we have left\n", "len(answer)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Back to the top](#In-this-lesson)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Euler's phi function" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "The Euler $ \\phi $ function uses the concept of **relative prime numbers**. Relative prime numbers are positive integers that only have $ 1 $ as a common divisior. So $ 2 $ and $ 5 $ are relative prime numbers, because their ownly common divisor is $ 1 $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We define a positive integer, $ n $. Then we have $ \\phi \\left( n \\right) $ as the number of relative prime numbers in the interval $ \\left[ 1, n \\right] $, which are relatively prime to $ n $.

\n", "So, $ \\phi \\left( 4 \\right) = 2 $. Let's see how that works. On the interval $ \\left[ 1, 4 \\right] $ we have the combinations $ \\left( 1, 4 \\right) $, $ \\left( 2, 4 \\right) $, $ \\left( 3, 4 \\right) $ and $ \\left( 4, 4 \\right) $. In the combination $ 1, 4 $ both only share the common divisor of $ 1 $. In the combination $ 2, 4 $ both are divisible by $ 1 $ and $ 2 $, so they are not relative prime numbers. In the combination $ 3, 4 $ both only share the common divisor of $ 1 $, but again, not so for $ 4, 4 $.

\n", "$ \\phi \\left( 5 \\right) = 4 $, since the combinations $ 1, 2, 3 $ and $ 4 $ with $ 5 $ are all each relatively prime. The combination $ 5, 5 $ has common divisors $ 1 $ and $ 5 $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We also need the notion of a **prime factor**. It is a list of prime numbers in the interval $ \\left[ 1, n \\right] $ that divide into $ n $. So for the numbers $ \\left\\{ 1, 2, 3, 4, 5 \\right\\} $ and thus $ n = 5 $, we have the prime numbers $ \\left\\{ 2, 3, 5 \\right\\} $ and of those only $ 5 $ divides $ 5 $ (without a remainder that is)." ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$\\left [ 5\\right ]$$" ], "text/plain": [ "[5]" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sym.ntheory.primefactors(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have to develop some reasoning for calculating the Euler $ \\phi $ function. Suppose we define the distinct prime divisors of $ n $ as $ {p}_{1}, {p}_{2}, \\dots , {p}_{k} $ and the universal set $ \\mathbb{U} = \\left\\{ 1, 2, \\dots, n \\right\\} $. Then we have the subsets of $ \\mathbb{U} $, named $ {A}_{i} $, consisting of those integers divisible by $ {p}_{i} $. We are looking for all the integers in $ \\mathbb{U} $ that are not divisible by $ {p}_{i} $, therefor $ \\phi \\left( n \\right) = \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap \\dots \\cap {A}_{k}^{c} \\right| $. To calculate $ \\phi \\left( n \\right) $ we thus have $$ \\phi \\left( n \\right) = \\left| \\mathbb{U} \\right| - \\left| {A}_{1} \\cup {A}_{2} \\cup \\dots \\cup {A}_{k} \\right| $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider that if we take a positive integer $ d $ and $ d $ divides $ n $ then there are $ \\frac{n}{d} $ multiples of $ d $ in $ \\mathbb{U} $. So if $ \\mathbb{U} = \\left\\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \\right\\} $, then $ n = 10 $. If $ d = 2 $ then $ \\frac{n}{d} = \\frac{10}{2} = 5 $. So there are $ 5 $ multiples of $ 2 $ in $ \\mathbb{U} $, which is indeed $ \\left\\{ 2, 4, 6, 8, 10 \\right\\} $, with a modulus of $ 5 $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, consider this $$ \\left| { A }_{ i } \\right| =\\frac { n }{ { p }_{ i } } \\\\ \\forall \\quad i\\neq j,\\quad \\left| { A }_{ i }\\cap { A }_{ j } \\right| =\\frac { n }{ { p }_{ i }{ p }_{ j } } $$\n", "This is what we just saw above. This means we have $$ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap \\dots \\cap { A }_{ k } \\right| =\\frac { n }{ { p }_{ 1 }{ p }_{ 2 }\\dots { p }_{ k } } $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since $ \\left| \\mathbb{U} \\right| = n $ we only need $ \\left| {A}_{1} \\cup {A}_{2} \\cup \\dots \\cup {A}_{k} \\right| $. $$ \\phi \\left( n \\right) =n-\\left[ \\sum _{ i=1 }^{ k }{ \\frac { n }{ { p }_{ i } } } -\\sum _{ i=1,j=1,i\n", "So for $ \\left\\{ 1, 2, 3 \\right\\} $, i.e. $ n = 3 $ we have the permutations $$ \\left\\{ 1,2,3 \\right\\} \\\\ \\left\\{ 1,3,2 \\right\\} \\\\ \\left\\{ 2,1,3 \\right\\} \\\\ \\left\\{ 2,3,1 \\right\\} \\\\ \\left\\{ 3,1,2 \\right\\} \\\\ \\left\\{ 3,2,1 \\right\\} $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We note the derangements $ \\left\\{ 2,3,1 \\right\\} $ and $ \\left\\{ 3,1,2 \\right\\} $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To use the inclusion-exclusion principle we define the sets $ {A}_{i} $ to be all the permutations of $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} $ which keeps the element in position $ i $ in its natural place, i.e. where it started off in $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} \\quad \\forall \\quad i = 1, 2, 3, \\dots , n$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As per usual we define a universal set. Here, its is all the permutations of $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we define $ {D}_{n} = \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap \\dots {A}_{n}^{c} \\right| = \\left| \\mathbb{U} \\right| -\\left| { A }_{ 1 }\\cup { A }_{ 2 }\\cup \\dots \\cup { A }_{ n } \\right| $" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The modulus of $ {A}_{1} $ is $ \\left( n-1 \\right)! $. This is the same for all $ \\left| {A}_{i} \\right| $." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are going to build up a summation equation again. For the first term we will have $$ \\sum _{ i=1 }^{ n }{ \\left| { A }_{ i } \\right| } =\\begin{pmatrix} n \\\\ 1 \\end{pmatrix}\\left( n-1 \\right) ! $$\n", "Next up we will have $$ \\sum _{ i