感谢@Michael Foukarakis指出了丢失的K.

Thanks @Michael Foukarakis for pointing the missing K.

Base case: T(n, 0) = 1
Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
                   = n * T(n-1, k-1) + 1

如下扩展

T(n, k) = n * T(n-1, k-1) + 1
        = n * (n-1) * T(n-2, k-2) + 1 + 1
        = n * (n-1) * T(n-2, k-2) + 2
        = n * (n-1) * (n-2) * T(n-3, k-3) + 3

        ...

         = n * (n-1) * (n-2) * ..(n-k) T(n-k, k-k) + k
         = n * (n-1) * (n-2) * ..(n-k) (1) + k
         = O(n^k)  (As it is a k th order polynomial)

总体而言，我们可以说 O(n ^k )运行时.

Overall we can say O(n^k) runtime.