Problema sobre q-enteros

Nuestro amigo vengoroso me envió hace un tiempo un problema que os planteo hoy a vosotros:

Llamamos números q-enteros a los polinomios:

\left [ n \right ] = 1+q+q^2+ \ldots q^{n-1}

Con estos números podemos construir, por ejemplo, los q-factoriales:

\left [ n \right ] != \left [ n \right ] \cdot \left [ n-1 \right ] \cdot \ldots \cdot \left [ 2 \right ] \cdot \left [ 1 \right ]

También podemos construir los números q-combinatorios:

\begin{bmatrix} n \\ k \end{bmatrix} = \cfrac{\left [ n \right ] !}{\left [ k \right ] ! \; \left [ n-k \right ] !}

A partir de aquí planteamos varias preguntas:

  1. Demostrar que \begin{bmatrix} n \\ k \end{bmatrix} es un polinomio (y no sólo una función racional).
  2. Si fijamos q un número natural que sea potencia de un primo y consideremos F_q el cuerpo finito con q elementos, demostrar que el conjunto de todos los subespacios vectoriales de dimensión k dentro de (F_q)^n tiene exactamente \begin{bmatrix} n \\ k \end{bmatrix} elementos.
  3. Hallar el polinomio de Taylor de la función N_{n,k}(q)= \begin{bmatrix} n \\ k \end{bmatrix} en un entorno de q=1.

A por él.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

