39 votos

Combinatoria interpretación de Binomio de Inversión

Es sabido que si $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ todos los $0 \le n \le m$,$g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$$0 \le n \le m$. Este tipo de inversión se denomina binomio inversión, por razones obvias.

Muchas agradables y elegantes pruebas existen (mi favorito de los usos exponencial funciones de generación de $f_n$$g_n$), y también muchas aplicaciones (tales como la demostración de que si el polinomio $f$ grado $n$ asume valores enteros en $0,1,\cdots,n$, $f(i) \in \mathbb{Z}$ para todos los enteros $i$).

Lo que me interesa es la siguiente:

  1. Un buen inclusión-exclusión de prueba similar a la interpretación de Möbius de la inversión como de la inclusión-exclusión.
  2. Si $f_0 = g_0 = 0$$i | f_i$$i>1$, obtenemos, por el Binomio Inversión, que $i | g_i$ (razón: $i\binom{n}{i} = n\binom{n-1}{i-1}$). Hay un buen combinatoria interpretación de este fenómeno? Bonito aplicaciones?
  3. Hay más famoso de frío/inversiones (sé de Möbius de la inversión, el binomio de la inversión, y el discreto derivados de la inversión de las $a_i \to a_{i+1}-a_{i})$?

32voto

Martin OConnor Puntos 116

Estos tipos de relaciones inversas son equivalentes a ortogonal de las relaciones entre conjuntos de números.

Supongamos que se tienen dos triangular conjuntos de números $a_{n,k}$$b_{n,k}$, cada uno definido por $k = 0, 1, \ldots, n$, de tal manera que $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm}.$$ Then $a_{n,k}$ and $b_{n,k}$ are orthogonal, and they have the inverse property you are asking for in (3); i.e., if $f_n = \sum_{k=0}^n a_{n,k} g_k$ then $g_n = \sum_{k=0}^n b_{n,k} f_k$, y viceversa.

Prueba: $$\sum_{k=0}^n b_{n,k} f_k = \sum_{k=0}^n b_{n,k} \sum_{m=0}^k a_{k,m} g_m = \sum_{m=0}^n \left(\sum_{k=m}^n b_{n,k} a_{k,m}\right) g_m = g_n.$$

Por lo tanto binomio de inversión de la siguiente manera a partir de la "hermosa identidad" $$\sum_{k=m}^n (-1)^{k+m} \binom{n}{k} \binom{k}{m} = \delta_{nm}.$$

Desde el ortogonal relación y la relación inversa que son equivalentes, tal vez la prueba de esta identidad dada por Aryabhata o la prueba de Yuval Filmus puede ser considerado como una combinatoria de la prueba de la relación inversa que se describen por los coeficientes binomiales.


Otros ejemplos

El Lah números de $L(n,k)$ satisfacer $$\sum_{k=m}^n (-1)^{k+m} L(n,k) L(k,m) = \delta_{nm},$$ y así, como los coeficientes binomiales, son (y firmar) auto-ortogonal y tener la relación inversa $$f_n = \sum_{k=0}^n L(n,k) g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} L(n,k) f_k.$$

Los dos tipos de números de Stirling, $\left[ n \atop k \right]$$\left\{ n \atop k \right\}$, son ortogonales, la satisfacción de $$\sum_{k=m}^n (-1)^{k+m} \left[ n \atop k \right] \left\{ k \atop m \right\} = \delta_{nm}$$ y $$\sum_{k=m}^n (-1)^{k+m} \left\{ n \atop k \right\} \left[ k \atop m \right] = \delta_{nm}.$$ Por lo tanto satisfacen la relación inversa $$f_n = \sum_{k=0}^n \left[ n \atop k \right] g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} \left\{ n \atop k \right\} f_k.$$

John Riordan escribió un libro "Relaciones Inversas y la Combinatoria de las Identidades" (American Mathematical Monthly 71 (5), Mayo de 1964, pp 485--498) y dedicado a dos de los seis capítulos de su texto Combinatoria de las Identidades de estos tipos de relaciones inversas. Por ejemplo, se muestra cómo las relaciones inversas pueden ser derivadas de los polinomios de Chebyshev (ya que son ortogonales) y los polinomios de Legendre (ya que también son ortogonales). Ver el artículo o el libro muchos más ejemplos.


Comentarios adicionales y consecuencias

La prueba utilizando el ortogonal relación también puede ser aplicado con respecto a la parte superior del índice para obtener la inversa de relaciones basadas en la parte superior del índice en lugar de la inferior. Así, por ejemplo, también tenemos (siempre, claro está, que las sumas convergen) $$f_n = \sum_{k=n}^\infty \binom{k}{n} g_k \Leftrightarrow g_n = \sum_{k=n}^\infty (-1)^{k+n} \binom{k}{n} f_k,$$ así como el mismo tipo de cosa para el Lah números, los números de Stirling, y el resto de los ejemplos.

Además, estos ortogonal de relaciones significa que las matrices que consiste ortogonal números son inversos. Así, por ejemplo, si $A$ $B$ $n \times n$ matrices tales que el$A_{ij} = \binom{i}{j}$$B_{ij} = (-1)^{i+j} \binom{i}{j}$, entonces la relación ortogonal implica que $AB = I$. Esto, por supuesto, significa que $BA = I$, y así cada relación ortogonal va en ambos sentidos; es decir, $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm} \Leftrightarrow \sum_{k=m}^n a_{n,k} b_{k,m} = \delta_{nm}.$$ Para más información sobre matrices inversas que consta de combinatoria de números, véase mi respuesta a la pregunta "los números de Stirling y matrices inversas."

19voto

Matt Dawdy Puntos 5479

Esta identidad, de inversión de Möbius, y el "teorema fundamental del cálculo discreto" son todos los casos especiales de Möbius de la inversión en un poset.

  • En esta identidad la correspondiente poset es el poset de subconjuntos finitos de $\mathbb{N}$.
  • En el clásico de inversión de Möbius es el poset $\mathbb{N}$ por debajo de la división.
  • En el cálculo discreto es el poset $\mathbb{Z}_{\ge 0}$ bajo el orden habitual.

Esta hermosa teoría fue descrita por primera vez por Gian-Carlo Rota en los Fundamentos de la Teoría Combinatoria yo, y elaboradas en muchos otros papeles. Si te gusta exponencial de las funciones de generación, será el amor En los Fundamentos de la Teoría Combinatoria VI. Estos documentos fueron toda una revelación para mí hace un par de años y espero que disfruten de ellos.

Un moderno referencia es Stanley Combinatoria Enumerativa Vol. I, Capítulo 3 (por cierto, creo que Stanley era un estudiante de la Rota). Aquí es la adecuada especialización del resultado general.

La proposición: Vamos a $g : \mathcal{P}_{\text{fin}}(\mathbb{N}) \to R$ ser una función de la poset de subconjuntos finitos de $\mathbb{N}$ a un anillo conmutativo $R$. Vamos

$$f(T) = \sum_{S \subseteq T} g(S).$$

Entonces

$$g(T) = \sum_{S \subseteq T} (-1)^{|S| - |T|} f(S)$$

donde $|S|$ denota el tamaño de $S$. (El caso especial en que el estado es para cuando se $g$ sólo depende de $|S|$.)

Prueba. Esto es en realidad un poco más general de la forma de inclusión-exclusión. Basta con intercambiar el orden de la suma en

$$\sum_{S \subseteq T} (-1)^{|S| - |T|} \sum_{R \subseteq S} g(R) = \sum_{R \subseteq T} g(R) \sum_{R \subseteq S \subseteq T} (-1)^{|S| - |T|}$$

y observar que el coeficiente es igual a $(1 - 1)^{|R| - |T|}$, que es igual a $0$ si $R = T$, en cuyo caso es igual a $1$. Por supuesto que puedo murmurar a mi manera a través de la norma de inclusión-exclusión de la prueba así: iniciar con $f(T)$, que tiene demasiados términos, por lo que restar los términos de $f(T - \{ t \})$, pero hemos restado los otros términos demasiadas veces, así que volver a agregar los términos de $f(T - \{ t_1, t_2 \})$...


Una observación fundamental acerca de Möbius funciones en general es que son de multiplicación el producto de posets. El posets he nombrado anteriormente son todos los productos de las cadenas, así que uno puede rápidamente calcular su Möbius funciones simplemente mediante el cálculo de la función de Möbius de una cadena.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X