Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How many functions are possible from the set $A=\{0,1,2\}$ into the set $B =\{0,1,2,3,4,5,6,7\}$ such that $f(i) \le f(j)$ for $i \lt j$ and $i,j \in A$?

I am not sure which counting model would give the easiest approach to solve this problem.Any ideas ?

share|cite|improve this question
up vote 4 down vote accepted

Start at $0$ and count to 7 while calling out whenever you reach a value of $f$. You end up saying "move to the next element of $B$" $7$ times, and "let the next value of $f$ be the number we have reached so far" $3$ times. That's $10$ utterances in total, $3$ of which are different from the rest. The number of ways to place them is $\binom{10}{3}$.

share|cite|improve this answer
You’re assuming that the functions must be injective, but the problem statement implies that they needn’t be. – Brian M. Scott Nov 25 '11 at 17:12
I'm not. You're allowed to say "let the next value of $f$ be the number we have reached so far" several times in a row without advancing through $B$ between them. – Henning Makholm Nov 25 '11 at 17:14
Yes, it’s okay; I had a mental hiccup. For the record, I wasn’t worried about that part, but about the final result: for some reason I was thinking that there were ten choices instead of eight. – Brian M. Scott Nov 25 '11 at 18:00

Such a function is simply a nondecreasing sequence of length 3, and so the easiest way is to choose which elements will appear in the sequence (with repetitions - why?) and after such choice the sequence itself is uniquely determined.

share|cite|improve this answer
well I can perceive the model you are alluding "the drawing of r objects from n distinct objects, when order of drawing is not important and we allow repetition", but I am still not sure how this is holding here. – Quixotic Nov 24 '11 at 15:54
Say you drew the numbers 5,2,6 from B; then they must correspond to the sequence 2,5,6. And say you drew 7,7,7, then they correspond to the sequence 7,7,7 and so forth. There is exactly one sequence (i.e. function from A to B that satisfies the conditions) for every choice of 3 elements from B (without order, with repetitions). – Gadi A Nov 24 '11 at 16:01
My head is not clear now .. I will look at it again after few hours. – Quixotic Nov 24 '11 at 16:03

Your Answer


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.