Bloque de Colores

Algunos resultados interesantes

Icono de Post March 3 2012 :: Combinatoria, Python, Uncategorized ::

Como conte en este post, para resolver el problema del post anterior, hice una serie de pruebas cuyos resultados se pueden ver acá. Me quedo un cubo triangularmente cortado de resultados de variaciones de los parámetros de la función descripta. Para acelerar un poco los tests, una vez que conseguí una solución (cuya demostración se puede encontrar en una hermosa versión typesetada en LaTeX acá) la programe en python usando técnicas de programacion dinámica. Esta versión se puede encontrar aqui.

Lo interesante fue que me quedaron varias secuencias de números y decidí ir a OEIS para testearlo. Me encontré entonces con una serie de resultados interesantes que decidí publicar acá para revisarlos mas adelante.

Resultados simples

  • Si m=n=k , la función devuelve una permutación. m!
  • si m=n, m<k => f(n, m, k) = k!/(k-m)!

Resultados interesantes

Parece existir algún tipo de patrón, lamentablemente no tengo el tiempo en este momento y sobre todas las cosas el nivel de matemática suficiente como para investigarlo un poco más. Escribo este post más que nada para revisarlo nuevamente después de haber pasado por Concrete Mathematics, que todavía no pude estudiar.

Algún otro resultado

Da la sensación de que jugando con las variables del cubo se encontrarían un montón de resultados interesantes.

Autor: Emiliano Martínez Luque.

Comments Off on Algunos resultados interesantes

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Icono de Post March 3 2012 :: Combinatoria, Lenguajes Formales, Lógica ::

Lo que estamos buscando es, dado A un alfabeto de tamaño k, la cantidad de cadenas de tamaño n que contienen exactamente m símbolos de A.

Para resolver este problema primero vamos a resolver lo siguiente:

Cuantas cadenas de tamaño n pueden ser creadas con todos los símbolos de un alfabeto de k símbolos?

Se propone la siguiente relación de recurrencia de 2 variables, donde:

n: representa el tamaño de la cadena

k: representa la cantidad de símbolos en el alfabeto

f(0, k) = 0

Para todo k, ya que la cantidad de cadenas de tamaño 0 que pueden formarse con todos los símbolos de A es 0.

f(1, 1) = 1

Ya que existe solo una cadena de tamaño 1 con 1 símbolo.

f(n, k) = k( f(n-1,k) + f(n-1, k-1) )

Demostración

Llamemos An,k al conjunto de todas las cadenas de tamaño n que contienen a todos los símbolos de A e intentemos construir todas las cadenas que pertenecen a este conjunto.

Para cada símbolo a de An,k vamos a realizar el siguiente procedimiento:

1. Llamemos An-1,k al conjunto de todas las cadenas de tamaño (n-1) con exactamente k símbolos de A (o sea con todos los símbolos de A).

Para cada cadena α de An-1,k construimos una nueva cadena concatenandole a, nos queda así una nueva cadena: . Como α tiene tamaño (n-1), la nueva cadena tiene tamaño n.

Ademas por definición de An-1,k, α contiene a todos los símbolos de A, y en particular contiene a a. Entonces de esta manera hemos formado todas las cadenas de An,k que comienzan por a y tienen al menos 2 ocurrencias de a.

Nos queda todavía construir todas las cadenas de An,k que comienzan por a pero tienen solo una ocurrencia de a.

2. Llamemos An-1,k-1 al conjunto de todas las cadenas de tamaño (n-1) que están formadas por todos los símbolos de A menos a.

Para cada cadena β de An-1,k-1 construimos una nueva cadena . Se cumple entonces que tiene tamaño n y ademas dado que β contiene a todos los símbolos de A menos a a y le hemos concatenado a, contiene los k símbolos de A.

A partir de estos dos pasos hemos construido todas las cadenas de An,k que comienzan con a. Como por definición de An,k, cualquier cadena de An,k necesariamente tiene que comenzar con un símbolo de A y a es un elemento arbitrario podemos aplicar el procedimiento para construir todas las cadenas del conjunto An,k.

Como por hipótesis, |An-1,k-1| = f(n-1,k-1), |An-1,k| = f(n-1,k) y como existen exactamente k símbolos de A se cumple que f(n, k) = k( f(n-1,k) + f(n-1, k-1) ).

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Asumiendo que la función anterior es correcta, podemos proponer la siguiente función:


g

(
n
,
m
,
k
)

=

(

m
k

)

×
f

(
n
,
m
)


Llamemos Am al conjunto de todos los subconjuntos de A con exactamente m elementos. Es conocido que la cantidad de subconjuntos de tamaño m de un conjunto se puede calcular como:


|

A
m

|
=

(

m
k

)


(Ver Combination) . Sabemos ademas por el resultado anterior que la cantidad de cadenas de tamaño n que pueden hacerse de un conjunto de tamaño m es igual a f(n,m), a partir de lo cual derivamos la formula.

Autor: Emiliano Martínez Luque.

