16.5.2. Non-Onto Functions

Let $\mathcal{H}(n, k)$ denote the number of valid non-onto functions from a set of size $n$ to a set of size $k$. The function counts the number of mappings where not every element in the target set consequently has a pre-image.

A non-onto function is a type of function where some elements in the target set do not have corresponding elements in the domain mapping to them. In mathematical terms, for a function $f: A \rightarrow B$, if there exists at least one element in set $B$ that is not an image of any element in set $A$, then $f$ is non-onto. This section defines a function $\mathcal{H}(n, k)$ that quantifies how many such mappings exist when mapping a set with $n$ elements to another set with $k$ elements.

Think of this as trying to assign people to different tasks. If you have 10 people (the domain) but only 5 tasks (the target), and not all tasks need to be assigned, then some tasks may not have anyone assigned to them. This situation represents a non-onto function.

The total number of functions from a set of size $n$ to a set of size $k$ is given by $k^n$. From this total, we subtract the number of non-onto functions to find the count of onto functions.

The total number of possible functions from set $A$ (of size $n$) to set $B$ (of size $k$) is calculated as $k^n$ because each of the $n$ elements in set $A$ can independently map to any of the $k$ elements in set $B$. To find the number of onto functions, we must subtract the number of non-onto functions, thus helping us understand how many mappings cover every target.

Imagine you have a box of chocolates (size $k$), and you have $n$ friends (size $n$) to share them with. If every friend can choose any chocolate, there are many ways to distribute them. However, if some chocolates are not picked by anyone, that's like having non-onto functions. The onto functions would be the ways to share chocolates such that every type of chocolate gets chosen.

An onto function is characterized by every element in the target set being the image of at least one element from the domain. This ensures that every element is represented in the mapping.

An onto function is a complete mapping from one set to another, meaning each element in the target set is mapped by at least one element in the source set. If such a function exists, it allows a perfect representation of the elements in the target set based on the elements from the domain. This concept is essential for understanding how to create effective and comprehensive mappings in mathematics.

Consider a school where every student (domain) needs to choose a subject (target). If each subject must have at least one student enrolled in it, then every subject is ensured to have representation. This scenario illustrates an onto function since all subjects will have students from among the total population of students.

The recurrence relation for the number of non-onto functions can be formulated based on the number of ways to select proper subsets of the target set and calculate onto functions accordingly.

To derive the recurrence relation for non-onto functions, we can evaluate ways to choose subsets of the target set that will not utilize all elements. For each subset chosen, we can count the number of valid functions that map input to chosen outputs that do not include all elements. This mathematical relationship helps recursively determine the number of ways functions can be formed without being onto.

Imagine you need to hire staff for different departments (target set). If you only choose some of the departments to fill, you can form different teams without needing to fill every department. Each choice of filled departments corresponds to the mathematical concept of non-onto functions, emphasizing the flexibility in hiring.

--