Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $F$ denote the set of all functions from $\{1,2,3\}$ to $\{1,2,3,4,5\}$

a) Find and simplify the number of functions $f$ in $F$ so that $f(1)=4$.

b) Find and simplify the number of one-to-one functions $f$ in $F$ so that $f(1)$ is greater than or equal to $4$.

c) Find and simplify the number of functions $f$ in $F$ so that $f(1)$ does not equal $f(2)$.

For (a) I have no idea how to write it out, and for (c) can't I make $f(1)=1$ and $f(2)=2,3,4,5$ that way they don't equal each other?

share|improve this question
    
For c) you have to work out, for each choice of $f(1)$, how many allowable choices there are for $f(2)$, and then you still have to think about the number of possibilities for $f(3)$. –  Gerry Myerson May 24 '13 at 9:32
add comment

2 Answers 2

a) We introduce some notation: Let $A,B$ be abitrary, non-empty (finite) sets and let $A^B := \{f \subseteq A \times B \ | \ f: A \mapsto B \}$. Let (for a given set $A$) $|A|$ be the number of elements of $A$. Now, a nice way to solve your problem is the following:

  1. Show that $|A^B| = |A|^{|B|}$

  2. Show that $F_a := \{ f \in F \ | \ f(1) = 4 \} \overset{\text{bijective}}\cong \{2,3\}^{\{1,2,3,4,5\}}$

b) Assuming "one-to-one functions" refers to injective functions: Let $F_b := \{ f \in F \ | \ f \text{ is injective }, f(1) \ge 4 \}$. Then $F_b$ is the disjoint union $F_b = \{ f \in F \ | \ f \text{ is injective }, f(1) = 4\} \cup \{ f \in F \ | \ f \text{ is injective }, f(1) = 5\}$. Hence, it is sufficient to prove that

  1. $X := \{ f \in F \ | \ f \text{ is injective }, f(1) = 4\} \overset{\text{bijective}}\cong \{ f \in F \ | \ f \text{ is injective }, f(1) = 5\} \overset{\text{bijective}}\cong \{ (x,y) \in \{1,2,3,4\} \times \{1,2,3,4\} \ | \ x \neq y \}$
  2. $|\{ (x,y) \in \{1,2,3,4\} \times \{1,2,3,4\} \ | \ x \neq y \}| = |\{1,2,3,4\}\times\{1,2,3,4\}| - |\{(1,1),(2,2),(3,3),(4,4)\}| = 4^2-4$

c) Let $F_c := \{ f \in F \ | \ f(1) \neq f(2)\}$. Then $F_c = F \setminus F_{1,2}$, where $F_{1,2} := \{ f \in F \ | \ f(1) = f(2) \}$ and show that $F_{1,2} \overset{\text{bijective}}\cong \{2,3\}^{\{1,2,3,4,5\}}$. Finally use the technique developed in a) to calculate $|F|$ and $|F_{1,2}|$ which allows you to get $|F_c| \overset{!}= |F| - |F_{1,2}|$.

share|improve this answer
    
It’s not necessary to assume that one-to-one function means injective function, since it’s a standard term that never means anything else. –  Brian M. Scott May 24 '13 at 16:29
add comment

This whole problem is basically just an exercise in using the multiplication principle, also sometimes called the Chinese menu principle:

Suppose that you are making a sequence of $k$ choices. There are $n_1$ different ways to make the first choice, $n_2$ different ways to make the second choice, and so on, through $n_k$ different ways to make the $k$-th choice. Then there are altogether $n_1n_2\dots n_k$ different ways to make the whole sequence of choices.

(a) Once you set $f(1)=4$, you must assign values to $f(2)$ and $f(3)$. In each case this means picking one of the $5$ numbers $1,2,3,4$, and $5$, so there are $5\cdot5=25$ ways to make the two choices. Once you’ve done that, you’ve completely defined the function $f$, so there are $25$ functions $f:\{1,2,3\}\to\{1,2,3,4,5\}$ such that $f(1)=4$.

(b) The same basic approach to solving the problem and to explaining the solution can be used here as well.

(c) No, you can’t simply make $f(1)=1$ and choose $f(2)\in\{2,3,4,5\}$: if you count only those functions, you’re missing all of the functions that have $f(1)=3$ and $f(2)=5$, for instance. Once again look at it in terms of building $f$ one value at a time. You can let $f(1)$ be any of the five numbers $1,2,3,4$, and $5$. No matter which value you choose, you can let $f(2)$ be any of the four remaining numbers. Finally, you can let $f(3)$ be any of the five numbers. This sequence of three choices can be made in $5\cdot4\cdot5=100$ ways.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.