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

Anuncios

Snakes (parte II)

Bueno, resulta que, el  aparentemente simple e inocente problema de las serpientes en realidad es un problema abierto en el área de combinatoria enumerativa.

Antes de plantear el problema que me interesa ahora, primero tengo que platicar cómo no se resuelve el problema de las serpientes.

Lo más natural al intentar resolver el problema es hacer algunos casos pequeños para darse una idea del comportamiento de la sucesión.

Serpientes, con su codificación

Como se sugirió en la entrada anterior, cada serpiende queda codificada por una sucesión de letras, indicando hacia dónde se hacen los giros.  Tabulando las cantidad de serpientes para cada longitud  tenemos:

1, 2, 4, 6, 10, 16, 26,…

Salvo los dos primeros términos, cada uno es igual a la suma de los dos anteriores, como en los números de Fibonacci. De hecho, salvo el primero todos son el doble de un número de Fibonacci. Vamos a denotar por s(n) el número de serpientes de longitud n y por f_n al n-ésimo número de Fibonacci. Conjeturamos entonces:

s(n)=2 f_n.

Fijándonos en las palabras que codifican cada serpiente, si I es un giro hacia la izquierda y D un giro para la derecha, entonces la lista de serpientes comienza como:

  • n=1. Sólo hay una palabra, vacía.
  • n=2. Hay 2 palabras, indicando los dos posibles giros:  I, D.
  • n=3. Las palabras posibles son II, ID, DI, DD.
  • n=4. Las palabras válidas son IID, IDI, IDD, DII, DID, DDI.  Nótese que III, DDD no son palabras váldias pues hacer 3 giros consecutivos en la misma dirección regresa al punto inicial y por tanto la serpiente se tocaría a sí misma.
  • n=5. Las palabras aquí son IIDI, IIDD, IDII, IDID, IDDI, DIID, DIDI, DIDD, DDII, DDID.

Unos casos más podrían convencernos que las serpientes corresponden a palabras donde no hay 3 símbolos consecutivos iguales.

Ahora, antes de seguir hay que aclarar que la descripción anterior sólo es corecta hasta n=11, porque a partir de entonces hay serpientes no válidas que no tienen 3 símbolos seguidos. Por ejemplo:

  • IDIIDIIDIID no es una serpiente válida, pues termina en el punto inicial y por tanto se corta a sí misma.

IDIIDIIDIID no tiene 3 símbolos iguales consecutivos

