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