Timeline for Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 29, 2017 at 7:21 | comment | added | Filip Nikšić | On the other hand, if we forget about $f$'s being injective, this shows $\sum_{j\leq k} j! {n \brace j} {n \choose j} \leq n^k {n \brace k}$. I'm not sure at the moment what the thing on the left is. | |
| Apr 29, 2017 at 7:12 | comment | added | Filip Nikšić | It doesn't quite work. Note that when $f$'s are injections, your $g$'s are not just any functions from $[n]$ to $k$-element subsets of $[n]$, they are surjections. So this actually shows a weaker inequality $k! {n \brace k} {n \choose k} \leq n^k {n \brace k}$, which is just ${n \choose k} \leq n^k / k!$. | |
| Apr 29, 2017 at 1:14 | history | answered | Richard Stanley | CC BY-SA 3.0 |