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.

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.

share|improve this question
1  
$\text{Im}(f)$ is the image of $f$. This is the collection of all numbers $y$ in $\{1,2, \dots\}$ such that $y=f(x)$ for some $x\in \{1,2,\dots, n\}$. It is the set of all $f(x)$, where $x$ ranges over $\{1,2,\dots,n\}$. –  André Nicolas Oct 2 '11 at 6:27
    
Welcome to MathSE. I see that this is your first question. So I wanted to let you know a few things about MathSE. Posting questions in the imperative (i.e. Compute all such, Prove that...), is considered rude by some of the members, so it would be nice of you to change that wording; perhaps by adding what are your thoughts or what you have tried in trying to answer the problem. If this is homework, please add the [homework] tag; don't worry, it won't stop people form answering. These sort of pleasantries usually result in more and better answers. Thank you. –  Arturo Magidin Oct 2 '11 at 6:27
    
What is meant by a bisection in this context? –  Brian M. Scott Oct 2 '11 at 6:34
1  
(a) For any $i$, $f(i)$ can take on $m$ possible values. So there are $m^n$ possible functions. You are expected to assume that "random" means all of these are equally likely. How many injective functions are there? We want to count the functions $f$ such that if $i \ne j$ then $f(i)\ne f(j)$. There are $m$ possible values of $f(1)$. If $f(2)\ne f(1)$, there are $m-1$ choices for $f(2)$, for a total so far of $m(m-1)$. Continue. In total there are $m(m-1)(m-2)\cdots(m-n+1)$ injective functions. Now I imagine you can find the required probability. Minor comment: it is bijection, not bisection. –  André Nicolas Oct 2 '11 at 6:45
    
@BrianM.Scott I made a typo, that is supposed to be "bijection." I corrected the original question. –  jamesio Oct 2 '11 at 6:48
show 5 more comments

2 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
Thanks for the help. I can do part a now. Could you please elaborate a little bit more on part b. I still cannot figure that part out. –  jamesio Oct 2 '11 at 23:30
    
@jamesio: There are better ways to approach part b than what I proposed. See Brian Scott's answer and the links it gives. –  Arturo Magidin Oct 3 '11 at 2:41
add comment

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.

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.