Números de Euler de primera clase

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de junio de 2020; la verificación requiere 1 edición .

En combinatoria , el número de Euler del primer tipo de n a k , denotado o , es el número de permutaciones de orden n con k ascensores , es decir, tales permutaciones que hay exactamente k índices j para los cuales . $\left\langle {n \encima de k}\right\rangle$ $E(n,k)$ $\pi =(\pi _{1},\pi _{2},\puntos,\pi _{n})$ $\pi _{j}<\pi _{{j+1}}$

Los números de Euler del primer tipo también tienen una interpretación geométrica y probabilística : el número expresa: ${\frac {1}{n!)}\left\langle {n \atop k}\right\rangle$

el volumen de una parte de un hipercubo n - dimensional delimitado por hiperplanos y ; $x_{1}+x_{2}+\puntos +x_{n}=k$ $x_{1}+x_{2}+\puntos +x_{n}=k-1$
la probabilidad de que la suma de n variables independientes uniformemente distribuidas en el intervalo se encuentre entre k -1 y k . $[0,1]$

Ejemplo

Las permutaciones de cuarto orden que tienen exactamente dos ascensores deben satisfacer una de tres desigualdades: , o . Hay exactamente 11 permutaciones de este tipo: $\Pi$ $\pi _{1}<\pi _{2}>\pi _{3}<\pi _{4}$ $\pi _{1}<\pi _{2}<\pi _{3}>\pi _{4}$ $\pi _{1}>\pi _{2}<\pi _{3}<\pi _{4}$

1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.

Por lo tanto $\left\langle {4 \encima de 2}\right\rangle =11$

Propiedades

Para un número natural dado, solo hay una permutación sin ascensores, es decir, . También hay una sola permutación que tiene n -1 ascensores, es decir, . De este modo, $norte$ $(n,n-1,n-2,\puntos,1)$ $(1,2,3,\puntos,n-1,n)$

\left\langle {n \encima de 0}\right\rangle =\left\langle {n \encima de n-1}\right\rangle =1

para todo natural .

norte

La imagen especular de una permutación con m ascensores es una permutación con n - m -1 ascensores. De este modo,

\left\langle {n \encima de m}\right\rangle =\left\langle {n \encima de nm-1}\right\rangle .

Triángulo de los números de Euler de primera especie

El significado de los números de Euler para valores pequeños de n y k se dan en la siguiente tabla (secuencia A008292 en OEIS ): $\left\langle {n \encima de k}\right\rangle$

n \ k	0	una	2	3	cuatro	5	6	7	ocho	9
0	una
una	una	0
2	una	una	0
3	una	cuatro	una	0
cuatro	una	once	once	una	0
5	una	26	66	26	una	0
6	una	57	302	302	57	una	0
7	una	120	1191	2416	1191	120	una	0
ocho	una	247	4293	15619	15619	4293	247	una	0
9	una	502	14608	88234	156190	88234	14608	502	una	0

Es fácil entender que los valores en la diagonal principal de la matriz vienen dados por la fórmula: $\left\langle {n \encima de n}\right\rangle =[n=0].$

El triángulo de Euler, como el triángulo de Pascal , es simétrico por la izquierda y la derecha. Pero en este caso, la ley de simetría es algo diferente:

\left\langle {n \encima de k}\right\rangle =\left\langle {n \encima de n-1-k}\right\rangle

para n > 0.

Es decir, una permutación tiene n -1- k crece si y sólo si su "reflexión" tiene k crece.

Fórmula recurrente

Cada permutación del conjunto da como resultado permutaciones de si insertamos un nuevo elemento n en todas las formas posibles. Insertando en la -ésima posición, obtenemos la permutación . El número de aumentos en es igual al número de aumentos en si o si ; y es mayor que el número de ascensores en si o si . Por lo tanto, en total tiene formas de construir permutaciones a partir de , que tienen ascensores, además de formas de construir permutaciones a partir de , que tienen ascensores. Entonces la fórmula recurrente deseada para números enteros tiene la forma: $\rho =\rho _{1}\puntos \rho _{{n-1}}$ $\{1,2,3,n-1\}$ $norte$ $\{1,2,3,n\}$ $norte$ $j$ $\pi =\rho _{1}\puntos \rho_{{j-1}}n\rho_{j}\puntos \rho_{{n-1}}$ $\Pi$ $\rho$ $j=1$ $\pi _{{j-1}}<\pi _{j}$ $\rho$ $j=n$ $\rho _{{j-1}}>\rho _{j}$ $\Pi$ $(k+1)\left\langle {n-1 \encima de k}\right\rangle$ $\rho$ $k$ $((n-2)-(k-1)+1)\left\langle {n-1 \encima de k-1}\right\rangle$ $\rho$ $k-1$ $n>0$

\left\langle {n \atop k}\right\rangle =(k+1)\left\langle {n-1 \atop k}\right\rangle +(nk)\left\langle {n-1 \atop k-1}\derecho\rango.

Supongamos también que

\left\langle {0 \encima de k}\right\rangle =[k=0]

(para números enteros ),

k

y en : $k<0$

\left\langle {n \atop k}\right\rangle =0.

Fórmulas explícitas

Fórmula explícita para los números de Euler de primera especie:

\left\langle {n \atop m}\right\rangle =\sum _{{k=0}}^{{m}}{n+1 \elegir k}(m+1-k)^{n} (-1)^{k}

