COMBINACIONES

PERMUTACIONES

PERMUTACIONES

Una permutación es una combinación en donde el orden es importante. La notación para permutaciones es P(n ,r) que es la cantidad de permutaciones de “n” elementos si solamente se seleccionan “r”.

Para exhibir una permutación podemos escribir la lista correspondiente,

(2,7,5,1,...,6)                       (Permutación como lista)

o bien utilizar la siguiente notación:

 

(1234 ... n)

(2751 ... 6)                   (permutación como aplicación biyectiva)

Permutaciones con repetición

Permutaciones con repetición de n elementos en las que el primer elemento se repite n1 veces, el segundo se repite n2  veces, y el último se repite  nk veces son los distintos grupos de n elementos que se pueden hacer de forma que en cada grupo, cada elemento aparezca el número de veces indicado y que dos grupos se diferencian únicamente en el orden de colocación. Se representa por Pnn1,n2,...,nk

Ejemplos:

1.    En una urna hay 9 bolas, 3 blancas, 2 rojas y 4 negras. ¿De cuantas formas distintas se pueden extraer las bolas de la urna?

Al tener tres bolas blancas, a efectos de ordenación se consideran iguales, lo mismo ocurre con las rojas y las negras. 

Las posibles ordenaciones son: pr=  9! =       1260

                                                            3!2!4!

2.    En una competición deportiva participan 4 equipos de 3 atletas cada uno. ¿De cuántas formas diferentes pueden llegar los equipos?

A la hora de elaborar la clasificación por equipos los atletas se consideran idénticos.

El número de posibles clasificaciones es: pr=  12! =   369600

                                                                             3!3!3!3!

Permutaciones sin repetición

Permutaciones sin repetición o permutaciones ordinarias de n elementos (de orden n) son los distintos grupos de n elementos distintos que se pueden hacer, de forma que dos grupos se diferencian únicamente en el orden de colocación. Se representa por Pn.

Para construir las permutaciones sin repetición de un conjunto de n elementos, tenemos que construir grupos de n elementos sin que se puedan repetir. Se trata entonces de hacer lo mismo que se ha hecho con las variaciones sin repetición de orden n a partir de un conjunto de n elementos

De un elemento. A = {1}. Únicamente existe una permutación: 1.

De dos elementos. A = {1,2}. V2,2 = 2. Las dos permutaciones son: 12 y 21.

De tres elementos. A = {1,2,3}. V3,3 = 6. Las seis permutaciones son: 123 , 132 , 213 , 231 , 312 y 321.

De cuatro elementos. A = {1,2,3,4}. V4,4 = 24. Las veinticuatro permutaciones son: 1234 , 1243 , 1324 , 1342 , 1423 , 1432 , 2134 , 2143 , 2314 , 2341 , 2413 , 2431 , 3124 , 3142 , 3214 , 3241 , 3412 , 3421 , 4123 , 4132 , 4213 , 4231 , 4312 , 4321.

Ejemplos:

1.       ¿De cuántas formas se pueden sentar 5 personas en un coche?

Son permutaciones de 5 elementos.         P5=  5*4*3*2*1=120

                               

      

2. Ocho vecinas guardan cola en una panadería para comprar pan. ¿De cuántas formas distintas se pueden colocar en la cola?     P8= 8!= 40320

Permutaciones circulares

Es un caso particular de permutaciones ordinarias en las que en la ordenación no hay ni comienzo ni fin (los elementos están dispuestos en forma circular). Para contar las distintas agrupaciones lo que haremos será fijar uno de los elementos y permutar los demás. Si tenemos n elementos permutaremos n-1. p*n= (n-1)!

Ejemplo:

1.    ¿De cuántas formas distintas se pueden sentar 6 personas en una mesa circular?

Fijamos una persona y permutamos el resto            P6= 5! = 120

VIDEO SOBRE PERMUTACIONES

Grafos

        En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamadosvértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de unconjunto. Son objeto de estudio de la teoría de grafos.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representanterminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Un grafo es un par ordenado , donde:
