Factorial ascendente y número de Stirling de primera clase

Question

Factorial ascendente y número de Stirling de primera clase

Matemáticas
combinatoria
números de stirling
Matemáticas discretas

jaynot

¿Es cierto que

(X + 1)^{\bar{norte}} = \sum_{k \geq 0} \sum_{i = 0}^{norte} (\binom{i}{k}) s_{norte, i} X^{k} ?

$(x+1)^{\bar{n}}= \sum_{k \ge 0} \sum _{i=0}^{n} {i \choose k}s_{n,i}\,\,x^k \,\,\,\,?$ dónde

s_{n, i}

$s_{n,i}$ es el número de Stirling de primera clase y el

\bar{n}

$\bar{n}$ denota factorial ascendente. En caso afirmativo, ¿alguien podría mostrarme?

he podido probar que

(X + 1)^{\bar{norte}} = \sum_{k \geq 0} s_{norte + 1, k + 1} X^{k}

$(x+1)^{\bar{n}}= \sum_{k \ge 0} s_{n+1,k+1}\,\,x^k \,\,\,\,$

Mi objetivo es tratar de conseguir eso.

s_{norte + 1, k + 1} = \sum_{i = 0}^{norte} (\binom{i}{k}) s_{norte, i}

$s_{n+1,k+1} = \sum _{i=0}^{n} {i \choose k}s_{n,i}$ equiparando (comparando) ambas identidades

pedro taylor

Obviamente, puede cambiar el límite inferior de

i

$i$ a

k

$k$ , porque cuando

i < k

$i < k$ el coeficiente binomial es cero. La página de Wikipedia sobre los números de Stirling del primer tipo incluye: La identidad

\sum_{pag = k}^{norte} [\binom{norte}{pag}] (\binom{pag}{k}) = [\binom{norte + 1}{k + 1}]

$\sum _{p=k}^{n}{\left[{n \atop p}\right]{\binom {p}{k}}}=\left[{n+1 \atop k+1}\right]$ puede probarse mediante las técnicas de la página Números de Stirling y funciones generadoras exponenciales .

Respuestas (2)

Factorial ascendente y número de Stirling de primera clase

Obviamente, puede cambiar el límite inferior de $i$ a $k$ , porque cuando $i < k$ el coeficiente binomial es cero. La página de Wikipedia sobre los números de Stirling del primer tipo incluye: La identidad $\sum_{pag = k}^{norte} [\binom{norte}{pag}] (\binom{pag}{k}) = [\binom{norte + 1}{k + 1}]$ $\sum _{p=k}^{n}{\left[{n \atop p}\right]{\binom {p}{k}}}=\left[{n+1 \atop k+1}\right]$ puede probarse mediante las técnicas de la página Números de Stirling y funciones generadoras exponenciales .

Mike Earnest · Answer 1

¿Conoces la identidad

\begin{matrix} (*) & X^{\bar{norte}} = \sum_{i = 0}^{norte} s_{norte, i} X^{i} ? \end{matrix}

$x^{\overline n} = \sum_{i=0}^n s_{n,i}x^i?\tag{$*$}$ El resultado deseado sigue bastante rápido sustituyendo

x + 1

$x+1$ para

x

$x$ en

(*)

$(*)$ :

(X + 1)^{\bar{norte}} = \sum_{i = 0}^{norte} s_{norte, i} (X + 1)^{i} = \sum_{i = 0}^{norte} s_{norte, i} \sum_{k \geq 0} (\binom{i}{k}) X^{k} .

$(x+1)^{\overline n}=\sum_{i=0}^n s_{n,i}(x+1)^i = \sum_{i=0}^ns_{n,i}\sum_{k\ge 0}\binom{i}kx^k.$ Identidad

(*)

$(*)$ puede demostrarse por inducción sobre

n

$n$ usando la relación

s_{n + 1, k} = s_{n, k - 1} + n s_{n, k}

$s_{n+1,k}=s_{n,k-1}+ns_{n,k}$ , combinado con

x^{\bar{n + 1}} = x \cdot x^{\bar{n}} + n x^{\bar{n}}

$x^{\overline{n+1}}=x\cdot x^{\overline n}+nx^{\overline n}$ . También hay una demostración combinatoria .

