1. ## Discrete Math!

1. (a) Use the product rule to prove that the number of functions from an n-element set to an m-element set is m^n.

(b) Use a counting argument to show that the multinomial coefficient
C(mn; n, n,..., n) is between m^n and m^(mn).

2. Suppose that S is a subset of {1, 2,..., 2n} of size n+1.
(a) Show that S must contain two integers a and b such that gcd(a,b)=1.

(b) Show that S must contain two integers c and d such that c divides d.

I'm no good at "showing" and "proving" so any help is much appreciated...thanks!

2. Originally Posted by noles2188
1. (a) Use the product rule to prove that the number of functions from an n-element set to an m-element set is m^n.
For starters, here's a solution for 1. (a).

A function is a mapping which assigns, to every element from the starting set, in this case the $\displaystyle n$-element set, exactly one element from the target set, in this case the $\displaystyle m$-element set.

As this mapping has to be done for each of the $\displaystyle n$ elements from the starting set, or domain, we might as well line all those elements up and see which elements from the codomain (or target set) can be assigned to them.

To the first element of the domain, we may assign any of $\displaystyle m$ elements of the codomain. Likewise, to the second, third,..., $\displaystyle n$-th element we can also assign any of the $\displaystyle m$ elements from the codomain, as there are no restrictions.

So, there are $\displaystyle n$ elements in the domain, and to each one of them, via different functions, we may assign any of those $\displaystyle m$ elements from the target set. From this and the product principle, it follows that there are $\displaystyle \underbrace{m\cdot m \cdot \cdot \cdot m}_{\text{n times}} = m^n$ different functions from a $\displaystyle n$-element set to a $\displaystyle m$-element set.