Tarea cálculo 3 

No he podido subir los archivos (ya los tengo) porque son grandes y se cancela la subida a la mitad. Sigo intentando…

 

Finalmente ya se pudo:

Anuncios

Gradientes y curvas de nivel con SAGE

Este es el archivo para la práctica en SAGE que se discutirá en clase sobre gradientes y curvas de nivel:    DESCARGA

RSK correspondence in SAGE

SAGE has a function to perform Robinson-Schensted algorith on a permutation. However it lacks the Robinson-Schensted-Knuth generalization that gives the bijection between nonnegative integer matrices and pairs of semistandard Young tableau.

After waiting a long time hoping someone would implement it, I needed it to do some checks related to my thesis, so I took RS code and adapted it. Posting here so it won’t get lost.

from itertools import izip
from bisect import bisect
def RSK(M):
    """ Implementation of the Robinson-Schensted-Knuth algorithm 
        for non negative integer matrices, based on the Robinson-Schensted implementation for Permutations 

    
    """
    # M is the matrix corresponding to the pair of tableau (P,Q)

    # First we create the double-row array
    upperrow = []
    lowerrow = []
    for r in range(M.nrows()):
        fila = M[r]
        for c in range(len(fila)):
            for k in range(M[r][c]):
                upperrow.append(r+1)
                lowerrow.append(c+1)
    p = []       #the "insertion" tableau
    q = []       #the "recording" tableau

    # We proceed to do bumping algorithm on lower row
    # and recording places on upper row
    for a,b in izip(upperrow, lowerrow):
        for r,qr in izip(p,q):
            if r[-1] > b:
                y_pos = bisect(r,b)
                b, r[y_pos] = r[y_pos], b
            else:
                break
        else:
            r=[]; p.append(r)
            qr = []; q.append(qr)
        
        r.append(b)
        qr.append(a)
    return [Tableau(p), Tableau(q)]

Example.

Perform the RSK correspondence on  matrix
\begin{pmatrix} 1&0&2 \\ 0&2&0 \\ 1&1&0 \end{pmatrix}

Me= Matrix( [[1,0,2],[0,2,0],[1,1,0]] )
RSK(Me)

[[[1, 1, 2, 2], [2, 3], [3]], [[1, 1, 1, 3], [2, 2], [3]]]

gives the pair of tableau
P:

1 1 2 2
2 3
3

and
Q:

1 1 1 3
2 2
3

SAGE: Práctica 1

Este es el archivo de la primera sesión de práctica con SAGE: Práctica 1 .

Para abrirlo, entra a tu cuenta de SAGE (ya sea en tu computadora o en la versión en línea) y usa el enlace upload.

El enlace upload sirve para añadir el archivo a tu cuenta

Luego indica el archivo que descargaste al inicio

EPIC WIN!!!!

Cualquier duda, la pueden dejar ahí abajo o a mi correo ¿lo apuntaron, verdad?

Tarea sobre funciones generadoras

Del curso de matemáticas discretas.

Recuerden que esta tarea no es para entregar, es de práctica para el examen.

  1. Resuelve las recurrencias:
    1. a_n=5a_{n-1} + 2 para n\ge 1, con a_0=0.
    2. a_n = c a_{n-1} +b para n\ge 1, con a_0=0 y c,b constantes.
    3. a_{n+2} = 2 a_{n+1}- a_n para n\ge 0 y a_0=0, a_1=1.
  2. Para cada una de las siguientes sucesiones, encuentra de forma explícita la función generadora ordinaria y la función generadora exponencial.
    1. a_n=n.
    2. a_n=n^2.
    3. a_n=3^n.
    4. a_n = 5\cdot 4^n - 7\cdot 2^n.
  3. Si A(x) es la función generadora de la sucesión a_0, a_1,a_2, a_3, \ldots, ¿cual es la función generadora ordinaria de las sucesiones b_n?
    1. b_n = a_n + c.
    2. b_n= n a_n.
    3. 0,0,0,a_0,a_1,a_2,a_3,a_4,\ldots.
    4. a_0, 0,a_1,0,a_2,0,a_3,0,a_4,\ldots.
    5. a_5,a_6,a_7,a_8,a_9, \ldots.
    6. a_0, a_2, a_4, a_6, a_8,\ldots.
  4. Si F(x) es la función generadora exponencial de la sucesión a_0, a_1, a_2, a_3,\ldots, ¿cuales son las funciones generadoras exponenciales de las sucesiones en el inciso anterior?
  5. Si A(x) es la función generadora ordinaria \sum_{n\ge 0} a_n x^n. ¿Cual es la función generadora ordinaria de la sucesión
    a_0, a_0+a_1, a_0+a_1+a_2, a_0+a_1+a_2+a_3,\ldots?
  6. Demuestra que si p_{par}(n) es el número de formas de particiones de n donde todas las partes son pares entonces
    \sum_{n\ge 0} p_{par} (n) = \prod_{k\ge 0} \frac{1}{1-x}
    Por ejemplo, para n=10 las particiones con partes pares son  [10], [8,2], [6,4],[6,2,2], [4,4,2],[4,2,2,2],[2,2,2,2,2,] y por tanto p_{par}(10)=7.
  7. ¿Cual es el coeficiente de x^n en el desarrollo de \frac{1}{(1-x^2)^2} ?
  8. Usa el método de funciones generadoras para hallar una fórmula para:
    1. la suma de  los primeros n números consecutivos.
    2. la suma de los cuadrados de los primeros n números consecutivos.
      Sugerencia: Considera el problema 5.
  9. ¿Cual es la función generadora de la sucesión  1,  1/2, 1/3, 1/4, … ?
  10. ¿Cual es la función generadora de la sucesión h_n donde
    h_n = 1 + \frac{1}{2} + \frac{1}{3} +\frac{1}{4} + \cdots + \frac{1}{n}
    para n\ge 1 ?

