Help in simplifying combinatorial sum $\frac{n!}{(n-k)!}-{1\over(n-k)!}{\sum _{m=1}^{k-1} (-1)^{m+1} (n-m)! S(k,k-m)}$

Question

I'm working on simplifying$$\frac{n!}{(n-k)!}-{1\over(n-k)!}{\sum _{m=1}^{k-1} (-1)^{m+1} (n-m)! S(k,k-m)}$$ where $S(n,k)$ refers to Stirling numbers of the second kind. I can show experimentally that this expression is equivalent to $$(n-k+1)^k,$$ and I'm stuck in showing this to be the case. I've tried to form an intuition about what the sum might be counting, and have also tried to write down and simplify the sum with the definition of the Stirling numbers, but neither approach has led to progress.

Any help or advice on how to simplify is appreciated. Thanks in advance.

Answer 1

Notice that your expression can be stated as $$\sum _{m=0}^k(-1)^m\frac{(n-m)!}{(n-k)!}S(k,k-m)=\sum _{m=0}^k(-1)^{k-m}\frac{(n-k+m)!}{(n-k)!}S(k,m).$$
Now recall that $a^{\underline{b}}=\frac{a!}{(a-b)!}=a(a-1)\cdots (a-b+1)$ and $a^{\overline{b}}=a(a+1)\cdots (a+b-1)$ hence $a^{\underline{b}}=(-1)^b(-a)^{\overline{b}}$ and $(a)^{\underline{b}}=(a-b+1)^{\overline{b}}$

Now, notice that $$x^k=\sum _{m=0}^kx^{\underline{m}}S(k,m),$$ this can be understood as splitting the functions into the cardinal of their images( count how many functions from $[n]$ to $[x]$ there are with image having exactly $m$ elements).

$$\sum _{m=0}^k(-1)^{k-m}\frac{(n-k+m)!}{(n-k)!}S(k,m)$$ $$=\sum _{m=0}^k(-1)^{k-m}(n-k+m)^{\underline{m}}S(k,m)$$ $$=\sum _{m=0}^k(-1)^{k-m}(n-k+1)^{\overline{m}}S(k,m)$$ $$=\sum _{m=0}^k(-1)^{k}(-n+k-1)^{\underline{m}}S(k,m)$$ $$=(-1)^k(-n+k-1)^k.$$

Answer 2

In seeking to show that

$$\frac{n!}{(n-k)!}-\frac{1}{(n-k)!} \sum_{m=1}^{k-1} (-1)^{m+1} (n-m)! {k\brace k-m} = (n-k+1)^k$$

we follow the observation by @Phicar and simplify the LHS as follows:

$$\frac{n!}{(n-k)!}+\frac{1}{(n-k)!} \sum_{m=1}^{k-1} (-1)^{m} (n-m)! {k\brace k-m} \\ = \frac{n!}{(n-k)!}+\frac{1}{(n-k)!} \sum_{m=1}^{k} (-1)^{m} (n-m)! {k\brace k-m} \\ = \frac{1}{(n-k)!} \sum_{m=0}^{k} (-1)^{m} (n-m)! {k\brace k-m}.$$

We have using standard EGFs

$$\frac{1}{(n-k)!} k! [z^k] \sum_{m=0}^{k} (-1)^{m} (n-m)! \frac{(\exp(z)-1)^{k-m}}{(k-m)!} \\ = k! [z^k] \sum_{m=0}^{k} (-1)^{m} {n-m\choose k-m} (\exp(z)-1)^{k-m} \\ = k! [z^k] \sum_{m=0}^{k} (-1)^{k-m} {n-k+m\choose m} (\exp(z)-1)^{m}.$$

Now since $\exp(z)-1 = z +\cdots$ the coefficient extractor enforces the range and we may write

$$k! [z^k] (-1)^{k} \sum_{m\ge 0} (-1)^{m} {n-k+m\choose m} (\exp(z)-1)^{m} \\ = k! [z^k] (-1)^{k} \frac{1}{(1+\exp(z)-1)^{n-k+1}} \\ = k! [z^k] (-1)^{k} \exp(-(n-k+1)z).$$

We have at last

$$\bbox[5px,border:2px solid #00A000]{ (n-k+1)^k.}$$