Counting Functions

Solved Problems

Solution.

1. We see that $$ and $$ The total number of functions $$ is given by
   $$
2. The total number of functions $$ is
   $$
3. There are no injections from $$ to $$ since $$
4. Similarly, there are no surjections from $$ to $$ because $$
5. The number of surjective functions $$ is given by the formula $$ Note that $$ and $$ are interchanged here because now the set $$ is the domain and the set $$ is the codomain. So, we have
   $$
   The Stirling partition number $$ is equal to $$ Hence, the number of surjections from $$ to $$ is
   $$

Solution.

1. The cardinalities of the sets are $$ and $$ Then the total number of functions $$ is equal to
   $$
2. The number of injective functions from $$ to $$ is equal to
   $$
3. Since $$ there are $$ mapping options for the next element $$
   $$
   Respectively, for the element $$ there are $$ possibilities:
   $$
   Thus, there are $$ injective functions with the given restriction.
4. By condition,$$ Then the first element $$ of the domain $$ can be mapped to set $$ in $$ ways:
   $$
   If $$ then $$ has $$ mapping options:
   $$
   If $$ then $$ has $$ mapping options:
   $$
   There are no restrictions for the last element $$. In all cases it can be mapped in $$ ways:
   $$
   Hence, there are $$ injective functions satisfying the given restrictions.

Solution.

The power set of $$ denoted $$ has $$ subsets. The power set of $$ denoted $$ has $$ elements.

The number of functions from $$ to $$ is equal to

Similarly, the number of functions from $$ to $$ is given by

Hence, the mapping $$ contains more functions than the mapping $$

Solution.

The Cartesian square $$ has $$ elements. Similarly, the $$ Cartesian power $$ has $$ elements.

The number of injective functions is given by

Solution.

The total number of functions from $$ to $$ is

To find the number of surjective functions, we determine the number of functions that are not surjective and subtract the ones from the total number.

A function is not surjective if not all elements of the codomain $$ are used in the mapping $$ Since the set $$ has $$ elements, a function is not surjective if all elements of $$ are mapped to the $$ element of $$ or mapped to the $$ element of $$ Obviously, there are $$ such functions. Therefore, the number of surjective functions from $$ to $$ is equal to $$

We obtain the same result by using the Stirling numbers. Given that $$ we have

Solution.

First we find the total number of functions $$

Since $$ there are no surjective functions from $$ to $$

Determine the number of injective functions:

Hence the number of functions $$ that are neither injective nor surjective is $$