es un conjunto de vértices o nodos, y
es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo a su número de vértices, .

El grado de un vértice o nodo es igual al número de arcos que lo tienen como extremo.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Grafo no dirigido:

Un grafo no dirigido o grafo propiamente dicho es un grafo donde:

es un conjunto de pares no ordenados de elementos de .

Un par no ordenado es un conjunto de la forma , de manera que . Para los grafos, estos conjuntos pertenecen al conjunto potencia de , denotado , y son de cardinalidad 2.

Arboles

Cuando se aprende o se enseña un nuevo concepto en el ámbito de las matemáticas, considero que ayuda mucho saber en donde se puede aplicar dicho concepto, por ejemplo, cuando aprendí el Teorema de Pitágoras, el cuadrado de la hipotenusa es igual a la suma del cuadrado de los catetos, se me grabó más cuando supe que lo podía usar para determinar la altura de un árbol o el ancho de un río.

De igual forma sucede con el concepto de árboles en Matemática Discreta, considero que si sabemos cuál es su aplicación vamos a entenderlo mejor.

Todos en algún momento nos hemos visto en la necesidad de buscar un archivo  en algún lugar de nuestra computadora ya sea porque no nos acordamos de la ubicación o simplemente porque queremos saber si está guardado allí; sin saberlo, hasta ahora, la forma en que el sistema operativo lo busca es usando la teoría de árboles, en este caso, árboles binarios.

 
Los hemos usado en gramática (árboles gramaticales), en adminsitración (árboles jerárquicos), en biología (árboles genealógicos), en cada libro o página web que leemos (árboles de contenido) y principalmente en los motores de búsquedas en internet (árboles binarios).

Árbol de contenidos - Libros, páginas Web

Árbol genealógico - Biología

Árbol Jerarquico - Administración

Árbol gramatical

Motores de búsqueda

En Estructura de Datos, se usan para organizar y relacionar datos de una base de datos. 

Bases de datos

 

 

Definiciones:

• Desde el punto de vista conceptual, un árbol es un caso particular de grafo, es un objeto que comienza con una raíz y se extiende en ramificaciones o lineas que terminan en un nodo.

• Representan la estructura no-lineal y dinámica de datos más importante en computación. Dinámica porque puede cambiar durante la ejecución de un programa y no-lineal porque a cada elemento del árbol pueden seguirle varios elementos.

• Es un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en un árbol. Una línea es un par de nodos ordenados, <u,v>, y a la secuencia de lineas se le llama ruta (path).

Propiedades:

• Tiene un nodo al que se le llama "nodo raíz" o raíz del árbol, éste no tiene "padre".
• Todos los nodos tienen una sola línea de entrada, excepto el nodo raíz, éste no tiene línea de entrada.
• Existe una "única" ruta del nodo raíz a todos los demás nodos del árbol.
• Si existe una ruta <a,b>, entonces "b" es el "hijo" de "a" y es el nodo raíz de un sub-árbol.
• Todos los nodos que son descendientes de un mismo nodo "padre", son "hermanos".
• Todo nodo que no tiene ramificaciones (hijos), es un nodo "terminal" u "hoja".
• Todo nodo que no es raíz ni terminal es un nodo "interior".
• "Grado" es el número de descendientes directos de un determinado nodo.
• "Grado del árbol" es el máximo grado de todos los nodos del árbol.
• "Nivel" es el número de ramificaciones que se deben recorrer para llegar a un determinado nodo. El nodo raíz tiene nivel 1.
• "Altura del árbol" es el máximo número  de niveles  de todos los nodos del árbol.

Representación:

Longitud de un árbol:

Es el número de arcos que deben ser recorridos desde la raíz hasta el nodo X.

Longitud de camino interno:

Es la suma de las longitudes de camino de todos los nodos del árbol.

 

en donde i = nivel del árbol, h = altura del árbol, ni = número de nodos en el nivel "i".