Comments Off on Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Recuento: Permutaciones y Selecciones ( Formulas básicas)

Icono de Post August 26 2009 :: Apuntes, Combinatoria ::

Principios Básicos

Principio de Multiplicación (Regla del producto)

Sean A1,A2,…, An conjuntos finitos, entonces |A1 x A2 x … x An| = |A1| . |A2|  ….  . |An|

Ej:
Tomemos 2 conjuntos:
A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ; | A | = 10
B = { a, b, c, d, e, f } ; | B | = 5

Supongamos que quiero saber todos las posibles conjuntos formados por 1 elemento de A y otro de B, por ej: { 3, b }, { a, 2 }.

O visto desde lenguajes formales cual es la cantidad de posibles cadenas formadas por primero un elemento de A y después un elemento de B, Ej: “3b”, “2a”, “9c”, “3c".

Existen 10 elementos en A y 5 en B por lo que la solución es: | A | x | B |  = 50

Principio de Adición (Regla de la Suma)

Sean A1,A2,…, An conjuntos finitos y disjuntos, entonces |A1 ∪ A2 ∪ … ∪ An| = |A1| + |A2| +  ….  + |An|

Ej:

Supongamos que tengo que elegir un elemento de A o de B (del ejemplo anterior). Como |A| = 10 y |B| = 5 y A ∩ B = ∅ entonces |A ∪ B| = 15, o sea que existen 15 posibles elementos que puedo elegir.

Principio de Exclusión y Exclusión

Si A1, A2 son conjuntos finitos pero no disjuntos. Entonces |A ∪ B| = |A| + |B| – |A ∩ B|
Esto se generaliza para la unión de varios conjuntos.

Permutaciones

Permutaciones

Supongamos que quiero calcular la cardinalidad del conjunto G formado por las cadenas de 3 caracteres formadas por elementos de C= {n, m, p} tales que no se repita nunca ningún elemento: { “nmp”, “npm”, “mnp”, “mpn”, “pmn”, “pnm” }.
Por el principio de multiplicación, Existen 3 posibilidades para el primero, luego como no se repiten 2 para el segundo y 1 para el tercero.
| G | = 3! = 6

La forma de poner n objetos en ordén es: P(n, n) = n!

R-Permutaciones

Supongamos ahora que quiero saber la cardinalidad del conjunto H formado por todas las cadenas de 3 carácteres formadas por elementos de A= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } sin que se repita nunca ningún elemento. Hay 10 posibilidades para el primer espacio, 9 para el segundo y 8 para el tercero, por lo que:

| H | = 10!7!

El número de permutaciones de r objetos de n en ordén pero sin repetición es: P(n, r) = n!(nr!)

Permutaciones con repetición

Supongamos que quiero saber la cardinalidad del conjunto formado por todas las cadenas de 3 caracteres formadas por elementos de A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } en las que se puedan repetir los elementos. Por la regla del producto existen 10 posibilidades para el primer carácter, 10 para el segundo y 10 para el tercero, por lo que el resultado es 103.

El número de permutaciones de r objetos de n en ordén con repetición es: nr

Selecciones

r-combinaciones

Una r-combinación de elementos de un conjunto es una selección sin ordenar de r elementos del conjunto, es decir, de subconjuntos de r elementos.

El número de r-combinaciones de n elementos, donde n es un entero no negativo y r es un entero tal que 0 <= r <= n es: C(n, r) = (nr)=n!r! . (nr)!
Ej:

Supongamos que quiero calcular la cardinalidad del conjunto J formado por todos los posibles subconjuntos de 2 elementos que contienen elementos de D = {w, x, y, z},  C(4,2) = 6, ya que J = { {w, x}, {w,y} , {w,z}, {x, y}, {x, z}, {y, z}}.

Relación entre r-permutaciones y r-combinaciones

Las r-permutaciones de un conjunto de cardinalidad n se pueden obtener formando las C(n,r) r-combinaciones del conjunto ( o sea todas los posibles subconjuntos de tamaño r formados por los n elementos del conjunto ) y luego ordenando estos elementos de todas las formas posibles, como cada subconjunto tiene tamaño r esto puede hacerse de P(r, r) formas de lo que sigue que:

P(n, r) = C(n, r) . P(r, r)

Selecciones con repetición

En un conjunto con n elementos hay C(n + r – 1, r) combinaciones con repetición.

Ej:

Supongamos que en un grupo de monedas hay 3 tipos distintos de 1, 5 y 10 centavos y hay por lo menos 5 de cada una de ellas. Cuantos posibles combinaciones de 5 monedas es posible extraer de este grupo?  Es importante recalcar que las monedas de cada valor son indistinguibles entre si  y no importa el orden en que se seleccionan las monedas, por lo que hay 5 combinaciones con repetición de 3 elementos.
Supongamos que cuando elejimos las monedas las metemos en una caja con 3 compartimentos, 1 para cada  tipo de moneda, entre cada compartimento hay una barra que las separa, de esta manera algunas de las posibles combinaciones podrian representarse como:
** | * | **
* | | ****
|*****|
***|*|*
…. etc.
Se ve que el numero de seleccionar 5 monedas de entre 3 tipos distintos corresponde al numero de formas de colocar 2 barras y 5 asteriscos. Por lo que el número de formas de seleccionar las monedas es equivalente al número de formas de seleccionar 5 asteriscos de entre 7 posiciones posibles, que se puede hacer de C(7, 5) maneras.

