Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 36 ยท Counting Principles

Counting Functions, Subsets and the Division Rule

Count functions between finite sets, injective maps, and subsets with the product rule, then learn the division rule for undoing overcounting. Python checks included.

The product rule has a neat reading in terms of functions. A function from a set A to a set B assigns to every element of A exactly one element of B. Counting functions turns out to count strings, subsets, arrangements and more. This lesson also introduces the division rule, which fixes overcounting.

How many functions?

If |A| = k and |B| = n, a function has k independent decisions, one per element of A, each with n possible values. By the product rule there are n^k functions from A to B. A string of length k over an alphabet of n symbols is just a function from positions {1, ..., k} to the alphabet, which is why there are n^k such strings.

Python All functions from a 3-set to a 2-set

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.

Injective functions

A function is injective (one-to-one) if different inputs always give different outputs. Counting them: the first element of A has n choices, the second n - 1 (it may not reuse the first output), and so on. So the number of injective functions is n ยท (n-1) ยท ... ยท (n-k+1), which is zero when k > n. This is the number of partial permutations.

Python Injective functions

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.

Subsets as functions

A subset of A can be described by a function from A to {0, 1}: 1 means "in", 0 means "out". There are 2^|A| such functions, so a set with n elements has exactly 2^n subsets. This is a bijection between subsets and binary strings, exactly as in Bijections and Double Counting.

Consequences you can derive instantly:

  • Subsets with an even number of elements: half of them, 2^(n-1), when n >= 1.
  • Subsets containing a particular element: 2^(n-1).
  • Non-empty subsets: 2^n - 1.
Python Even-sized subsets

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.

The division rule

Sometimes the easiest way to count is to over-count in a uniform way and then divide. Division rule. If a procedure counts every object of interest exactly d times, the number of objects is (count of the procedure) / d.

Example: seat 4 people around a table with 4 chairs in a row of 4 chairs: 4! = 24 ways. Now suppose the chairs are in a ring and only relative positions matter. Rotating everyone by one seat gives the same arrangement, and each arrangement is counted 4 times (one per rotation). So there are 24 / 4 = 6 circular arrangements.

Python Division rule for circular seating

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.

You will see the division rule again for repeated letters and for combinations, where ordering is removed by dividing by k!.

flowchart LR
    O["Over-count: 24"] --> D["Each object counted 4 times"]
    D --> A["Divide: 24 / 4 = 6"]

Division works only when every object is over-counted by the same factor.

Dividing is valid only if the overcount factor is exactly the same for every object. If some arrangements are counted fewer times (because of symmetry), you need a more careful method.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

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

    Each of the 4 inputs has 3 outputs: 3^4 = 81.
  2. 2. How many injective functions from a 3-element set to a 5-element set?

    5 x 4 x 3 = 60.
  3. 3. How many non-empty subsets does a 6-element set have?

    2^6 - 1 = 63.
  4. 4. When may you use the division rule?

    The uniform overcount factor is what makes the division exact.

Summary

  • There are n^k functions from a k-set to an n-set; strings are functions.
  • Injective functions number n(n-1)...(n-k+1).
  • A set with n elements has 2^n subsets (functions to {0, 1}).
  • The division rule undoes a uniform overcount, as in circular seating.

Next: Permutations