permite obtener expresiones relativamente simples para valores pequeños de m :

\left\langle {n \encima de 0}\right\rangle =1;

\left\langle {n \atop 1}\right\rangle =2^{n}-n-1;

\left\langle {n \atop 2}\right\rangle =3^{n}-(n+1)2^{n}+{n+1 \elegir 2}.

Fórmulas de suma

De la definición combinatoria, es obvio que la suma de los números de Euler de primera especie ubicados en la n-ésima fila es igual , ya que es igual al número de todas las permutaciones del orden : $¡norte!$ $norte$

\sum _{{m=0}}^{n}\left\langle {n \atop m}\right\rangle =n!

Las sumas alternas de signo de los números de Euler del primer tipo para un valor fijo de n están relacionadas con los números de Bernoulli : $B_{{n+1}}$

\sum _{{m=0}}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle ={\frac {2^{{n+1}} (2^{{n+1}}-1)B_{{n+1}}}{n+1}},

\sum _{{m=0}}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n \elegir m}^{{-1}}= (n+1)B_{n},

\sum _{{m=0}}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n-1 \elegir m}^{{-1} }=0.

Las siguientes identidades también son válidas, conectando números de Euler del primer tipo con números de Stirling del segundo tipo :

\sum _{{k=nm}}^{n}\left\langle {n \atop k}\right\rangle {k \choose nm}=m!\left\{{n \atop m}\right\ }

\sum _{{k=0}}^{n}2^{k}\left\langle {n \atop k}\right\rangle =\sum _{{k=1}}^{{\infty} }{\frac {k^{n}}{2^{k}}}=\sum_{{k=1}}^{{n}}k!\left\{{n \sobre k}\right \}

\sum _{{k=0}}^{n}3^{k}\left\langle {n \atop k}\right\rangle =2^{{n+1}}\sum _{{k= 1}}^{{\infty}}{\frac {k^{n}}{3^{k}}}

Función generadora

La función generadora de números de Euler de primera clase tiene la forma:

{\frac {1-w}{e^{{{(w-1)z}}-w}}=\sum_{{m,n\geq 0}}\left\langle {n \atop m} \ derecha\rangle w^{m}{\frac {z^{n}}{n!)}}

Los números de Euler de primera especie también están relacionados con la función generadora de la sucesión de -ésimas potencias ( el polilogaritmo de un entero de orden negativo): $norte$

\sum_{{k=1}}^{{\infty}}k^{n}x^{k}={\frac {\sum_{{m=0}}^{{n-1}} \left\langle {n \atop m}\right\rangle x^{{m+1}}}{(1-x)^{{n+1}}}}.

Además, la transformada Z de

\izquierda\{n^{k}\derecha\}_{{k=1}}^{N}

es el generador de las primeras N filas de los números de Euler del triángulo cuando el denominador del enésimo elemento de la transformación se cancela multiplicando por : $norte$ $(z-1)^{{j+1}}$

Z\izquierda[\{n^{k}\}_{{k=1}}^{3}=\izquierda\{{\frac {z}{(z-1)^{2}}},{ \frac {z+z^{2}}{(z-1)^{3}}},{\frac {z+4z^{2}+z^{3}}{(z-1)^{ 4}}}\derecho\}\derecho]

La identidad de Vorpitsky

La identidad de Vorpitsky expresa una función de potencia como la suma de los productos de los números de Euler de primera especie y los coeficientes binomiales generalizados :

x^{n}=\sum_{{m=0}}^{{n-1}}\left\langle {n \atop m}\right\rangle {x+m \choose n}.

En particular:

x^{2}={x \elegir 2}+{x+1 \elegir 2}

x^{3}={x \elige 3}+4{x+1 \elige 3}+{x+2 \elige 3}

x^{4}={x \elegir 4}+11{x+1 \elegir 4}+11{x+2 \elegir 4}+{x+3 \elegir 4}

y así sucesivamente Estas identidades se prueban fácilmente por inducción .

La identidad de Vorpitsky da otra forma de calcular la suma de los primeros cuadrados: $norte$

\sum _{{k=1}}^{n}k^{2}=\sum _{{k=1}}^{n}\left\langle {2 \atop 0}\right\rangle {k \elegir 2}+\left\langle {2 \atop 1}\right\rangle {k+1 \elegir 2}=\sum _{{k=1}}^{n}{k \elegir 2}+{ k+1 \elegir 2}=

=\left({1 \elegir 2}+{2 \elegir 2}+\puntos +{n \elegir 2}\right)+\left({2 \elegir 2}+{3 \elegir 2}+\puntos +{n+1 \elegir 2}\derecha)=

={n+1 \elegir 3}+{n+2 \elegir 3}={\frac {n(n+1)(2n+1)}{6}}.

Literatura

Donald Knuth , Ronald Graham , Oren Patashnik . Números de Euler // Matemáticas concretas. Fundamentos de Informática = Matemáticas Concretas. Una Fundación para la Informática. — M .: Mir ; Binomio. Laboratorio de conocimiento , 2006. - Pág. 703. - ISBN 5-94774-560-7 .
D. Knut. Algoritmos básicos // El arte de la programación . - M. : Williams, 2006. - T. 1.
Weisstein, Eric W. Eulerian Number (inglés) en el sitio web Wolfram MathWorld .
Weisstein, Eric W. Worpitzky's Identity (inglés) en el sitio web de Wolfram MathWorld .
números eulerianos . Páginas de Matemáticas.