Equivalencias de Números Combinatorios

(00)=0!0! . 0! =1

( n 0 ) = n ! 0 ! . n ! = 1

( n 1 ) = n ! 1 ! . n ! = 1

( n n ) = n ! 0 ! . n ! = 1

Números combinatorios complentarios

( n k ) = n ! k ! . ( n k ) ! = n ! ( n k ) ! . k ! = ( n n k )

Permutaciones con Objetos Indistinguibles y Distribuciones de Objetos en Cajas

Ej 4.5.8 de MD
¿Cuantas permutaciones se pueden realizar con las letras de la palabra “PAPAYA¨? . No se puede usar la formula general de Permutaciones porque la letra “A” se repite 3 veces y la letra “P” se repite 2. Por lo que debe pensarse así: se pueden seleccionar las posiciones de las 3 letras “A” de C(6, 3) formas distintas, las “P” se pueden colocar en C(3,2) formas distinras quedando C(1, 1) para la “Y”. Por la regla del Producto queda:
C(6,3) . C(3, 2) . C(1,1) =   6 ! 3 ! . 3 ! . 3 ! 2 ! . 1 ! . 1 = 6 ! 3 ! . 2 !   = 60

El número de permutaciones diferentes de n objetos; donde hay n1objetos indistinguibles de tipo 1, n2 objetos indistinguibles de tipo 2, …, nk objetos indistinguibles de tipo k; es:
n ! n 1 ! . n 2 ! . n k !

Ej 4.5.9 de MD
¿De cuántas formas se pueden distribuir a cuatro jugadores manos de 5 cartas usando una baraja de 5 cartas? . Observese que al primero se le pueden distribuir C(52, 5), al segundo C(47, 5), al terceso C(42, 5) y al cuarto C(37, 5) (Quedando 32 cartas en el maso como una 5ta clase posible). Por la regla del producto queda:
C(52, 5) . C(47, 5) . C(42, 5) . C(37, 5) = 52 ! 47 ! . 5 ! . 47 ! 42 ! . 5 ! 42 ! 47 ! . 5 ! . 37 ! 32 ! . 5 ! =   52 ! 5 ! . 5 ! . 5 ! . 5 ! . 32 !

El número de formas de distribuir n objetos distinguibles en k cajas distinguibles de forma que en la caja i-ésima haya ni objetos, i = 1,2, …, k; es:
n ! n 1 ! . n 2 ! . n k !

Referencias

Matemática Discreta y sus aplicaciones; Rosen, Kenneth H.; 5ª edición, Mc Graw Hill, 2004

Algebra I; Rojo, Armando; 21ª ed, Magister Eos; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Recuento: Permutaciones y Selecciones ( Formulas básicas)

Razonando sobre corrección de Programas en Haskell

Icono de Post May 18 2009 :: Algoritmia, Combinatoria, Haskell, Lógica ::

Una de las cosas más interesantes de Haskell es lo facil que resulta razonar sobre corrección de programas. Veamos un ejemplo simple; construiremos una función que tome 3 elementos ordenables y los devuelva como una triada ordenada (Ejercicio 2.40 de Razonando con Haskell):


ordena3:: Ord a => a -> a -> a -> (a, a, a )
ordena3 a b c 	| a <= b && b <= c = (a, b, c) 		-- Caso 1
	 	| a <= b = ordena3 a c b		-- Caso 2
		| b <= c = ordena3 b a c		-- Caso 3
		| otherwise = (c, b, a)			-- Caso 4

Las posibles permutaciones de un conjunto de 3 elementos distintos son obviamente 3! = 2 * 3 = 6. Sean 3 elementos ordenables distintos, a los que llamamos 1, 2, 3 tales que 1 < 2 < 3, veamos como trata el programa estas 6 permutaciones distintas:

ordena3 1 2 3 Caso 1 -> (1 ,2 ,3)
ordena3 1 3 2 Caso 2 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 2 1 3 Caso 3 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 2 3 1 Caso 2 -> ordena3 2 ,1 ,3; Caso 3 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 3 1 2 Caso 3 -> ordena3 1 ,3 ,2; Caso 2 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 3 2 1 Caso 4 -> (1 ,2 ,3)

Las condiciones exhaustuan todos los caso y el algoritmo termina siempre. ( No se consideran los casos en que existen elementos duplicados en la explicación ya que es trivial ver que por el uso de <= en las condiciones están contemplados en la definición de la función. )

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Autor: Emiliano Martínez Luque.

Comments Off on Razonando sobre corrección de Programas en Haskell