4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Maybe an inclusion-exclusion count of functions from a $k$-set to an $(n-k+1)$-set? $\endgroup$ – RobPratt Jul 10 at 20:29
7
$\begingroup$

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.$$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.