The number of strictly increasing functions f from the set 1,2,3,4,5,6 to the set 1,2,,9 s…

Question

The number of strictly increasing functions $f$ from the set $\{1,2,3,4,5,6\}$ to the set $\{1,2,\ldots,9\}$ such that $f(i) 
e i$ for $1 \le i \le 6$, is equal to:

Accepted Answer

A strictly increasing function from a 6-element set to a 9-element set is determined entirely by choosing its image (a 6-element subset of $\{1,\ldots,9\}$), since the values must then be assigned in increasing order. There are $\binom{9}{6}=84$ such functions in total, and we must exclude those with $f(1)=1$ (since $f$ strictly increasing and $f(i)\ge f(1)+ (i-1) \ge i$ forces potential equalities down the line --- this is handled by casework on $f(1)$).

Considering the minimal cases where $f(i)=i$ can occur (analysis shows the constraint effectively reduces to conditions on $f(1)$):

- $f(1)=2$: remaining values chosen as $^7C_5$ possibilities $=21$
- $f(1)=3$: $^6C_5=6$
- $f(1)=4$: $^5C_5=1$

$21+6+1 = 28$

Solutions · 1