Skip to main content Accessibility help
Internet Explorer 11 is being discontinued by Microsoft in August 2021. If you have difficulties viewing the site on Internet Explorer 11 we recommend using a different browser such as Microsoft Edge, Google Chrome, Apple Safari or Mozilla Firefox.

Chapter 12: Counting functions and subsets

Chapter 12: Counting functions and subsets

pp. 144-156

Authors

, University of Manchester
  • Add bookmark
  • Cite
  • Share

Summary

Very many counting problems can be formulated in terms of counting the number of functions between two sets (possibly satisfying certain properties) or counting the number of subsets of a given set (possibly satisfying certain properties). In this chapter we give a brief introduction to these ideas. They naturally lead to the binomial coefficients, one of the most important families of numbers in all mathematics.

Counting sets of functions

Suppose that X and Y are finite sets. It is natural to ask how many different functions there are with domain X and codomain Y. For example, if X is a set of people and Y is a set of dishes on a menu, then each function XY represents a choice of (one) dish for each person, so that the number of functions represents the number of possible orders by the set of people. If S is a set of students and T is a set of tutors then a function ST is an assignment of a tutor for each student.

There is another increased level of abstraction here. The idea of treating a set, for example the set of integers, as a single mathematical object is one stage of abstraction. A further stage is viewing a function from one set to another as a single mathematical object. But now we are forming a new set whose elements are the functions from one set to another and asking questions about this set.

About the book

Access options

Review the options below to login to check your access.

Purchase options

Hardback
US$195.00
Paperback
US$54.00

Have an access code?

To redeem an access code, please log in with your personal login.

If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.

Also available to purchase from these educational ebook suppliers