Gaussian binomial coefficient

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient ${\displaystyle {\tbinom {m}{r}}}$cuenta las r combinaciones elegidas de un conjunto de m elementos. Si se toman esos m elementos como las diferentes posiciones de caracteres en una palabra de longitud m , entonces cada r combinación corresponde a una palabra de longitud m usando un alfabeto de dos letras, digamos {0,1}, con r copias de la letra 1 (que indican las posiciones en la combinación elegida) y m − r letras 0 (para las posiciones restantes).

Así pues, por ejemplo, el${\displaystyle {4 \choose 2}=6}$Las palabras que usan 0 y 1 son${\displaystyle 0011,0101,0110,1001,1010,1100}$.

Para obtener el coeficiente binomial gaussiano${\displaystyle {\tbinom {m}{r}}_{\!q}}$, cada palabra está asociada con un factor q ^d , donde d es el número de inversiones de la palabra, donde, en este caso, una inversión es un par de posiciones donde la izquierda del par contiene la letra 1 y la posición derecha contiene la letra 0 .

Con el ejemplo anterior, hay una palabra con 0 inversiones,${\displaystyle 0011}$, una palabra con 1 inversión,${\displaystyle 0101}$, dos palabras con 2 inversiones,${\displaystyle 0110}$,${\displaystyle 1001}$, una palabra con 3 inversiones,${\displaystyle 1010}$y una palabra con 4 inversiones,${\displaystyle 1100}$. Este es también el número de desplazamientos a la izquierda de los 1 desde la posición inicial.

Estos corresponden a los coeficientes en${\displaystyle {4 \choose 2}_{\!q}=1+q+2q^{2}+q^{3}+q^{4}}$.

Otra forma de visualizar esto es asociar cada palabra con un camino a través de una cuadrícula rectangular de altura r y ancho m − r , que va desde la esquina inferior izquierda hasta la esquina superior derecha. El camino da un paso a la derecha por cada 0 y un paso hacia arriba por cada 1. Una inversión cambia la dirección de un paso (derecha+arriba se convierte en arriba+derecha y viceversa), por lo que el número de inversiones es igual al área bajo el camino.

Dejar${\displaystyle B(n,m,r)}$sea ​​el número de formas de lanzar ${\displaystyle r}$bolas indistinguibles en${\displaystyle m}$contenedores indistinguibles, donde cada contenedor puede contener hasta${\displaystyle n}$bolas. El coeficiente binomial gaussiano se puede utilizar para caracterizar${\displaystyle B(n,m,r)}$. En efecto,

${\displaystyle B(n,m,r)=[q^{r}]{n+m \choose m}_{\!q}.}$

dónde${\displaystyle [q^{r}]P}$denota el coeficiente de${\displaystyle q^{r}}$en polinomio${\displaystyle P}$(Véase también la sección de Aplicaciones más abajo).

Al igual que los coeficientes binomiales ordinarios, los coeficientes binomiales gaussianos son simétricos respecto al centro, es decir, invariantes bajo la reflexión.${\displaystyle r\mapsto mr}$:

${\displaystyle {m \choose r}_{\!q}={m \choose m-r}_{\!q}.}$

En particular,

${\displaystyle {m \choose 0}_{\!q}={m \choose m}_{\!q}=1\,,}$

${\displaystyle {m \choose 1}_{\!q}={m \choose m-1}_{\!q}={\frac {1-q^{m}}{1-q}}=1+q+\cdots +q^{m-1}\quad m\geq 1\,.}$

La evaluación de un coeficiente binomial gaussiano en q = 1 es

${\displaystyle \lim _{q\to 1}{\binom {m}{r}}_{\!q}={\binom {m}{r}}}$

es decir, la suma de los coeficientes da el valor binomial correspondiente.

El grado de${\displaystyle {\binom {m}{r}}_{\!q}}$es:${\displaystyle {\binom {m+1}{2}}-{\binom {r+1}{2}}-{\binom {(m{-}r)+1}{2}}=r(m-r)}$.

Los análogos de la identidad de Pascal para los coeficientes binomiales gaussianos son: ^{[ 2 ]}

${\displaystyle {m \choose r}_{\!q}=q^{r}{m-1 \choose r}_{\!q}+{m-1 \choose r-1}_{\!q}}$

y

