Problema sobre q-enteros

Publicado por ^DiAmOnD^ | 27 enero, 2009 | Juegos | 19 |

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.

0 0 votes

Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉

Sobre el 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. También tengo un blog dedicado a las "escape rooms", por si te apetece pasarte: XRooMers.

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.

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

19 Comments

más antiguo

más reciente más votado

Inline Feedbacks

View all comments

Bitacoras.com

27/01/2009 09:02

Información Bitacoras.com…

Si lo deseas, puedes hacer click para valorar este post en Bitacoras.com. Gracias….

Responde

Manuel

27/01/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.

Responde

Tobar

27/01/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.

Responde

vengoroso

27/01/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).

Responde

Tobar

27/01/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}$

Responde

Tobar

27/01/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.

Responde

J.E.

27/01/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)$

Responde

^DiAmOnD^

27/01/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.

Responde

Andrew

27/01/2009 21:20

$Np^{x}=q$ , q=numero natural, n-esima potencia de un primo.

Responde

Naka Cristo

27/01/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.

Responde

27/01/2009 22:43

Muy interesante el problema y lo que rodea a estos números. 1) Que es un polinomio (en ) de grado se obtiene del mismo modo que ya hiciéramos en https://gaussianos.com/fraccion-polinomica/ 2) Para el segundo apartado, por abreviar pongamos , y sea q potencia de un primo Si es linealmente independiente en , debe ser que no es combinación de las combinaciones posibles de . Es decir que dados , tenemos posibilidades para , y en consecuencia tenemos posibles sistemas de vectores lin. indep. Esto también nos dice que cada subespacio de con dimensión admite bases posibles. Dividiendo ambas expresiones obtenemos… Lee más »

Responde

28/01/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.

Responde

Manuel

29/01/2009 10:58

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

Responde

29/01/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/

Responde

vengoroso

29/01/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… Lee más »

Responde

fede

29/01/2009 14:05

vengoroso, los 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 es un par (i,j) que cumple i < j y > ) De donde me parece que los coeficientes del polinomio expresado en términos de es el numero de secuencias de k unos y n-k… Lee más »

Responde

vengoroso

29/01/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?

Responde

fede

29/01/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… Lee más »

Responde

fede

29/01/2009 21:13

Si , (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 . o, cambiando letras, . Si es el numero de secuencias de a unos y b ceros con exactamente n inversiones, , porque esas secuencias o empiezan por cero (y hay de estas, porque al quitar el cero inicial no quitamos ninguna inversión) o empiezan por uno (y hay de estas, porque al quitar el uno inicial quitamos tantas inversiones… Lee más »

Responde

fede

30/01/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.