Programacion numerica unidad 1

Números de Stirling.

Primera Clase.
Dado el grupo de permutaciones Sn sobre un conjunto de n elementos, se podría plantear la cuestión de cuántas permutaciones se pueden descomponer exactamente en k ciclos. A este número S1(n,k) así definido lo llamaremos Número de Stirling de primera clase.
Por ejemplo, el número S1(4,3) = 6 significa que hay seis permutaciones de 4 elementos (por ejemplo.en el conjunto 1234) que se pueden descomponer en 3 ciclos. Serían estas: (1)(2)(34), (1)(3)(24), (1)(4)(23), (2)(3)(14), (2)(4)(13) y (3)(4)(12).
Se puede definir S1(n,0) con n>0 como 0, y aceptaremos que S1(0,0)=1 y que S1(0,n)=0.
Es claro que se cumple que S1(n,n)=1 pues sólo obtendríamos la permutación identidad, y es fácil demostrar que S1(n,1)=(n-1)!

Segunda Clase.
Es interesantepreguntarse cuántas particiones distintas de k conjuntos se pueden definir en un conjunto de n elementos. El resultado se denomina como “número de Stirling de segunda clase” y lo representaremos por S2(n,k). Así, el número S2(5,4) representará el número de particiones distintas en cuatro conjuntos disjuntos que se pueden definir en un conjunto de 5 elementos. Por ejemplo, en el conjunto {1,2,3,4,5} sepueden definir estas particiones de 4:
{1}{2}{3}{45}, {1}{2}{4}{35}, {1}{2}{5}{34}, {1}{3}{4}{25}, {1}{3}{5}{24}, {1}{4}{5}{23}, {2}{3}{4}{15}, {2}{3}{5}{14}, {2}{4}{5}{13}, {3}{4}{5}{12}. En total 10, como se puede comprobar en la tabla de abajo.
Es claro que S2(n,0)=0 y que S2(n,1)=S2(n,n)=1 porque sólo hay una forma de partir un conjunto de n elementos en conjuntos de n elementos (élmismo) y también una sola forma de partirlo en n subconjuntos (los de un solo elemento).
La propiedad que permite generar estos números es:
S2(n,r) = r*S1(n-1,r)+S1(n-1,r-1)

http://hojamat.es/sindecimales/combinatoria/teoria/teorcomb.htm
http://www.multilingualarchive.com/ma/enwiki/es/Stirling_number
http://www.buenastareas.com/ensayos/Numeros-Stirling/1589873.html





Conclusión.
LosNúmeros de Stirling, son una serie que se utiliza para identificar el número de permutaciones o de combinaciones de un número de acuerdo a un número k.








El Problema de Josephus.
El problema de Flavio Josephus es un problema teórico que se encuentra en matemática y ciencias de la computación. Según lo que cuenta Josephus, él y 40 soldados camaradas se encontraban atrapados en unacueva, rodeados de romanos. Prefirieron suicidarse antes que ser capturados y decidieron que echarían a suertes quién mataba a quién. Los últimos que quedaron fueron él y otro hombre. Entonces convenció al otro hombre que debían entregarse a los romanos en lugar de matarse entre ellos.

El problema plantea lo siguiente:
Hay n personas paradas en un círculo esperando a ser ejecutadas. Después deque ejecutan a la primera persona, saltean a k − 1 personas y la persona número k es ejecutada. Entonces nuevamente, saltean a k − 1 personas y la persona número k es ejecutada. La eliminación continúa alrededor del círculo (que se hace cada vez más pequeño a medida que más personas son eliminadas del mismo) hasta que sólo queda la última, que es liberada.
El objetivo es escoger el lugar inicialen el círculo para sobrevivir (es el último que queda),
dados n y k.


http://es.wikipedia.org/wiki/Problema_de_Flavio_Josefo
http://descartes.cnice.mec.es/materiales_didacticos/problema_josephus/ProblJosephus.htm
http://www.multilingualarchive.com/ma/enwiki/es/Josephus_problem





Conclusión.
Este problema, fue de gran ayuda para Josephus y su amigo, ya que gracias a él, lograronsalir vivos de la cueva y entregarse a los romanos. Es un problema recursivo, ya que se sigue un ciclo para ir eliminando a las personas.

















Algoritmo de Josephus
1. Inicio
2. Dame el número de personas que se encuentran en el circulo
3. Escanea, i
4. T1(i)= 1 hasta i
5. Pos=1
6. K=2
7. For (i)
Elimina de T1(i) pos+K
Pos= pos+K
K=3
Si solo quedan...