0
$\begingroup$

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 ?

2 Answers 2

4

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

  • 0
    You’re assuming that the functions must be injective, but the problem statement implies that they needn’t be.2011-11-25
  • 0
    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.2011-11-25
  • 0
    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.2011-11-25
2

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.

  • 0
    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.2011-11-24
  • 0
    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).2011-11-24
  • 0
    My head is not clear now .. I will look at it again after few hours.2011-11-24