La combinatoria de las fórmulas y las interpretaciones

Question

He encontrado que $$ \sum_{j=0}^{s}(n-s+j)!\binom{s}{j}(s-j)! =s! \sum_{j=0}^{s} \frac{(n-s+j)!}{j!} = \frac{(n+1)!}{n+1-s}$$ He probado esta fórmula con la inducción, pero me preguntaba si hay una (combinatoria?) la interpretación que puede explicarlo.

Por otra parte, yo quería simplificar de una manera similar a las siguientes:

$$ \sum_{j=0}^{s}(n-s+j)!\binom{s}{j}3^{s-j}(s-j)! = s! 3^s \sum_{j=0}^{s} \frac{(n-s+j)!}{j!3^j} = ?$$ es posible?

Answer 1

Aquí otra que no sea de la inducción y no combinatoria prueba.

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

---

Alternativamente

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

Answer 2

Estoy consiguiendo:

$$\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*}$$

pero no sé si eso cuenta como una combinatoria de la prueba :D

De todos modos, podemos fácilmente hacer que en un adicional de $3^{s-j}$ factor de:

$$\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*}$$

pero eso no simplificar bien como antes, desde que se $\int_{0}^{1}v^{n-s}e^{-uv}\,dv$ depende de la integral exponencial. A partir de la última identidad, con la ayuda de un CAS que tengo:

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

Al menos, el $\color{blue}{\text{non-trivial part}}$ es administrado por un rápido convergente la serie.

Answer 3

Yo uso la notación $x^{\underline k}=x(x-1)\ldots(x-k+1)$ por la caída de los factorial. Primera nota de que

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

Deje $A=\{0,1,\ldots,n\}$; a continuación, $s^{\underline j}(n-j)!$ es el número de permutaciones $a_0a_1\ldots a_n$ $A$ tal que $a_j=s$, e $a_i<s$$0\le i<j$. Suma más de $j$ conseguir $(1)$ se obtiene el número de permutaciones de $A$, en la que cada elemento anterior $s$ es menor que $s$.

Ahora vamos a $\pi=a_0a_1\ldots a_n$ ser una permutación arbitraria de $A$. Deje $j$ ser mínima tal que $a_j\ge s$, vamos a $a_k=s$, y deje $\pi'$ ser la permutación que resulta de intercambiar $a_j$$a_k$. A continuación, $\pi'$ es una de las permutaciones contado por $(1)$, y el mapa de $\pi\mapsto\pi'$ $(n+1-s)$a-$1$, por lo que

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

Del mismo modo, podemos reescribir

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

Si pensamos en el conjunto de $A$ por encima como un conjunto de $n+1$ numeradas bolas blancas, $(2)$ es el número de maneras de elegir una permutación del tipo de contado en $(1)$ y, a continuación, la pintura de cada una de las bolas anteriores balón $s$ independientemente con uno de los tres colores rojo, azul y verde. Por desgracia, yo no veo ninguna buena manera de contar los resultados en un ir para simplificar $(2)$.