coeficiente binomial gaussiano

Una descripción combinatoria de los coeficientes binomiales gaussianos implica inversiones .

El coeficiente binomial ordinario${\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 m-r}$:

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

counts the number of k-dimensional vector subspaces of an n-dimensional vector space over ${\displaystyle \mathbb {F} _{q}}$ (the points of a Grassmannian). When expanded as a polynomial in q, it yields the well-known decomposition of the Grassmannian into Schubert cells. For example, the Gaussian binomial coefficient

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

is the number of one-dimensional subspaces in (F_q)ⁿ, or equivalently the number of points in the associated projective space. Furthermore, when q is 1 (respectively −1), the Gaussian binomial coefficient yields the Euler characteristic of the corresponding complex (respectively real) Grassmannian.

The number of k-dimensional affine subspaces of F_qⁿ is equal to

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

This allows another interpretation of the identity

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

as counting the (r − 1)-dimensional subspaces of (m − 1)-dimensional projective space by fixing a hyperplane, counting such subspaces contained in that hyperplane, and then counting the subspaces not contained in the hyperplane; these latter subspaces are in bijective correspondence with the (r − 1)-dimensional affine subspaces of the space obtained by treating this fixed hyperplane as the hyperplane at infinity.

Gaussian binomial coefficients play an important role in the cyclic sieving phenomenon. Let C be a cyclic group of order n with generator c. Let X be the set of k-element subsets of the n-element set {1, 2, ..., n}. The group C has a canonical action on X given by sending c to the cyclic permutation (1, 2, ..., n). The number of fixed points of c^d on X is equal to

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

where q is taken to be the d-th power of a primitive n-th root of unity.

In the conventions common in applications to quantum groups, a slightly different definition is used; the quantum binomial coefficient there is

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

This version of the quantum binomial coefficient is symmetric under exchange of ${\displaystyle q}$ and ${\displaystyle q^{-1}}$.