${\displaystyle {m \choose r}_{\!q}={m-1 \choose r}_{\!q}+q^{m-r}{m-1 \choose r-1}_{\!q}.}$

Cuando${\displaystyle q=1}$, ambos dan la identidad binomial usual. Podemos ver que como${\displaystyle m\to \infty }$, ambas ecuaciones siguen siendo válidas.

El primer análogo de Pascal permite el cálculo recursivo (con respecto a m ) de los coeficientes binomiales gaussianos utilizando los valores iniciales.

${\displaystyle {m \choose m}_{\!q}={m \choose 0}_{\!q}=1}$

y también muestra que los coeficientes binomiales gaussianos son efectivamente polinomios (en q ).

El segundo análogo de Pascal se deriva del primero mediante la sustitución.${\displaystyle r\rightarrow m-r}$y la invariancia de los coeficientes binomiales gaussianos bajo la reflexión${\displaystyle r\rightarrow m-r}$.

Estas identidades tienen interpretaciones naturales en términos de álgebra lineal . Recordemos que${\displaystyle {\tbinom {m}{r}}_{q}}$cuenta subespacios r -dimensionales${\displaystyle V\subset \mathbb {F} _{q}^{m}}$y dejar${\displaystyle \pi$ Sea $\mathbb {F} _{q}^{m}\to \mathbb {F} _{q}^{m-1}}$ una proyección con espacio nulo unidimensional.${\displaystyle E_{1}}$. La primera identidad proviene de la biyección que toma${\displaystyle V\subset \mathbb {F} _{q}^{m}}$al subespacio${\displaystyle V'=\pi (V)\subset \mathbb {F} _{q}^{m-1}}$; En caso${\displaystyle E_{1}\not \subset V}$, el espacio${\displaystyle V'}$es r -dimensional, y también debemos hacer un seguimiento de la función lineal.${\displaystyle \phi :V'\to E_{1}}$cuyo gráfico es${\displaystyle V}$; pero en caso${\displaystyle E_{1}\subset V}$, el espacio${\displaystyle V'}$es ( r −1)-dimensional, y podemos reconstruir${\displaystyle V=\pi ^{-1}(V')}$sin ninguna información adicional. La segunda identidad tiene una interpretación similar, tomando${\displaystyle V}$a${\displaystyle V'=V\cap E_{n-1}}$para un espacio ( m −1)-dimensional${\displaystyle E_{m-1}}$, dividiéndose nuevamente en dos casos.

Ambos análogos pueden probarse observando primero que, a partir de la definición de${\displaystyle {\tbinom {m}{r}}_{q}}$, tenemos:

Como

${\displaystyle {\frac {1-q^{m}}{1-q^{m-r}}}={\frac {1-q^{r}+q^{r}-q^{m}}{1-q^{m-r}}}=q^{r}+{\frac {1-q^{r}}{1-q^{m-r}}}}$

La ecuación ( 1 ) se convierte en:

${\displaystyle {\binom {m}{r}}_{q}=q^{r}{\binom {m-1}{r}}_{q}+{\frac {1-q^{r}}{1-q^{m-r}}}{\binom {m-1}{r}}_{q}}$

y sustituyendo la ecuación ( 3 ) se obtiene el primer análogo.

Un proceso similar, utilizando

${\displaystyle {\frac {1-q^{m}}{1-q^{r}}}=q^{m-r}+{\frac {1-q^{m-r}}{1-q^{r}}}}$

En cambio, da el segundo análogo.

Existe un análogo del teorema del binomio para coeficientes q -binomiales, conocido como el teorema del binomio de Cauchy:

${\displaystyle \prod _{k=0}^{n-1}(1+q^{k}t)=\sum _{k=0}^{n}q^{k(k-1)/2}{n \choose k}_{\!q}t^{k}.}$

Al igual que el teorema del binomio habitual, esta fórmula tiene numerosas generalizaciones y extensiones; una de ellas, que corresponde al teorema generalizado del binomio de Newton para potencias negativas, es:

${\displaystyle \prod _{k=0}^{n-1}{\frac {1}{1-q^{k}t}}=\sum _{k=0}^{\infty }{n+k-1 \choose k}_{\!q}t^{k}.}$

En el límite${\displaystyle n\rightarrow \infty }$, estas fórmulas producen

${\displaystyle \prod _{k=0}^{\infty }(1+q^{k}t)=\sum _{k=0}^{\infty }{\frac {q^{k(k-1)/2}t^{k}}{[k]_{q}!\,(1-q)^{k}}}}$

y

${\displaystyle \prod _{k=0}^{\infty }{\frac {1}{1-q^{k}t}}=\sum _{k=0}^{\infty }{\frac {t^{k}}{[k]_{q}!\,(1-q)^{k}}}}$.

Configuración${\displaystyle t=q}$proporciona las funciones generadoras que cuentan particiones con partes distintas y arbitrarias, respectivamente.

Con los coeficientes binomiales ordinarios, tenemos:

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{\!2}={\binom {2n}{n}}}$

