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:

Demostrar que $\begin{bmatrix} n \\ k \end{bmatrix}$ es un polinomio (y no sólo una función racional).

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.

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.

Posts aleatorios

Autor: ^DiAmOnD^ | Publicado el 27 de January de 2009
Categorías: Juegos | Imprime este post

Sin comentarios

Trackback | 27 Jan, 2009

Bitacoras.com
Manuel | 27 de January de 2009 | 14:49

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.
Tobar | 27 de January de 2009 | 16:30

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.
vengoroso | 27 de January de 2009 | 16:59

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).
Tobar | 27 de January de 2009 | 18:24

las permutaciones estan ligadas al coeficiente binomial mediante la siguiente identidad: $P(n,k) = k!\,C(n,k)$

${n\choose k} = {n-1\choose k-1} + {n-1 \choose k}$
Tobar | 27 de January de 2009 | 18:36

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.
J.E. | 27 de January de 2009 | 18:39

Bueno…

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

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

$(q-1)*\left[n\right]= q+q^2+q^3+\ldots q^n - (1+q+q^2+\ldots q^{n-1})$

$(q-1)*\left[n\right]= q^n-1$

$\left[n\right]= (q^n-1)/(q-1)$
^DiAmOnD^ | 27 de January de 2009 | 18:39

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.
Andrew | 27 de January de 2009 | 21:20

$Np^{x}=q$ , q=numero natural, n-esima potencia de un primo.
Naka Cristo | 27 de January de 2009 | 22:31

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.
M | 27 de January de 2009 | 22:43

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}$
M | 28 de January de 2009 | 19:45

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.
Manuel | 29 de January de 2009 | 10:58

Vengoroso: no has entendido mi objeción. Si desarrollas [n]! el objeto que obtienes NO es un q-entero.
M | 29 de January de 2009 | 11:36

Manuel, aunque hay que tener en cuenta lo que indicas, y yo no sea el más indicado para hablar sobre estos entes, su interés queda reflejada en muchos aspectos:

http://mathworld.wolfram.com/q-Analog.html

http://en.wikipedia.org/wiki/Field_with_one_element

Por cierto, hay una demo del q-triángulo de Pascal en
http://demonstrations.wolfram.com/QPascalTriangle/
vengoroso | 29 de January de 2009 | 11:58

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é
fede | 29 de January de 2009 | 14:05

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)
vengoroso | 29 de January de 2009 | 15:17

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?
fede | 29 de January de 2009 | 16:52

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.
fede | 29 de January de 2009 | 21:13

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$ .
fede | 30 de January de 2009 | 20:49

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.