19 Comentarios

  1. Uhmm…. pero el factorial de un q-entero NO es otro q-entero. Esto no impide intentar la solución, pero estéticamente queda feo.

    Publica una respuesta
  2. 1. El coeficiente binomial {n \choose k} es el coeficiente del término x^ky^{n-k}, obtenido al desarrollar (x+y)^n.

    2. El coeficiente binomial {n\choose k} es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

    Publica una respuesta
  3. Manuel, la relación de estos polinomios con las correspondientes nociones clásicas se tiene cuando tomas q=1. En ese caso recuperas los enteros, factoriales, etc. de toda la vida.

    Tobar, los números q-combinatorios aparecen de manera similar, cuando consideras la expansión del binomio (X+Y)^n pero donde consideras que X, Y en vez de ser variables que conmutan entre sí verifican YX = qXY (esto puede pasar con matrices 2\times 2, por ejemplo). Y en vez de contar subconjuntos, cuentan ciertos subespacios vectoriales (eso es lo que pretende probar el apartado 2).

    Publica una respuesta
  4. de manera compacta…

    T(\mathbf{x}) = f(\mathbf{a}) + \nabla f(\mathbf{a})^T (\mathbf{x} - \mathbf{a}) + \frac{1}{2} (\mathbf{x} - \mathbf{a})^T \nabla^2 f(\mathbf{a}) (\mathbf{x} - \mathbf{a}) + \cdots

    luego… ya dependiendo del entorno que se dice en el enunciado. … .

    T(\mathbf{x}) = \sum_{|\alpha| \ge 0}^{}{\frac{\mathrm{D}^{\alpha}f(\mathbf{a})}{\alpha !}(\mathbf{x}-\mathbf{a})^{\alpha}}

    en la que incluyo la matriz hessiana y gradiantes.

    H(f) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n} \\ \frac{\partial^2 f}{\partial x_2\partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n\partial x_1} & \frac{\partial^2 f}{\partial x_n\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}

    buff… debo descansar, eso era respecto a la heissiana.

    Publica una respuesta
  5. Tobar lo que estás comentando no tiene que ver con el problema. Son definiciones de conceptos que aparecen en el problema, sí, pero no tienen nada que ver con el asunto en cuestión. Por favor, intenta centrarte en el asunto.

    Publica una respuesta
  6. Tengo el punto 1

    Primero tenemos la identidad
    \left[n\right]-\left[k\right]=q^k\left[n-k\right]
    que es inmediata

    También tenemos de forma inmediata
    $latex \begin{bmatrix}n\\n\end{bmatrix}=
    \begin{bmatrix}n\\ 0\end{bmatrix}=1$

    Y ahora un pelín más difícil es sacar
    $latex \begin{bmatrix}n\\ k\end{bmatrix}=
    \begin{bmatrix}n-1\\ k-1\end{bmatrix}+
    q^k\begin{bmatrix}n-1\\ k\end{bmatrix}
    $

    $latex \begin{bmatrix}n\\k\end{bmatrix}=
    \frac{\left[n-1\right]!}{\left[k\right]!\left[n-k\right]!}
    (\left[k\right]+(\left[n\right]-\left[k\right]))=
    \begin{bmatrix}n-1\\k-1\end{bmatrix}+
    \frac{\left[n-1\right]!(\left[n\right]-\left[k\right])}{\left[k\right]!\left[n-k\right]!}=$
    $latex =\begin{bmatrix}n-1\\k-1\end{bmatrix}+
    q^k\begin{bmatrix}n-1\\k\end{bmatrix}$

    Y ahora por inducción podemos escribir todos los q-combinatorios en función de otros más pequeños hasta llegar a los triviales haciendo sólo sumas y multiplicaciones.

    Publica una respuesta
  7. Muy interesante el problema y lo que rodea a estos números.

    1) Que \begin{bmatrix} n \\ k \end{bmatrix} es un polinomio (en q\in\mathbb{C}) de grado (n-k)k se obtiene del mismo modo que ya hiciéramos en http://gaussianos.com/fraccion-polinomica/

    2) Para el segundo apartado, por abreviar pongamos V=(F_q)^n, y sea q potencia de un primo

    Si \{v_1,\ldots,v_l\} es linealmente independiente en V, debe ser que v_l no es combinación de las q^{l-1} combinaciones posibles de v_1,v_2,\ldots,v_{l-1}. Es decir que dados v_1,\ldots,v_{l-1}, tenemos q^n-q^{l-1} posibilidades para v_l, y en consecuencia tenemos (q^n-1)(q^n-q)\ldots (q^n-q^{k-1}) posibles sistemas de k vectores lin. indep.

    Esto también nos dice que cada subespacio de V con dimensión k admite (q^k-1)(q^k-q)\ldots (q^k-q^{k-1}) bases posibles.

    Dividiendo ambas expresiones obtenemos el número de subespacios de dimensión k. Finalmente, hay que tener en cuenta que

    \begin{bmatrix} n \\ k \end{bmatrix}=\cfrac{(q^n-1)(q^{n-1}-1)\ldots (q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\ldots(q-1)}=\cfrac{(q^n-1)(q^n-q)\ldots (q^n-q^{k-1})}{(q^k-1)(q^k-q)\ldots(q^k-q^{k-1})}

    3) El tercero lo tengo que madurar un poco más, pues me sale algo engorroso. De momento, he obtenido lo siguiente

    \begin{bmatrix} n \\ n-1 \end{bmatrix}= \begin{bmatrix} n \\ 1 \end{bmatrix}=\displaystyle{\sum_{k=1}^n} {n \choose k}(z-1)^{k-1}

    Publica una respuesta
  8. Usando la propiedad de recurrencia que decía Naka Cristo, podemos sacar el desarrollo de
    \begin{bmatrix}n\\ k\end{bmatrix} alrededor de q=0 y luego trasladarlo a q=1.

    Tenemos que \begin{bmatrix}n+1\\ k\end{bmatrix}=q^k \begin{bmatrix}n\\ k\end{bmatrix}+\begin{bmatrix}n\\ k-1\end{bmatrix}=\begin{bmatrix}n\\ k\end{bmatrix}+q^{n-k}\begin{bmatrix}n\\ k-1\end{bmatrix}.

    Para \alpha=(\alpha_0,\alpha_1,\ldots,\alpha_k)\in\mathbb{N}^{k+1}, vamos a abreviar |\alpha|=\alpha_0+\ldots+\alpha_k y |\alpha|_*=0*\alpha_0+1*\alpha_1+\ldots+k*\alpha_k. Entonces, de la recurrencia sale

    \begin{bmatrix}n\\ k\end{bmatrix}=\displaystyle{\sum_{|\alpha|=n-1 \atop \alpha\in\mathbb{N}^{k+1}} q^{|\alpha|_*}}.

    Finalmente trasladamos a q=1:

    \begin{bmatrix}n\\ k\end{bmatrix}=\displaystyle{\sum_{|\alpha|=n-1 \atop \alpha\in\mathbb{N}^{k+1}} ((q-1)+1)^{|\alpha|_*}}=\displaystyle{\sum_{|\alpha|=n-1 \atop \alpha\in\mathbb{N}^{k+1}}} \displaystyle{\sum_{l=0}^{|\alpha|_*} {|\alpha|_* \choose l} (q-1)^l}

    Supongo que estoy matando moscas a cañonazos y que la respuesta puede darse de forma más cerrada, aunque vemos que para el caso k=1 \;(o\;n-1) esta expresión se reduce a la que indiqué ayer.

    Publica una respuesta
  9. Vengoroso: no has entendido mi objeción. Si desarrollas [n]! el objeto que obtienes NO es un q-entero.

    Publica una respuesta
  10. Manuel, disculpa si no te entendí correctamente. Tienes razón en lo que dices, pero como dice M los q-enteros aparecen en muchos sitios (geometría en cuerpos finitos, problemas deformación-cuantización, cálculo umbral) y uno no puede ignorarlos sólo porque queden feos. Lo que me pareció curioso es que esta familia de polinomios tenga propiedades tan parecidas a las de los números combinatorios, como el q-análogo de la fórmula de Stiffel (la relación de recurrencia que prubea Naka Cristo).

    M, buena tú solución. Para el punto 3 yo no fui capaz de encontrar una fórmula cerrada. El coeficiente q-binomial se puede escribir también como
    \begin{bmatrix} n \\ k \end{bmatrix} = \sum b_i q^i, donde b_i es el número de particiones con i elementos (vistas como diagramas de Young) que caben dentro de un rectángulo k\times(n-k) . A partir de aquí se puede hacer un cambio de variables, que da esencialmente lo mismo que obtienes tú.

    Yo opté por obtener los coeficientes del desarrollo tomando logaritmos y derivando con respecto de q. Con esto no tienes una fórmula cerrada, pero obtienes una recurrencia bastante curiosa (cambiando subíndices por superíndices, al estilo del cálculo umbral) que te permite obtener los coeficientes. Las cuentas son horribles, así que os las ahorraré 😉

    Publica una respuesta
  11. vengoroso, los b_h además de ser el número de particiones de h en un máximo de k partes y cuya parte máxima es n-k, son tambien el numero de secuencias formadas por k unos y n-k ceros que tienen exactamente h inversiones. (Las dos cantidades cumplen la misma relación de recurrencia, deducida de la relacion de recurrencia entre los q-coeficientes)
    (Donde una inversión de una secuencia a_1,\ldots ,a_n es un par (i,j) que cumple i < j y a_i > a_j)

    De donde me parece que los coeficientes c_h del polinomio expresado en términos de (q-1)^h es el numero de secuencias de k unos y n-k ceros con h ‘flechas’ distintas entre un 1 y un cero posterior en la secuencia. (Es decir de el numero de esas secuencias con h inversiones marcadas)

    Publica una respuesta
  12. fede, creo que no he comprendido del todo lo que dices, pero si es verdad que hay una interpretación combinatoria de los coeficientes c_h sería muy interesante. ¿Podrías explicarlo con algo más de detalle?

    ¿Crees que se puede expresar eso de las “flechas” usando un grafo bipartito (uno de los lados representado los 0’s, el otro los 1’s) orientado?

    Publica una respuesta
  13. No me expresé muy claramente…A ver ahora.
    Lo que quería decir es:
    Tomamos una secuencia, por ejemplo, de 5 ceros y 4 unos: 1 1 0 1 0 0 0 1 0
    Por encima de la secuencia dibujamos 3 arcos diferentes que unan unos con ceros posteriores, por ejemplo uno que enlace (en el ejemplo) la posicion 2 con la 3, otro que enlace la posición 2 con la 5 y otro que enlace la 4 con la 6.
    Cada arco empieza en un uno y termina en un cero.

    Esta es una secuencia de 4 unos y 5 ceros con 3 arcos (antes los llamaba flechas…) entre unos y ceros (posteriores a los 1).

    Entonces el número total de configuraciones de estas que se pueden formar con 4 unos y 5 ceros y 3 arcos colocados encima entre unos y ceros de la forma anterior es el coeficiente c_3 de (q-1)^3
    en la expansión \begin{bmatrix} 4+5 \\ 4 \end{bmatrix} = \sum c_k(q-1)^k

    Prepararé y pondré un argumento detallado.

    Publica una respuesta
  14. Si \displaystyle \begin{bmatrix} n \\ k \end{bmatrix} = \sum_{i \ge 0} p(k,n-k,i) q^i , (el sumatorio es en realidad un polinomio de grado k(n-k) )
    de la relación $latex \begin{bmatrix} n \\ k \end{bmatrix} = \begin{bmatrix} n-1 \\ k \end{bmatrix} +
    q^{n-k}\begin{bmatrix} n-1 \\ k-1 \end{bmatrix} $ se deduce, comparando coeficientes, que p(k,n-k,i) = p(k,n-k-1,i) + p(k-1,n-k, i-(n-k)) .
    o, cambiando letras, p(a,b,n) = p(a, b-1, n) + p(a-1, b, n-b).

    Si t(a,b,n) es el numero de secuencias de a unos y b ceros con exactamente n inversiones, t(a,b,n) = t(a, b-1, n) + t(a-1, b, n-b), porque esas secuencias o empiezan por cero (y hay t(a, b-1, n) de estas, porque al quitar el cero inicial no quitamos ninguna inversión) o empiezan por uno (y hay t(a-1, b, n-b) de estas, porque al quitar el uno inicial quitamos tantas inversiones como ceros haya en la secuencia).
    Como también es igual la situación en las condiciones iniciales t(a,b,0)=1, etc,
    resulta que t(a,b,n) = p(a,b,n).

    Si en lugar de expresar el polinomio  \begin{bmatrix} n \\ k \end{bmatrix} como \sum b_iq^i, lo escribimos como \sum c_i(q-1)^i (cambiamos de base),  \displaystyle c_i = \sum_h \binom{h}{i}b_h
    (porque \displaystyle q^a = ( (q-1)+1)^a = \sum_i \binom{a}{i}(q-1)^i).

    Una configuracion que consiste en una secuencia de k unos y n-k ceros en que hemos marcado i inversiones de las existentes en la secuencia, puede tener en total i inversiones, o i+1 o i+2, etc.

    Para cada h hay p(k,n-k,h) = b_h secuencias con exactamente h inversiones en total y para cada una de esas secuencias podemos elegir i inversiones de \dbinom{h}{i} formas.
    Sumando para cada posible h, obtenemos el numero total de secuencias con i inversiones de las existentes marcadas (con arcos o flechas en comentario anterior).
    Pero
     \sum_h \dbinom{h}{i} b_h = c_i .

    Publica una respuesta
  15. El resultado anterior en términos de grafos:
    c_i cuenta el número de grafos bipartitos diferentes que se pueden formar de la siguiente forma:
    – Dividimos el conjunto {V_1,V_2,\ldots ,V_n} en dos conjuntos de vértices A y B con k y (n-k) elementos respectivamente.
    – Trazamos i aristas desde elementos de A a elementos de B con índice mayor.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Si lo deseas, puedes hacer click para valorar este post en Bitacoras.com. Gracias....

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *