Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 36 · Inclusion-Exclusion

Surjections and Euler's Totient

Use inclusion-exclusion to count onto functions and to derive Euler's totient formula phi(n), with Python checks against brute force.

Inclusion-exclusion has two more flagship applications. First, counting surjections, functions in which every element of the target is hit. Second, counting the integers up to n that share no factor with n, known as Euler's totient function φ(n).

Surjections (onto functions)

A function f: A → B is surjective (onto) if every element of B is the image of at least one element of A. Let |A| = k and |B| = n. All functions number n^k (see Counting Functions and Subsets). A surjection has no element of B left uncovered.

Let Bi be the set of functions that miss the target element i. The functions missing a chosen set of j targets are functions into the other n - j targets: (n-j)^k. By the "none of the properties" form of inclusion-exclusion:

Surj(k, n) = Σ (-1)^j · C(n, j) · (n-j)^k, summing j from 0 to n.

Example: onto functions from 4 elements to 3: 81 - 3·16 + 3·1 - 0 = 36.

Python Surjections: formula versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When k < n the answer is 0, since you cannot cover more targets than you have inputs. The formula handles this automatically.

A practical reading

Surjections count ways to give n distinct tasks to k workers so that nobody is idle, or to put k distinct balls into n distinct boxes with no empty box. Example: 5 distinct letters into 3 distinct mailboxes, all non-empty: 150.

Python Balls into boxes, none empty

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the boxes are identical (unlabelled), divide by n! to get the Stirling numbers of the second kind, a topic of the partitions chapter.

Euler's totient function

φ(n) is the number of integers k with 1 <= k <= n and gcd(k, n) = 1. For example φ(12) = 4 (1, 5, 7, 11) and φ(7) = 6 (every number below a prime).

If n = p1^a1 · ... · pr^ar has prime factors p1, ..., pr, let Ai be the multiples of pi up to n. A number is coprime to n exactly when it is in none of the Ai. The intersection of a chosen group of the Ai is the set of multiples of the product of those primes, of size n / (product). Inclusion-exclusion gives

φ(n) = n · (1 - 1/p1) · (1 - 1/p2) · ... · (1 - 1/pr)

because expanding the product on the right reproduces exactly the alternating sum of n / (product) terms.

Python Totient: three methods

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Useful consequences: for a prime p, φ(p) = p - 1; for a prime power, φ(p^a) = p^a - p^(a-1); and when gcd(m, n) = 1, φ(mn) = φ(m) φ(n). Finally Σ φ(d) over the divisors d of n equals n.

Python Divisor sum of the totient

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart TD
    N["n = p1^a1 ... pr^ar"] --> S["Remove multiples of each prime"]
    S --> P["Add back multiples of pairs"]
    P --> F["phi(n) = n (1-1/p1) ... (1-1/pr)"]

The totient is inclusion-exclusion over the prime divisors of n.

The totient is the engine of modular arithmetic: Euler's theorem says a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1, and RSA encryption depends on it.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many onto functions from a 4-element set to a 2-element set?

    2^4 - 2 x 1^4 + 0 = 14 (all functions minus the two constant ones).
  2. 2. What is φ(20)?

    20 x (1 - 1/2) x (1 - 1/5) = 8.
  3. 3. What is φ(p) for a prime p?

    Every number from 1 to p - 1 is coprime to p.
  4. 4. How many onto functions from a 2-element set to a 3-element set?

    Two inputs cannot cover three targets, so the count is 0.

Summary

  • Surj(k, n) = Σ (-1)^j C(n, j) (n-j)^k counts onto functions from a k-set to an n-set.
  • φ(n) counts integers up to n coprime to n; by inclusion-exclusion φ(n) = n Π (1 - 1/p).
  • Both results are the "none of the properties" form of the sieve.
  • Surjections divided by n! give Stirling numbers of the second kind.

Next: Recurrence Relations