Examen final: Matemáticas discretas I, 2010

El examen se aplicó a los estudiantes de la licenciatura de Física-Matemáticas en dos fechas, el 30 de junio (la fecha programada) y otra opción el 6 de julio para quienes querían esperar algunos días.

Examen del 30 de junio.

INSTRUCCIONES: Selecciona 5 de los 6 problemas y resuélvelos.

Problema 1. Demuestra que el número de soluciones enteras y positivas de la ecuación x_1+x_2+x_3+x_4=9 es el mismo que el número de soluciones enteras y positivas de la ecuación x_1+x_2+x_3+x_4+x_5+x_6=9.

Problema 2. Las fichas en un juego de poker pueden ser rojas, azules o blancas. ¿De cuántas formas se puede hacer un montón con 12 fichas?

Problema 3. Demuestra mediante alguna biyección que si X es un conjunto con n elementos, entonces la
cantidad de subconjuntos con un número par de elementos es la misma que la cantidad de subconjuntos con un número impar de elementos.

Problema 4. Sea G una gráfica simple con 10 vértices y 28 aristas. Demuestra que contiene un ciclo de
longitud 4.

Problema 5. Demuestra usando un argumento combinatorio que
\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \cdots +  n\binom{n}{n}= n 2^{n-1}.

Problema 6. Encuentra dos gráficas simples y conexas que tengan la misma sucesión de grados pero que no sean isomorfas (¡demuestra que no lo son!).

Examen del 6 de julio.

INSTRUCCIONES: Selecciona 5 de los 7 problemas y resuélvelos.

Problema 1. ¿De cuántas formas puedes acomodar en fila 10 unos y 5 ceros de tal forma que no haya dos ceros en posiciones contiguas?

Problema 2. ¿Cuántas gráficas simples con 12 vértices existen?

Problema 3. ¿Cuántas soluciones tiene la ecuación x_1+x_2+x_3+x_4+x_5=24 si cada x_i es entera y positiva?

Problema 4. Si mn⩾2,
a) ¿Cuántos ciclos de longitud 4 hay en la gráfica K_{m,n}?
b) ¿Cuántas trayectorias de longitud 2 hay en K_{m,n}?
c) ¿Cuántas trayectorias de longitud 3 hay en K_{m,n}?

Problema 5. Demuestra usando un argumento combinatorio que (n-k)\binom{n}{k} = n\binom{n-1}{k}.

Problema 6. Si d_n es el número de formas de cubrir una cuadrícula de 2×n con dominós, demuestra que
d_{n+2}=d_0 + d_1 + d_2 + \cdots + d_{n-1}+d_n .

Problema 7. Sea X = {1,2,3,…,20}. Demuestra mediante alguna biyección que la cantidad de subconjuntos de
X con un número par de elementos es la misma que la cantidad de subconjuntos de X con un número impar de elementos.

Examen parcial: Matemática discreta

Este es el 3er parcial del curso de matemática discreta (tema: teoría de gráficas).

  1. Sea G una gráfica simple sin ciclos. Demuestra que |E| = |G|-\omega(G).
  2. Sea G una gráfica simple (posiblemente disconexa). Si G es 4-regular, entonces puedes colorear las aristas de rojo o azul de forma que cada vértice tenga el mismo número de aristas de cada color.
  3. Si en una gráfica simple cada vértice tiene grado k (k\ge 2), prueba que debe existir un ciclo de longitud mayor o igual a k+1.
  4. Si G, H son dos gráficas simples con el mismo número de vértices y las listas ordenadas de los grados de los vértices en cada gráfica son iguales, ¿necesariamente son gráficas isomorfas?
  5. Sea G una gráfica con 10 vértices y 38 aristas. Demuestra que contiene a K_4 como subgráfica inducida.
  6. ¿Cuantos automorfismos tiene la gráfica siguiente?