Combinatorial formulas and interpretations

Here's another non-induction and non-combinatorial proof.

$$\begin{align} \sum_{j=0}^{s}(n-s+j)!\binom{s}{j}(s-j)! &=s! \sum_{j=0}^{s} \frac{(n-s+j)!}{j!} \cdot \color{lightgrey}{\frac{(n-s)!}{(n-s)!}}\\ &=s!(n-s)!\sum_{j=0}^s\binom {n-s+j}{n-s}\\ &=s!(n-s)!\binom {n+1}{n-s+1} &&\tiny\text{using }\sum_{r=a}^b\binom {m+r}{m+a}=\binom {m+b+1}{m+a+1}\\ &=s! (n-s)!\frac {(n+1)!}{(n-s+1)!s!}\\ &=(n-s)!\frac{(n+1)!}{(n-s+1)!}\\ &=\frac{(n+1)!}{n-s+1}\qquad\blacksquare \end{align}$$

---

Alternatively

$$\begin{align} \sum_{j=0}^{s}(n-s+j)!\binom{s}{j}(s-j)! &= n!\sum_{j=0}^s\frac{\binom sj}{\frac{n!}{(n-s+j)!(s-j)!}}\\ &=n!\sum_{j=0}^s\frac{\binom s{s-j}}{\binom n{s-j}}\\ &=\frac{n!}{\binom ns}\sum_{j=0}^s\frac{\binom ns\binom s{s-j}}{\binom n{s-j}}\\ &=\frac{n!}{\frac{n!}{s!(n-s)!}}\sum_{j=0}^s\frac{\binom n{s-j}\binom {n-s+j}{j}}{\binom n{s-j}}\\ &=s!(n-s)!\sum_{j=0}^s\binom {n-s+j}{n-s}\\ &=s!(n-s)!\binom{n+1}{n-s+1}\\ &=s!(n-s)! \frac{(n+1)!}{(n-s+1)!s!}\\ &=\frac{(n+1)!}{n-s+1}\qquad\blacksquare \end{align}$$

I am getting:

$$\begin{eqnarray*}\sum_{j=0}^{s}\binom{s}{j}(n-s+j)!(s-j)!&=&\iint_{(0,+\infty)^2}\sum_{j=0}^{s}\binom{s}{j}x^{s-j} y^{n-s+j} e^{-(x+y)}\,dx\,dy\\&=&\iint_{(0,+\infty)^2} x^s y^n e^{-(x+y)}\left(\frac{1}{x}+\frac{1}{y}\right)^s\,dx\,dy\\&=&\iint_{(0,+\infty)^2} y^{n-s} e^{-(x+y)}(x+y)^s\,dx\,dy\\&=&\int_{0}^{+\infty}\int_{0}^{u}y^{n-s} e^{-u} u^s\,dy\,du\\&=&\int_{0}^{+\infty}\int_{0}^{1} v^{n-s} e^{-u} u^{n+1}\,dv\,du\\&=&\color{red}{\frac{(n+1)!}{n-s+1}}\end{eqnarray*}$$

but I do not know if that counts as a combinatorial proof :D

Anyway, we may easily throw in an additional $3^{s-j}$ factor:

$$\begin{eqnarray*}\sum_{j=0}^{s}\binom{s}{j}3^{s-j}(n-s+j)!(s-j)!&=&\iint_{(0,+\infty)^2}\sum_{j=0}^{s}\binom{s}{j}(3x)^{s-j} y^{n-s+j} e^{-(x+y)}\,dx\,dy\\&=&\iint_{(0,+\infty)^2} y^{n-s} e^{-(x+y)}\left(3x+y\right)^s\,dx\,dy\\&=&\frac{1}{3}\int_{0}^{+\infty}\int_{0}^{1}u^{n+1} v^{n-s}\exp\left(-\frac{u}{3}-uv\right)\,dv\,du\end{eqnarray*}$$

but that does not simplify nicely as before, since $\int_{0}^{1}v^{n-s}e^{-uv}\,dv$ depends on a exponential integral. From the last identity, with the help of a CAS I got:

$$ \sum_{j=0}^{s}\binom{s}{j}3^{s-j}(n-s+j)!(s-j)!\\ = \color{red}{3^{s+1}n!(s-n)!} -\frac{(n+1)!}{s+1}\color{blue}{\,\phantom{}_2 F_1\left(n+2,s+1;s+2;-\frac{1}{3}\right)}. $$

At least, the $\color{blue}{\text{non-trivial part}}$ is given by a fast-convergent series.

I use the notation $x^{\underline k}=x(x-1)\ldots(x-k+1)$ for the falling factorial. First note that

$$\sum_{j=0}^s(n-s+j)!\binom{s}j(s-j)!=\sum_{j=0}^s(n-s+j)!s^{\underline{s-j}}=\sum_{j=0}^ss^{\underline j}(n-j)!\;.\tag{1}$$

Let $A=\{0,1,\ldots,n\}$; then $s^{\underline j}(n-j)!$ is the number of permutations $a_0a_1\ldots a_n$ of $A$ such that $a_j=s$, and $a_i<s$ for $0\le i<j$. Summing over $j$ to get $(1)$ yields the number of permutations of $A$ in which every element preceding $s$ is smaller than $s$.

Now let $\pi=a_0a_1\ldots a_n$ be an arbitrary permutation of $A$. Let $j$ be minimal such that $a_j\ge s$, let $a_k=s$, and let $\pi'$ be the permutation that results from interchanging $a_j$ and $a_k$. Then $\pi'$ is one of the permutations counted by $(1)$, and the map $\pi\mapsto\pi'$ is $(n+1-s)$-to-$1$, so

$$\sum_{j=0}^s(n-s+j)!\binom{s}j(s-j)!=\sum_{j=0}^ss^{\underline j}(n-j)!=\frac{(n+1)!}{n+1-s}\;.$$

Similarly, we can rewrite

$$\sum_{j=0}^{s}(n-s+j)!\binom{s}{j}3^{s-j}(s-j)! = \sum_{j=0}^s3^js^{\underline j}(n-j)!\;.\tag{2}$$

If we think of the set $A$ above as a set of $n+1$ numbered white balls, $(2)$ is the number of ways of choosing a permutation of the type counted in $(1)$ and then painting each of the balls preceding ball $s$ independently with one of the three colors red, blue, and green. Unfortunately, I don’t see any nice way to count the outcomes in one go to simplify $(2)$.