0
$\begingroup$

Consider $f:\{1,\dots,n\} \to \{1,\dots,m\}$ with $m > n$. Let $\operatorname{Im}(f) = \{f(x)|x \in \{1,\dots,n\}\}$.

a.) What is the probability that a random function will be a bijection when viewed as f':\{1,\dots,n\} \to \operatorname{Im}(f)?

b.) How many different function f are there for which $\sum_{i=1}^n f(i)=k?$ Not sure where to start and have no idea what $\operatorname{Im}(f)$ means. Please help me get started on this.

  • 0
    @jamesio: You can follow the suggested link and see whether you can adapt the idea. With some work, you can obtain an **expression** for the desired number. It will not simplify nicely.2011-10-03

2 Answers 2

3

First, you need to count the number of functions. That's easy: for each element of $\{1,\ldots,n\}$, there are $m$ possible images. So the number of functions is put answer here.

A function $f$ is a bijection onto its image if and only if it is one-to-one. So you should count the number of one-to-one functions. Not too bad either: $f(1)$ can be anything. Then $f(2)$ can be anything except $f(1)$; then $f(3)$ can be anything except $f(1)$ or $f(2)$. And so on. So the number of one-to-one functions is fill in the blank.

Question (b) seems a bit more delicate. A naive approach would be to figure out in how many ways you can write $k$ as a sum of $n$ positive integers, none of them greater than $m$. Then for each of them you need to find how many functions you have. That seems a bit harder, since the answer will depend on the number of times that a particular integer gets repeated. For instance, if $m=5$, $n=3$, and $k=6$, you have six different one-to-one functions (images $(1,2,3)$, $(2,3,1)$, $(3,1,2)$, $(1,3,2)$, $(3,2,1)$, $(2,1,3)$), three with a single repeat (images $(1,1,4)$, $(1,4,1)$, $(4,1,1)$), an one with three repeats (namely, $(2,2,2)$). They correspond to the fact that the number of ways to write $6$ as a sum of three positive integers are $1+1+4$, $1+2+3$, and $2+2+2$.

  • 0
    @jamesio: There are better ways to approach part b than what I proposed. See Brian Scott's answer and the links it gives.2011-10-03
3

The answer to (b) is the same as the answer to the following question:

How many solutions does the equation $x_1+x_2+\dots+x_n=k$ have if each $x_i$ is required to be an integer between $1$ and $m$ inclusive?

Think of $x_i$ as $f(i)$.

Versions of this question have been discussed here before: a couple of very recent discussions are here and here.