>>723
左側：
C[n, k] = Π[j=0, k-1] (n-j)/(k-j) > Π[j=0, k-1] (n/k) = (n/k)^k,

右側：　補題より
C[n, k] = n(n-1)…(n-k+1)/k! < (n^k)/k! < e^(k-1)･(n/k)^k,

〔補題〕
k≧2 のとき　(k^k)/k! < e^(k-1),

（略証）
(1 +1/j)^j = Σ[L=1, j] C[j, L](1/j)^L = Σ[L=1, j] (1-1/j)(1-2/j)…(1-(L-1)/j)/L!
はjについて単調増加。
∴　{(j+1)/j}^j = (1 + 1/j)^j < e,
j=1,…,k-1 を入れて掛けると
　(k^k)/k! < e^(k-1),

(別法)
マクローリン展開から
　e^x > x^{k-1} /(k-1)! + (x^k)/k! + x^{k+1} /(k+1)!
　　　= (x^k)/k! {(k/x) + 1 + x/(k+1)},
　e^k > (k^k)/k! {2 + k/(k+1)} > (k^k)/k! e,　　　(k≧3)
∴　e^{k-1} > (k^k)/k!,
k=2 は直接確かめる。 　　(終)