Question

COMBINATORICS:

Let A = {a1,a2,...,am} and B = {b1,b2,...,bn}. how many functions from A to B satisfy
a)f(a1) = b1 and f(a2) = b2?
b)f(a1) = f(a2)?
c)f(a1) does not equal f(a2)?
d)f(a1) is an element of {b1,b2,b3}??

Answer 1

Let's start with just asking the question: How many functions from A to B, without restrictions, are there?

Answer 2

n^m?

Answer 3

Right. Now when we specify that \(f(a_1)=b_1\) and \(f(a_2)=b_2\), all we're really doing is removing two elements from A. So then we just have a function from\[A=\{a_3,a_4,...,a_m\}\]to\[B=\{b_1,...,b_n\}.\]How many functions are there now?

Answer 4

n^m - 2?

Answer 5

or if were just taking 2 elements out of A, then (n-2)^m

Answer 6

The first way was correct. It should be \(\displaystyle n^{m-2}\).

Answer 7

oh yes I mixed that up. thanks.

Answer 8

The second question is a bit trickier. So first, we need to choose what \(f(a_1)\) is. How many options are there for this?

Answer 9

m

Answer 10

Actually, there are \(n\) choices since \(f(a_1)\in\{b_1,...,b_n\}\), and this set has \(n\) elements. But now, we also know that \(f(a_2)=f(a_1)\), so that means that there is only one choice for \(f(a_2)\).

Finally, we just have to finish making the function from \(\{a_3,...,a_m\}\) to \(\{b_1,...,b_n\}\). From the previous question, there are \(n^{m-2}\) ways to do this.

So in total, we have \(n\) choices for \(f(a_1)\) and \(f(a_2)\), and \(n^{m-2}\) choices for the rest. So all we do is multiply them together to get \(n\cdot n^{m-2}=n^{m-1}\) total choices.

Did this all make sense?

Answer 11

yes that did make sense. ok so then if f(a1) ≠ f(a2) then there are n ways to choose f(a1) and n-1 ways to choose f(a2) then there are still m-2 choices for the rest right?

Answer 12

\(n^{m-2}\) ways to choose the rest, but yes, that seems right.

Answer 13

so it would be n·(n-1)·n^m-2

Answer 14

Looks right.

Answer 15

great. starting to make sense now.

Answer 16

And the last problem is similar. How many options for \(f(a_1)\) are there?

Answer 17

3: {b1,b2, b3}

Answer 18

Perfect. And how many choices for the rest of \(A\)?

Answer 19

m-1

Answer 20

\(n^{m-1}\). So the total number of choices is \[3\cdot n^{m-1}\]

Answer 21

ohh right ok. that makes makes sense. beautiful. thanks so much

Answer 22

You're welcome.