Esto quiere decir que la descripción simple que conjeturamos para las serpientes no es la correcta. De hecho, tampoco es cierta la conjetura de que el número de serpientes siempre es el doble de un número de Fibonacci (y precisamente a partir de n=12 falla la conjetura.

¿Cual es entonces la sucesión real de número de serpientes? ¿Porqué los primeros términos de la sucesión están relacionados con los números de Fibonacci?

Para calcular los valores reales de la sucesión usamos la computadora para generar todos los caminos hasta cierta longitud. El siguiente programa, en el lenguaje de programación Ruby genera todas las posibles serpientes y muestra la sucesión asociada.

#! /usr/bin/ruby
# coding: utf-8

def dir(q,p)
	#   dirección de p-->q
	v=[q[0]-p[0],q[1]-p[1]]
	if v == [0,1]
		return :N
	elsif v==[0,-1]
		return :S
	elsif v==[1,0]
		return :E
	elsif v==[-1,0]
		return :W
	end
end

def mueve(x, d)
	if d == :N
		return [x[0], x[1]+1]
	elsif d == :S
		return [x[0], x[1]-1]
	elsif d == :E
		return [x[0]+1,x[1]]
	elsif d == :W
		return [x[0]-1,x[1]]
	end
	return [x[0],x[1]]
end

def gira(d, c)
	#puts "girando #{d}"
	if c == 1  # giro positivo
		if d == :N
			return :W
		elsif d == :W
			return :S
		elsif d == :S
			return :E
		elsif d== :E
			return :N
		end
	elsif c== -1   #giro negativo
		if d == :N
			return :E
		elsif d == :E
			return :S
		elsif d == :S
			return :W
		elsif d == :W
			return :N
		end
	end
end

def recorre(s)    # Esta función "recorre" una cadena y regresa falso si se corta a sí misma
	puntos=[[0,0],[1,0]]
	s.downcase!
	s.each_char{ |c|
		p=puntos[-2]
		q=puntos[-1]
		diractual = dir(q,p)
		if c == "d"
			newdir=gira(diractual, -1)
		elsif c=="i"
			newdir=gira(diractual, 1)
		elsif c=="a"
			newdir = diractual
		end
		a=puntos[-1]
		b=mueve(a,newdir)
		if puntos.include?(b)
			return false
			break
		else
			puntos << b
		end
	}
	return s
end

def main       #Aquí generamos todas las serpientes
levels=[""]
print "1"
0.upto(20){ |n|    #Iteramos sobre todas las longitudes
	past=levels
	new=[]
	past.each{ |s|      # Y para cada una de longitud n-1, intentamos extenderla
		if recorre(s+"i") then new << s+"i" end
		if recorre(s+"d") then new << s+"d" end
		#if recorre(s+"a") then new << s+"a" end   # Activar esta línea para permitir avanzar sin girar
	#puts "level #{n} genera #{new}"
	}
	print ", #{new.length}"     # Finalmente mostramos cuántas hubo en ese nivel
	levels = new
}
end

main

El resultado de correr el programa es

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 282, 452, 724, 1160, 1842, 2936, 4688, 7480, 11844, 18826, 29956

que difiere de la sucesión de dobles de Fibonacci a partir de la posición 12.

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422

Podemos consultar datos sobre la segunda sucesión en la base de datos OEIS

Polinomios que cuentan

Imagina que queremos contar de cuantas formas se puede contar de cuantas formas se puede obtener 8 al tirar un par de dados. Uno puede realizar el clásico diagrama de coordenadas

Y concluir que hay 5 formas de obtener el 8.  Con el mismo diagrama, podemos encontrar el resultado f(k) para cualquier suma k:

f(2)=1, f(3)=2, f(4)=3, f(5)=4, f(6)=5, f(7)=6, f(8)=5, f(9)=4, f(10)=3, f(11)=2, f(12)=1.

Pero ¿qué pasa si queremos tirar tres dados? ¿cinco dados? ¿20 dados? ¿m dados? Ya no es práctico usar la representación de coordenadas, necesitamos un nuevo modelo.

Consideremos sólo un dado. ¿De cuantas formas podemos obtener el valor k? Pues de 1 forma si k=1,2,3,4,5,6  y 0 de cualquier otra forma.  Vamos a codificar todos los resultados posibles en una única expresión:

a+a^2+a^3+a^4+a^5+a^6

Donde los exponentes representan los valores de los dados y los coeficientes (todos 1) representan el número de formas de obtener esos valores.  Así, por ejemplo,  a^3 = 1a^3 indica que sólo hay 1 forma de obtener a^3.

Ahora, si tenemos dos dados, pues son dos polinomios a considerar:

(a+a^2+a^3+a^4+a^5+a^6)(a+a^2+a^3+a^4+a^5+a^6)

Hacemos la multiplicación y el resultado es…

a^2+2a^3+3a^4+4a^5+5a^6+6a^7+5a^8+4a^9+3a^{10}+2a^{11}+a^{12}.

Los coeficientes son precisamente el número de formas de obtener el exponente al tirar dos dados.  De hecho, el coeficiente de  a^k en el desarrollo de (a+a^2+a^3+a^4+a^5+a^6)^m es el número de formas de obtener el valor k al tirar m dados y con esta información podemos encontrar el valor exacto.

Observamos que a+a^2+a^3+a^4+a^5+a^6 es una serie geométrica, por lo que

a+a^2+a^3 +a^4+a^5 +a^6 = a \left( \frac{1-a^6}{1-a} \right)

y por tanto

(a+a^2+a^3+a^4+a^5+a^6)^m=a^m(1-a^6)^m(1-a)^{-m}

Ejemplo.

¿De cuántas formas se puede obtener 15 al tirar 8 dados?

El resultado es el coeficiente de a^{15} en  a^8 (1-a^6)^8 (1-a)^{-8}. Es decir, es el coeficiente de a^7 en (1-a^6)^8 (1-a)^{-8}.  Usando el teorema del Binomio (primero para exponentes enteros y luego para exponentes negativos) tenemos

(1-a^6)^8 (1-a)^{-8} = \left(\sum_{j=0}^8 {8 \choose j}(-a^6)^j\right)\left(\sum_{j\ge 0}{j+7 \choose 7}(-a)^j\right),

y al desarrollar, los términos que contienen a^7 son:

\binom{8}{0}\cdot \binom{14}{7}(-a)^7 + \binom{8}{1}(-a^6)\cdot \binom{8}{1}(-a),

con lo que concluimos que el número de formas de obtener 15 al tirar 8 dados es

{14\choose 7} - 64 = 3368.

Reflexiones.

Entre las cuentas, puede perder uno de punto de vista la idea central: estamos representando una sucesión de varios valores (formas de tirar un dado) mediante un solo objeto algebraico (un poliomio), y manipulaciones con este objeto nos dan información acerca de la combinatoria del problema.

El método puede modificarse para resolver problemas similares (por ejemplo, si quisiéramos saber de cuántas formas se puede obtener 30 al tirar 3 dados normales y dos dados en forma de icosaedro, intentaríamos encontrar el coeficiente de a^{30} en el desarrollo de

(a+a^2+a^3+a^4+a^5+a^6) ^3 (a+a^2+a^3+\cdots+a^{20})^2

Este es un caso particular del método de funciones generadoras, en el que una serie de potencias representa una cantidad (posiblemente infinita) de valores de una sucesión.

Bibliografía.

  • Aigner, Martin. A Course in Enumeration. Graduate Texts in Mathematics, 238. (2007)
  • Bona, Miklós. Introduction to Enumerative Combinatorics.  McGraw Hill Higher Education. (2007)
  • Camina and Lewis. An Introduction to Enumeration.  Springer Undergraduate Mathematics Series. (2010)

Snakes (parte I)

Snake, snake, snake, snake, snake, snake, snake, snake, snake, …

Hace unos días, vihart subió un video a youtube en el cual muestra diferentes cosas que hace con unas serpientes para armar.

Ahora, entre todas las cosas que dice, la parte que me interesa aquí está entre 0:45 y 1:30 donde plantea un par de problemas matemáticos relacionados.

El primero de ellos podría describirse así: considera una serpiente formada por 10 segmentos. Cada segmento forma un ángulo de 90º respecto al anterior. ¿Cuantas serpientes (lo que llama slithers) se pueden obtener?

Por ejemplo, si las serpientes están formadas por 4 segmentos, algunas posibles opciones serían las siguientes

Ejemplos de serpientes con 4 segmentos. La flecha indica la posición de la cabeza.

Inmediatamente surge el primer problema. ¿Cuando decir que dos serpientes son iguales? ¿Será cierto que la primera y la tercera serpiente del ejemplo son iguales?

Esa pregunta, al menos, la resolvemos usando un truco clásico, ilustrado en el video: codificar un problema combinatorio mediante palabras.   En el video se muestra que cada serpiente corresponde a una serie de letras indicando su estructura (estando en inglés, pone L para izquierda, R para derecha).

Nosotros indicaremos con la I un giro a la izquierda y con D un giro a la derecha. Así, por ejemplo, las 3 serpientes del ejemplo corresponden a las palabras

IID, IDI, DDI.

En la primera, por ejemplo, al recorrer el primer segmento (horizontal) se hace un giro de 90º hacia la izquierda y por tanto se continúa hacia arriba; después del segundo segmento se gira hacia la izquierda nuevamente, quedando el camino apuntando hacia la izquierda; finalmente se hace un giro hacia la derecha y la cabeza termina apuntando hacia arriba. Esos giros los representamos como IID.

La otra regla implícita es que una serpiente no puede en ningún momento tocarse (por ejemplo, una instrucción III haría que la cabeza toque la cola (se forma un cuadrado), lo cual no es válido.

Para dejar completamente en claro el problema, ilustramos las 6 distintas serpientes que se pueden hacer con 4 segmentos:

 

Las 6 serpientes formadas con 4 segmentos

Observación: nota que la dirección inicial no importa realmente, sólo la forma de la serpiente. Por ello, para simplificar los dibujos, siempre he puesto el primer segmento horizontal y hacia la derecha (piensa en una cuadrícula…).  Esto quiere decir que una serpiente la podemos girar, pero no podemos levantarla y reflejarla. Por eso, la segunda serpiente en ambas figuras es la misma: IDI, mientras que, aunque también es una escalera, la quinta DID es diferente, porque no se puede girar para hacerla coincidir con IDI.

El segundo problema es completamente similar, excepto que no se requiere que cada segmento forme un ángulo de 90º con el anterior, sino que se permite que varios segmentos avancen en la misma dirección; a estas variantes les llama snakes (y que aquí llamaremos víboras). Así, una víbora que no es serpiente podría ser:

Una víbora: derecha-avance-izquierda

En este caso tenemos tres posibilidades para movimiento: Derecha, Izquierda y Avanzar.

Problemas.

Entonces, tenemos los dos problemas planteados:

  1. Determinar el número de serpientes con 10 segmentos.
  2. Determinar el número de víboras con 10 segmentos.

Sin embargo, lo que me llamó la atención de este problema, planteado de pasada en apenas un minuto, es que tiene muchas matemáticas detrás, y es posible plantear muchas preguntas interesantes acerca del problema (algunas de las cuales hasta ahora desconozco la respuesta).

El primer paso siguiente es evidente para cualquiera que tenga sensibilidad para las matemáticas:

  • ¿Cual es el número de serpientes con n segmentos?
  • ¿Cual es el número de víboras con n segmentos?

En caso que no sea posible encontrar una fórmula cerrada ¿hay algún tipo de recurrencia? (Bueno, si la hay es muy probable que se puede encontrar también  una fórmula cerrada usando el método de funciones generadoras)

Un problema intermedio para la resolución anterior es:

  • ¿Cuales son las condiciones necesarias y suficientes para que una palabra sea una serpiente o una víbora? Es decir, encontrar una forma de decidir si una sucesión como IDDIDIDDDII es una serpiente o no (porque podría cruzarse a sí misma. Y de forma similar, una forma para decidir si una sucesión de letras forma una víbora válida.

Por otro lado, aunque son problemas muy parecidos, podría ser posible que uno problema tenga solución sencilla y el otro no.

Al intentar resolver el problema, es natural empezar a realizar casos pequeños. Sin embargo, después de unos cuantos segmentos el problema se hace tedioso manualmente. Esto crea nuevos problemas de otro estilo:

  • Elaborar un programa de computadora que liste (y por tanto cuente) todas las serpientes con n segmentos.
  • Elaborar un programa de computadora que liste (y por tanto cuente) todas las víboras con n segmentos.

Si te tomas unos minutos haciendo dibujos, observarás que puede haber muchísimas direcciones. Por otro lado, que los ángulos sean rectos y que los segmentos todos sean iguales, sugiere que las serpientes en realidad son caminos sobre un plano cartesiano:

Una serpiente es un camino reticular en el plano cartesiano

Inmediatamente se me ocurren dos problemas :

  • Determinar (sin necesidad de un dibujo) la posición de la cabeza a partir de una palabra. Por ejemplo la palabra IDDIDI termina en (4,-1). ¿Cómo se llega a esa conclusión sin dibujar?  Nuevamente, tenemos un problema para serpientes y otro para víboras.
  • ¿Cual es el  menor rectángulo que contiene a la serpiente (víbora)? En la figura anterior es el rectángulo de 2×2 que tiene esquinas (0,0), (2,2). (Piensa en la menor caja en la que cabría la serpiente).

En ambos problemas asumimos que el primer movimiento es de (0,0) a (0,1), es decir, una unidad en la dirección x. (No era tan arbitraria la elección hecha arriba al dibujar las serpientes).

Finalmente, podemos obtener una nueva clase de problemas (y para éstas repetir todos los anteriores) si en vez de 90º indicamos que las serpientes tengan que formar un ángulo que sea múltiplo de 60º. Por ejemplo, una hexaserpiente podría ser algo como:

Una hexaserpiente, moviéndose sobre una retícula triangular

Yo creo que un buen problema matemático no sólo es aquél que es interesante resolver en sí mismo y ya, sino que al mismo tiempo permite formular muchas ideas nuevas, plantear nuevas preguntas, generalizaciones, variantes, etc.

Mucha suerte con las serpientes.

Ah, y ¡feliz día π!

El problema de Catalan

El problema de Catalan consiste en determinar el número de formas Cn en que se puede calcular el producto de n factores ordenados, realizando las operaciones por parejas.

Por ejemplo, si n=4, el producto abcd puede calcularse de las siguientes cinco formas:

  • [(a\cdot b)\cdot c]\cdot d,
  • [a\cdot(b\cdot c)]\cdot d,
  • (a\cdot b)\cdot(c\cdot d),
  • a\cdot [b\cdot(c\cdot d)],
  • a\cdot[(b\cdot c)\cdot d].

Hay un bonito artículo en Wikipedia explicando cómo obtener una relación recursiva para calcular estos números:

C_n=\sum_{k=1}^{n-1} C_k C_{n-k}.

Que, como todos ya sabemos, es la recurrencia que genera los números de Catalan.

Ahora, es común definir los números de Catalan como el número de formas de recorrer una cuadrícula de n×n partiendo de la coordenada (0,0) hasta la (n,n) de manera que los movimientos permitidos sean a la derecha y hacia arriba y no se permite cruzar la diagonal. Por ejemplo

Media_httpuploadwikim_arnkk

(Imagen de Wikimedia Commons)

son las C4=14 formas de recorrer la cuadrícula de 4×4.

El problema planteado aquí es: establece una correspondencia entre las formas de poner paréntesis a n factores y las formas de recorrer la cuadrícula de n×n siguiendo las reglas mencionadas.

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.