$f:\{1,2,\ldots,100\}\rightarrow \{1,2,\ldots,200\} $. How many functions can be made?

Question

I need to find out how many strictly increasing monotonic functions
$$f:\{1,2,\ldots,100\}\rightarrow \{1,2,\ldots,200\} $$ exist. And I do believe, that the answer should be $\binom{200}{100}$, but I have no idea how to prove it. How can I creat such functions and calculate them all?

I know there were similar questions, but I need more explanations.

Since $|{1,2,...,100}|=100< 200=|{1,2,...,200}|$ we cannot create a surjective function $f$. Hence, we cannot create a bijective function $f$. — Dave, Sep 14 '17 at 12:06
If you can say why you think that answer is right you will be most of the way to the proof. — Ethan Bolker, Sep 14 '17 at 12:09
This is a good example of a homework-based question! Well done $\ddot\smile$ — gen-ℤ ready to perish, Sep 14 '17 at 13:00
Jonas Vitkauskas! What was that? Why deface the question? Are you trying to cover up an attempt to get your homework done here? — Jyrki Lahtonen, Sep 14 '17 at 16:13

score 3 · Answer 1 · answered Sep 14 '17 at 12:06

3

If $f:A \to B$ is a bijection ($A,B$ are finite sets), then the number of elements in $A$ = the number of elements in $B$.

In your question: $A$ has $100$ elements and $B$ has $200$ elements.

Conclusion ?

answered Sep 14 '17 at 12:06

Fred

77,394

For those wondering, this answer was written when OP specified that $f$ has to be a bijection. – JiK Sep 15 '17 at 07:29

score 1 · Accepted Answer · answered Sep 14 '17 at 18:39

1

The map $f\mapsto f\bigl([100]\bigr)$ maps the set of admissible functions $f:\>[100]\to[200]$ bijectively onto the set of all $100$-element subsets of $[200]$. The number of these subsets is indeed ${200\choose100}$.

answered Sep 14 '17 at 18:39

Christian Blatter

226,825

$f:\{1,2,\ldots,100\}\rightarrow \{1,2,\ldots,200\} $. How many functions can be made?

2 Answers2