Con coeficientes q -binomiales, el análogo es:

${\displaystyle \sum _{k=0}^{n}q^{k^{2}}{\binom {n}{k}}_{\!q}^{\!2}={\binom {2n}{n}}_{\!q}}$

Gauss utilizó originalmente los coeficientes binomiales gaussianos en su determinación del signo de la suma cuadrática de Gauss . ^{[ 3 ]}

Los coeficientes binomiales gaussianos aparecen en el conteo de polinomios simétricos y en la teoría de particiones . El coeficiente de q ^r en

${\displaystyle {n+m \choose m}_{\!q}}$

es el número de particiones de r con m o menos partes, cada una menor o igual que n . De manera equivalente, también es el número de particiones de r con n o menos partes, cada una menor o igual que m .

Los coeficientes binomiales gaussianos también juegan un papel importante en la teoría enumerativa de espacios proyectivos definidos sobre un cuerpo finito. En particular, para cada cuerpo finito${\displaystyle \mathbb {F} _{q}}$con q elementos, el coeficiente binomial gaussiano

${\displaystyle {n \choose k}_{\!q}}$

cuenta el número de subespacios vectoriales k -dimensionales de un espacio vectorial n -dimensional sobre${\displaystyle \mathbb {F} _{q}}$(los puntos de una grassmanniana ). Cuando se expande como un polinomio en q , produce la conocida descomposición de la grassmanniana en celdas de Schubert. Por ejemplo, el coeficiente binomial gaussiano

${\displaystyle {n \choose 1}_{\!q}=1+q+q^{2}+\cdots +q^{n-1}}$

es el número de subespacios unidimensionales en ( F _q ) ⁿ , o equivalentemente el número de puntos en el espacio proyectivo asociado . Además, cuando q es 1 (respectivamente −1), el coeficiente binomial gaussiano produce la característica de Euler de la grassmanniana compleja (respectivamente real) correspondiente.

El número de subespacios afines k -dimensionales de F _q ⁿ es igual a

${\displaystyle q^{n-k}{n \choose k}_{\!q}}$.

Esto permite otra interpretación de la identidad.

${\displaystyle {m \choose r}_{\!q}={m-1 \choose r}_{\!q}+q^{m-r}{m-1 \choose r-1}_{\!q}}$

como contar los subespacios ( r − 1)-dimensionales del espacio proyectivo ( m − 1)-dimensional fijando un hiperplano , contando dichos subespacios contenidos en ese hiperplano y luego contando los subespacios no contenidos en el hiperplano; estos últimos subespacios están en correspondencia biyectiva con los subespacios afines ( r − 1)-dimensionales del espacio obtenido al tratar este hiperplano fijo como el hiperplano en el infinito.

Los coeficientes binomiales gaussianos juegan un papel importante en el fenómeno de cribado cíclico. Sea C un grupo cíclico de orden n con generador c . Sea X el conjunto de subconjuntos de k elementos del conjunto de n elementos {1, 2, ..., n }. El grupo C tiene una acción canónica sobre X dada al enviar c a la permutación cíclica (1, 2, ..., n ). El número de puntos fijos de c ^d en X es igual a

${\displaystyle {\binom {n}{k}}_{\!q}}$

donde q se toma como la d -ésima potencia de una raíz n - ésima primitiva de la unidad .

En las convenciones comunes en las aplicaciones a grupos cuánticos , se utiliza una definición ligeramente diferente; el coeficiente binomial cuántico allí es

${\displaystyle q^{k^{2}-nk}{n \choose k}_{\!q^{2}}}$.

Esta versión del coeficiente binomial cuántico es simétrica bajo intercambio de${\displaystyle q}$y${\displaystyle q^{-1}}$.