Exercise 1.11

Question

Let A and B be sets with $|A| = n$, $|B| = m$.
\begin{enumerate}[label=(\alph*)]
\item How many functions are there from $A$ to $B$ (i.e., functions with domain $A$, assigning
an element of $B$ to each element of $A$)?
\item How many one-to-one functions are there from $A$ to $B$? (See Section A.2.1 of the
math appendix for information about one-to-one functions.)
\end{enumerate}

fifthist x · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item   Each of the $n$ inputs has $m$ choices for an output, resulting in 
$$m^{n}$$ possible functions.

\item   If $n < m$, at least two inputs will be mapped to the same output, 
so no one-to-one function is possible. 
  
  If $n \geq m$, the first input has $m$ choices, the second input has $m - 1$ 
  choices, and so on. The total number of one-to-one functions then is 
  $$m(m-1)(m-2)\dots(m-n+1)$$
\end{enumerate}

Exercise 1.11

Answers

Comments

Exercise 1.11

Answers

Comments

Add answer