Question

 Let an denote the number of surjective (onto) functions f : {1, 2, . . . , n} −→

{1, 2, 3} such that f(1) < f(2). Give a Θ estimate for an.

Answer 1

number of surjective functions $f:[k]\to[n]$ :

$N=\displaystyle \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix}(-1)^i(n-i)^k$

in our case:

$N=\displaystyle \sum_{i=0}^n \begin{pmatrix} 3 \\ i \end{pmatrix}(-1)^i(3-i)^n=3^n-3\cdot2^n+3$

minimum number of function such that f(1) > f(2) is 0

maximum number of function such that f(1) > f(2) is 3:

$f(2)=1,f(2)=2,f(1)=3$

so, $\theta$ estimate for a_n :

$N-3\le a_n \le N$

$3^n-3\cdot2^n<a_n<3^n-3\cdot2^n+3$