Ay dios mío. Soy tan estúpido. Usé esa identidad para probar la primera parte que afirmé. Sí, veo lo que quieres decir. Yo no estaba pensando de esa manera en absoluto. Gracias.
@Jaynot Bueno, eso es lo que pasa con la combinatoria, a menudo no hay una manera obviamente correcta de atacar un problema, por lo que el hecho de que exista una prueba breve no significa que deba castigarse por no poder encontrarla.

Marko Riedel · Answer 2

por la identidad

\sum_{pag = k}^{norte} [\binom{norte}{pag}] (\binom{pag}{k}) = [\binom{norte + 1}{k + 1}]

$\sum_{p=k}^n {n\brack p} {p\choose k} = {n+1\brack k+1}$

obtenemos en la LHS usando series de potencias formales

norte! [z^{norte}] \sum_{pag = k}^{norte} (\binom{pag}{k}) \frac{1}{pag!} {(registro \frac{1}{1 - z})}^{pag}

$n! [z^n] \sum_{p=k}^n {p\choose k} \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^p$

Tenemos $\log\frac{1}{1-z} = z + \cdots$ por lo que no hay contribución al extractor de coeficientes cuando $p\gt n$ y podemos continuar con

norte! [z^{norte}] \sum_{pag \geq k} (\binom{pag}{k}) \frac{1}{pag!} {(registro \frac{1}{1 - z})}^{pag} = norte! [z^{norte}] \sum_{pag \geq 0} (\binom{pag + k}{k}) \frac{1}{(pag + k)!} {(registro \frac{1}{1 - z})}^{pag + k} = norte! [z^{norte}] {(registro \frac{1}{1 - z})}^{k} \sum_{pag \geq 0} (\binom{pag + k}{k}) \frac{1}{(pag + k)!} {(registro \frac{1}{1 - z})}^{pag} = norte! [z^{norte}] \frac{1}{k!} {(registro \frac{1}{1 - z})}^{k} \sum_{pag \geq 0} \frac{1}{pag!} {(registro \frac{1}{1 - z})}^{pag} = norte! [z^{norte}] \frac{1}{k!} {(registro \frac{1}{1 - z})}^{k} Exp registro \frac{1}{1 - z} = norte! [z^{norte}] \frac{1}{k!} {(registro \frac{1}{1 - z})}^{k} \frac{1}{1 - z} .

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

Para el RHS partimos de

\sum_{norte \geq 0} [\binom{norte}{k + 1}] \frac{z^{norte}}{norte!} = \frac{1}{(k + 1)!} {(registro \frac{1}{1 - z})}^{k + 1}

$\sum_{n\ge 0} {n\brack k+1} \frac{z^n}{n!} = \frac{1}{(k+1)!} \left(\log\frac{1}{1-z}\right)^{k+1}$

de modo que por diferenciación

\sum_{norte \geq 0} [\binom{norte + 1}{k + 1}] \frac{z^{norte}}{norte!} = \frac{1}{k!} {(registro \frac{1}{1 - z})}^{k} \frac{1}{1 - z} .

$\sum_{n\ge 0} {n+1\brack k+1} \frac{z^n}{n!} = \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k} \frac{1}{1-z}.$

Vemos que LHS y RHS tienen el mismo EGF y esto prueba la afirmación. Aquí hemos hecho uso repetido de la clase combinatoria etiquetada

S mi T (tu \times C Y C (Z)) .

$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\times \textsc{CYC}(\mathcal{Z})).$

Esta es la descomposición de permutaciones en conjuntos de ciclos disjuntos.

Factorial ascendente y número de Stirling de primera clase

jaynot

pedro taylor

Respuestas (2)

Mike Earnest

jaynot

Mike Earnest

Marko Riedel

jaynot

Interpretación combinatoria de la fórmula explícita para los números de Stirling de segunda clase

¿Cuál es la prueba combinatoria para la fórmula de S(n,k)S(n,k)S(n,k) - Números de Stirling de segunda especie?

Números de Stirling de segundo tipo en Multiset

Sobre el número de Stirling de segunda clase

Un problema de Combinatoria de Brualdi sobre el cálculo de los Números de Stirling

Incapaz de probar una relación que los Números de Stirling de 2º tipo deben satisfacer

Números de Stirling de segunda clase

¿Cómo relacionar el número de todas las aplicaciones X→YX→YX\to Y con los números de Stirling del segundo tipo?

¿Cuál es la relación entre los números de Stirling y las funciones generadoras?

Prueba combinatoria de recurrencia del número de Stirling de segunda clase