Relaciones laborales

septiembre 20, 2008

Bijective proofs preferredUn patrón de longitud n es una secuencia finita (a_1,\dots,a_n) de enteros positivos tal que para cada i\in\{1,\dots,n\} se tiene que o bien a_i=i o bien a_i=a_j para algún j con 1\leq j<i.

¿Cuántos patrones de longitud n hay?

LATER: Estas cosas se llaman patrones, porque describen la forma de cadenas de carácteres: reemplazo cada caracter por el número de posición en la cadena en que ese caracter aparece por primera vez. Una implementación naive en Haskell puede ser:

pattern :: Eq a => [a] -> [Int]
pattern s = code [] (s`zip`[1..])
  where code dict []                = []
        code dict ((c,i):cis) 
          | Just j <- lookup c dict = j : code dict  cis
          | otherwise               = i : code ((c,i):dict) cis

quijote = "En un lugar de la Mancha, de cuyo nombre no quiero acordarme, \ 
          \no ha mucho tiempo que vivía un hidalgo de los de lanza en \ 
          \astillero, adarga antigua, rocín flaco y galgo corredor." 

y, con esas definiciones, evaluar pattern quijote da

[1, 2, 3, 4, 2, 3, 7, 4, 9, 10, 11, 3, 13, 14, 3, 7, 10, 3,
19, 10, 2, 22, 23, 10, 25, 3, 13, 14, 3, 22, 4, 32, 33, 3,
2, 33, 37, 38, 11, 14, 3, 2, 33, 3, 45, 4, 47, 14, 11, 33,
3, 10, 22, 33, 11, 13, 10, 11, 37, 14, 25, 3, 2, 33, 3, 23,
10, 3, 37, 4, 22, 23, 33, 3, 75, 47, 14, 37, 79, 33, 3, 45,
4, 14, 3, 86, 47, 86, 89, 10, 3, 4, 2, 3, 23, 47, 13, 10, 7,
9, 33, 3, 13, 14, 3, 7, 33, 108, 3, 13, 14, 3, 7, 10, 2,
116, 10, 3, 14, 2, 3, 10, 108, 75, 47, 7, 7, 14, 11, 33, 25,
3, 10, 13, 10, 11, 9, 10, 3, 10, 2, 75, 47, 9, 4, 10, 25, 3,
11, 33, 22, 89, 2, 3, 155, 7, 10, 22, 33, 3, 32, 3, 9, 10,
7, 9, 33, 3, 22, 33, 11, 11, 14, 13, 33, 11, 177]

8 comentarios to “Relaciones laborales”

  1. quimey said

    Si hacer caso de lo de Bijective proofs encontre una recurrencia bastante linda(es muy parecida a la de los numeros combinatorios)
    Si llamamos a_k^l = cantidad de patrones de largo k con exactamente l numeros distintos nos damos cuenta de que a_k^1 = a_k^k=1 \forall k y que a_k^l = a_{k-1}^{l-1}+l a_{k-1}^l si 2\leq l \leq k-1 y k \geq 3

  2. charlydif said

    La cantidad de patrones es lo mismo que la cantidad de particiones de un conjunto etiquetado de n elementos.

  3. quimey said

    Despues de hacer varias cuentas pude calcular una funcion generatriz para a_k^l como solucion de la ecuacion diferencial en derivadas parciales:
    x y f_y(x,y) + (x y -1)f(x,y) +x y =0 con el dato inicial f(0,y)=f(x,0)=0, pero aca me doy cuenta que todo lo que aprendì no me sirve porque las curvas caracteristicas no cortan a estas rectas.😦

  4. Grin Without a Cat said

    Y para la suma \sum_l a_k^l x^k?

  5. quimey said

    Lo que encontre es \sum_{k=l}^{\infty} a_k^l x^k = \prod_{j=1}^{l} \frac{x}{1-jx}

  6. Grin Without a Cat said

    Y en la otra dirección, es decir, \sum_l a^l_kx^l?🙂

    A todo esto: esa ecuación diferencial es para la función generadora ordinaria, pero uno puede probar con otras, como la generadora exponencial, \sum_{k,l} \frac{a_{k,l}}{k!l!}x^ky^l, o solo considerarla `exponencial’ en una de las dos variables…

  7. Juan Domingo Petruzza said

    y para rematarla
    http://en.wikipedia.org/wiki/Bell_number
    el que tenga nombre propio y no haya fórmula bella en wikipedia es síntoma de que no la hay😦
    pero una prueba biyectiva sale al toque

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: