Lesson 03 The inclusion exclusion principle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This Jupyter notebook<sup>[1]</sup> 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",
    "    + <a href=\"mailto:juan.klopper@uct.ac.za\">Email me with your thoughts, comments, suggestions and corrections</a> \n",
    "<a rel=\"license\" href=\"http:https://creativecommons.org/licenses/by-nc/4.0/\"><img alt=\"Creative Commons Licence\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http:https://purl.org/dc/terms/\" href=\"http:https://purl.org/dc/dcmitype/InteractiveResource\" property=\"dct:title\" rel=\"dct:type\">The Klopper Lectures on Discrete Mathematics</span> <span xmlns:cc=\"http:https://creativecommons.org/ns#\" property=\"cc:attributionName\"></span> study notes is licensed under a <a rel=\"license\" href=\"http:https://creativecommons.org/licenses/by-nc/4.0/\">Creative Commons Attribution-NonCommercial 4.0 International License</a>.\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:https://ipython.org"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='http:https://fonts.googleapis.com/css?family=Alegreya+Sans:100,300,400,500,700,800,900,100italic,300italic,400italic,500italic,700italic,800italic,900italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http:https://fonts.googleapis.com/css?family=Arvo:400,700,400italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http:https://fonts.googleapis.com/css?family=PT+Mono' rel='stylesheet' type='text/css'>\n",
       "<link href='http:https://fonts.googleapis.com/css?family=Shadows+Into+Light' rel='stylesheet' type='text/css'>\n",
       "<link href='http:https://fonts.googleapis.com/css?family=Philosopher:400,700,400italic,700italic' rel='stylesheet' type='text/css'>\n",
       "\n",
       "<style>\n",
       "\n",
       "@font-face {\n",
       "    font-family: \"Computer Modern\";\n",
       "    src: url('http:https://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunss.otf');\n",
       "}\n",
       "\n",
       "#notebook_panel { /* main background */\n",
       "    background: #ddd;\n",
       "    color: #000000;\n",
       "}\n",
       "\n",
       "\n",
       "\n",
       "/* Formatting for header cells */\n",
       ".text_cell_render h1 {\n",
       "    font-family: 'Philosopher', sans-serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 2.2em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(0, 80, 120);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       ".text_cell_render h2 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 1.9em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(200,100,0);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       "\n",
       ".text_cell_render h3 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    margin-top:12px;\n",
       "    margin-bottom: 3px;\n",
       "    font-style: italic;\n",
       "    color: rgb(94,127,192);\n",
       "}\n",
       "\n",
       ".text_cell_render h4 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "}\n",
       "\n",
       ".text_cell_render h5 {\n",
       "    font-family: 'Alegreya Sans', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 16pt;\n",
       "    color: grey;\n",
       "    font-style: italic;\n",
       "    margin-bottom: .1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".text_cell_render h6 {\n",
       "    font-family: 'PT Mono', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 10pt;\n",
       "    color: grey;\n",
       "    margin-bottom: 1px;\n",
       "    margin-top: 1px;\n",
       "}\n",
       "\n",
       ".CodeMirror{\n",
       "        font-family: \"PT Mono\";\n",
       "        font-size: 100%;\n",
       "}\n",
       "\n",
       "</style>\n",
       "\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "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 $.<p/>\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 $.<p/>\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| $$<p/>\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| $.<p/>\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| $$<p/>\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| $$<p/>\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.<p/>\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 } $$<p/>\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<j }^{  }{ \\left| { A }_{ i }\\cap { A }_{ j } \\right|  } +\\sum _{ i,j,k|i<j<k }^{  }{ \\left| { A }_{ i }\\cap { A }_{ j }\\cap { A }_{ k } \\right|  } +\\dots +{ \\left( -1 \\right)  }^{ n-1 }\\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap \\dots \\cap { A }_{ n } \\right|   $$<p/>  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.<p/>\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} $.<p/>\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<j }^{  }{ \\left| { A }_{ i }\\cap { A }_{ j } \\right|  } +\\sum _{ i,j,k|i<j<k }^{  }{ \\left| { A }_{ i }\\cap { A }_{ j }\\cap { A }_{ k } \\right|  } +\\dots +{ \\left( -1 \\right)  }^{ n-1 }\\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap \\dots \\cap { A }_{ n } \\right|   $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For $ n = 4 $ we have $$ \\left| { A }_{ 1 } \\right| +\\left| { A }_{ 2 } \\right| +\\left| { A }_{ 3 } \\right| +\\left| { A }_{ 4 } \\right| \\\\ -\\left| { A }_{ 1 }\\cap { A }_{ 2 } \\right| -\\left| { A }_{ 1 }\\cap { A }_{ 3 } \\right| -\\left| { A }_{ 1 }\\cap { A }_{ 4 } \\right| -\\left| { A }_{ 2 }\\cap { A }_{ 3 } \\right| -\\left| { A }_{ 2 }\\cap { A }_{ 4 } \\right| -\\left| { A }_{ 3 }\\cap { A }_{ 4 } \\right| \\\\ +\\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 3 } \\right| +\\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 4 } \\right| +\\left| { A }_{ 1 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| +\\left| { A }_{ 2 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| \\\\ +{ \\left( -1 \\right)  }^{ 3 }\\left( \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right|  \\right)   $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are all easy to calculate<br/>\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 $$<p/>\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 $.<p/>\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 $.<p/>\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<j }^{ k,k }{ \\frac { n }{ { p }_{ i }{ p }_{ j } } +\\dots +{ \\left( -1 \\right)  }^{ k-1 }\\frac { n }{ { p }_{ 1 }{ p }_{ 2 }\\dots { p }_{ k } }  }  \\right] $$\n",
    "If you start small and work your way to larger values of $ n $, you will see this ends up being $$ \\phi \\left( n \\right) = n \\left( 1-\\frac { 1 }{ { p }_{ 1 } }  \\right) \\left( 1-\\frac { 1 }{ { p }_{ 2 } }  \\right) \\dots \\left( 1-\\frac { 1 }{ { p }_{ k } }  \\right)  $$\n",
    "We have $ n={ p }_{ 1 }^{ { \\alpha  }_{ 1 } }{ p }_{ 2 }^{ { \\alpha  }_{ 2 } }\\dots { p }_{ k }^{ { \\alpha  }_{ k } } $, where $ {\\alpha}_{i} \\ge 1 $ and the $ {p}_{i} $ values are distinct prime numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Sympy* uses the ```totient()``` function to implement the Euler $ \\phi $ function to calculate relative prime numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$4$$"
      ],
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sym.ntheory.totient(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How did *sympy* do this?  We, it looed at the prime divisors of $ 5 $."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\left [ 5\\right ]$$"
      ],
      "text/plain": [
       "[5]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sym.ntheory.primefactors(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, $ {p}_{1} = 5 $ and it used $ \\phi \\left( n \\right) = n \\left( 1-\\frac { 1 }{ { p }_{ 1 } }  \\right) \\left( 1-\\frac { 1 }{ { p }_{ 2 } }  \\right) \\dots \\left( 1-\\frac { 1 }{ { p }_{ k } }  \\right)  $ to get $$ \\phi \\left( 5 \\right) = 5 \\left( 1 - \\frac{1}{5} \\right) = 5 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Derangements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Derangements** are the permutations of $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} $ in which none of the $ n $ integers appears in its natural place.<p/>\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<j }^{ n }{ \\left| { A }_{ i }\\cap { A }_{ j } \\right|  } =\\begin{pmatrix} n \\\\ 2 \\end{pmatrix}\\left( n-2 \\right) !+\\begin{pmatrix} n \\\\ 3 \\end{pmatrix}\\left( n-3 \\right) ! $$\n",
    "Again, if you start with small sets and work your way up, you will get to $$ \\begin{pmatrix} n \\\\ 1 \\end{pmatrix}\\left( n-1 \\right) !-\\begin{pmatrix} n \\\\ 2 \\end{pmatrix}\\left( n-2 \\right) !+\\begin{pmatrix} n \\\\ 3 \\end{pmatrix}\\left( n-3 \\right) !+\\dots +{ \\left( -1 \\right)  }^{ n-1 }\\begin{pmatrix} n \\\\ n \\end{pmatrix}\\\\ =n!\\left[ 1-\\frac { 1 }{ 1! } +\\frac { 1 }{ 2! } -\\frac { 1 }{ 3! } +\\dots +\\frac { { \\left( -1 \\right)  }^{ n } }{ n! }  \\right]  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}