parte 5

CAMINOS Y CICLOS
Camino o trayectoria es el recorrido desde un V0 (vértice inicial) a Vn (vértice destino) de longitud n, es una sucesión alternante de n + 1 vértices y n aristas que comienza en elvértice V0 y termina en el Vn . Formalmente significa: comience en el vértice v0; recorra la arista e1 hasta v1; siga por la arista e2 hasta v2, y así sucesivamente. 
(v_0', e_1', v_1', e_2', v_2',…. v_{n - 1}, e_n, v_n) 
Donde la arista e_i es incidente sobre los vértices v_{i - 1} y v_i para i = 1, … n. 
Ejemplo: 

Construyamos un camino en G desde el vértice 1 hasta el vértice 2 de longitud4. 
Camino o trayectoria de G: (1, e_1, 2, e_2, 3, e_3, 4, e_4, 2) 
Además, el mismo camino se puede representar así: (1, 2, 3, 4, 2) 
En caso de que no se repita ningún vértice entonces recibe elnombre de camino simple, por ejemplo: (1, 2, 3,4) y (7, 6, 5,2) 
IMPORTANTE 
Sean v y w vértices en un grafo G. 
* Un camino simple o trayectoria de v a w es una ruta de v a w sin vérticesrepetidos. 
* Un ciclo (o circuito) es un camino de longitud diferente de cero de v a v sin aristas repetidas. 
* Un ciclo simple es un ciclo de v a v en el que no hay vértices repetidos, exceptopor el inicio y el fin que son iguales a v. 
Tomando como referencia la grafica anterior, vamos a determinar si tiene caminos simples, ciclo y ciclo simple.
conecxa 
una grafica es conexa si dados cualquiera dos vertices existe una trayectoria.

Representación de los grafos

 Representación por incidencia

Lista de incidencia

El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista.

 Matriz de incidencia

El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Representación por adyacencia

 Listas de adyacencia

El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.

 Matriz de adyacencia

Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V²)).

Representación Grafica

Un grafo se representa mediante un diagrama en el cual a cada vértice le corresponde un punto y si dos vértices son adyacentes se unen sus puntos

correspondientes mediante una línea, ejemplo:

ISOMORFISMO DE GRAFOS

Definición:
Dos grafos G₁ y G₂ son isomorfos si existe una función biyectiva f entre los vértices de G₁ y G₂, y una función biyectiva g entre lados de G₁ y G₂ tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G₂. Al par de funciones f y g se le denomina isomorfismo.

Ejemplo:
Sean los siguientes grafos G₁ y G₂ 

Un isomorfismo para los grafos anteriores G₁ y G₂ esta definido por:f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E

y g(X_i) = Y_i, i = 1, ... , 5

Los grafos G₁ y G₂ son isomorfos si y solo si para alguna ordenación de vértices y lados sus matrices de incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:

GRAFOS APLANABLES

Este tipo de grafos, además de aparecer con mucha frecuencia también cuentan con muchas propiedades interesante. Se analizarán algunas de las más importantes.

Definición:
Diremos que un grafo es aplanable si puede ser dibujado sobre un plano de tal manera tal que ninguna arista se cruce con otra excepto, desde luego, en los vértices comunes. El siguiente es un grafo aplanable:

el grafo i) también es aplanable ya que puede dibujarse como se muestra en el grafo ii)

Ejemplo:
La siguiente figura es un grafo no aplanable que a decir verdad corresponde al problema de determinar si es posible conectar las casas 1, 2, 3 a los servicios de Luz, Agua y Drenaje, de tal manera que no haya 2 líneas de conexión que se crucen una con la otra.

Definición:
Una región (o cara) de un grafo aplanable se define como una área del plano que está acotada por aristas y no pude continuar dividiéndose subáreas.

Ejemplo:
El siguiente grafo tiene 5 regiones que son:

Definición:
Diremos que una región es infinita si su área es infinita y se dice que es finita, si su área es finita. En un grafo aplanable se tienen exactamente una región infinita.

Tenemos el siguiente resultado:

v  e + r = 2

donde v, e y r son el numero de vértices, aristas y regiones respectivamente. Esta ecuación se conoce como la Formula de Euler para grafos aplanables. Sin excepción alguna todos los grafos aplanables conexos deben satisfacer la formula de Euler.

En cualquier grafo aplanable lineal conexo que no tenga lazos y que tenga 2 o mas aristas se cumple la siguiente desigualdad:

e  3v  6

Debido a que el grafo es lineal cada región es acotada por 3 o más aristas por lo tanto el número es mayor o igual que 3r. en la frontera a lo largo de 2 regiones, el numero total es igual o menor a 2e así tenemos:

2e  3r

ó

De acuerdo a la fórmula de Euler, tenemos que:

ó

3v - 6  e

Es evidente que la planaridad de un grafo no se ve afectada si una arista es dividida en dos arista por la inserción de un vértice de grado 2 como i) o si 2 aristas se combinan en una sola arista al eliminar este vértice como en ii) 

i)	ii)

Definición: 
Dos grafos G₁ y G₂ son isomorfos bajo vértices de grado 2, si son isomorfos ó si pueden transformarse en grafos isomorfos mediante repeticiones de inserciones y/o eliminaciones de vértices de grado 2 como en i) y i i).

Ejemplo:
Los siguientes grafos son isomorfos bajo vértices de grado 2.

Teorema de Kuratoswki 
Un grafo es aplanable si y solo si no contiene cualquier subgrafo que sea isomorfo bajo vértices de grado 2 a cualquier de los siguientes grafos, que son llamados de Kuratowski

 Árboles

Un grafo conectado que contiene circuitos no simples se llama árbol. En el año de 1857 Arthur Cayley, matemático inglés, los empleó para contabilizar componente químicos, no obstante, es importante señalar que no solo es una herramienta de la química sino que se han utilizado en diversas áreas, por ejemplo, conforme el propio interés de la materia encaminado hacia las ciencias de la computación, se utiliza para la construcción de las redes.  Propiedades de los árboles Entre las propiedades más importantes de los árboles está la presencia de un paseo entre cualquiera de dos vértices del árbol; segundo, que el número de vértices no es menor al número de aristas del árbol y que un árbol con más de dos vértices tiene por lo menos dos hojas. Un ejemplo claro de los árboles en la vida cotidiana son los árboles genealógicos. Para este caso, los vértices representan a los miembros de la familia y los arcos representan la relación de parentesco. Conforme los conocimientos adquiridos con anterioridad, el árbol no deja de ser un grafo, pero es del tipo no dirigido. Ejemplo de árbol genealógico: En este ejemplo cabe señalar que los recuadros representan los vértices del grafo y los arcos son las líneas que representan las relaciones de parentesco conforme a esta familia:  Representación de árboles El árbol es un grafo no dirigido conectado con circuitos no simples; además, no contiene arcos múltiples, con la propiedad de que hay un único camino simple entre cada par de vértices, teniendo el siguiente teorema: Teorema 1. “Un grafo no dirigido es un árbol si y solo si hay un camino simple único entre cualesquiera dos de sus vértices”. Conforme los siguientes grafos, ¿cuál de ellos es del tipo de árboles? Ejemplo: ¿Cuáles de los grafos de la figura 6.2  son árboles? Fig. 6.2 Grafo 1,2 y 3 Si se observan los siguientes grafos, se concluye que el grafo G1 no es un árbol porque se observa un circuito simple, pero los grafos G2 Y G3  son de árboles, porque están conectados con circuitos no simples. Como se sabe, existen grafos que no tienen conexión y podría existir confusión el pensar que un árbol es un grafo conectado que tiene circuitos no simples, pero es importante mencionar que existen árboles del tipo que contienen circuitos no simples que no necesariamente están conectados, y esos árboles reciben el nombre de bosques, cuya característica es que cada uno de sus componentes conectados es un árbol.             Los árboles son mostrados a continuación: En gran parte de las aplicaciones de árboles, se designa a un vértice particular del árbol como laraíz, por lo que se pude asignar una dirección a cada arco, debido que hay un camino único de la raíz a cada vértice del grafo dirigiéndose cada arco alejándose de la raíz, conforme lo enunciado en el teorema 1, en el apartado 6.1.2, por lo tanto es un grafo de árbol con raíz, esto es simplemente el árbol que junto con su raíz forman un grafo y en caso que fuesen diferentes s vértices como raíz, se producen diferentes árboles con raíz. A continuación se muestra un grafo de árbol con raíz: De acuerdo a lo anterior se muestran los árboles con raíz en donde a y c son las raíces correspondientes del grafo R. Lo usual es elaborar un grafo de árbol con raíz en la parte superior del grafo, en donde las flechas muestran la dirección de los arcos, como se muestra en la siguiente figura: En el apartado 6.1.1 se elaboró un árbol genealógico con el propósito de familiarizarse con la terminología, que es de origen genealógico y botánico.  Observe el siguiente grafo: En esta figura se deduce que E es un árbol con raíz a, se observa que los padres son b, c y d y, a su vez, don hermanos, f y g son hijos de b; además, e es hijo de c. Otro ejemplo: si se supone que A es un árbol con raíz, si v es un vértice en A diferente de la raíz, el padre de v es el único vértice u tal que hay un arco dirigido de u a v. Cuando u es el padre de v, v es llamado un hijo de u. Los vértices con el mismo padre son llamados hermanos. Los ancestrosde un vértice diferente de la raíz son los vértices en el grafo de la raíz a ese vértice, excluyendo el vértice mismo e incluyendo a la raíz. Los descendientes de un vértice v son aquellos vértices que tienen a v como ancestro. Un vértice de un árbol es llamado hoja si no tiene hijos. Los vértices que tienen hijos son llamados vértices internos. La raíz es un vértice interno a menos que sea el único vértice del grafo, en ese caso es una hoja. Si a es un vértice en un árbol, el subárbol con a como raíz, es el subgrafo del árbol que consiste de a y sus descendientes y todos los arcos incidentes en estos descendientes.   Observa la siguiente figura: En este árbol Z, la raíz está en el vértice a; el padre de c es b y su descendencia es b y e; los hermanos de i son h y j, quienes son hijos de g; además, se pueden observar todos los ancestros de m; y también se observa que en este árbol con raíz existe otro subárbol con raíz en el vértice g, si se hace un acercamiento en esta parte se percibe lo siguiente: El padre es g, los hijos son h,i,j y los descendentes de j son i e m, y el descendente de h es k. También existe un árbol con raíz, de nombre m-ario, que consiste en que cada vértice interno no tiene más de m hijos, y  el árbol m-ario completo consiste si cada vértice tiene exactamente m hijos y  un árbol m-ario con cuando m=2 es llamado árbol binario. Conforme lo visto anteriormente se distinguirán los diferentes tipos de grafos: Este grafo representa un árbol binario completo porque cada uno de sus vértices internos tiene un hijo. En esta figura se representa un árbol, árbol 3-ario, completo porque cada uno de sus vértices internos tiene tres hijos. Este es un árbol 5-ario completo porque cada vértice interno tiene 5 hijos. Este grafo representa un árbol m-ario completo para alguna m, porque algunos de sus vértices internos tienen dos hijos y otros tienen tres hijos. También existe el caso de un árbol con raíz ordenado debido que los hijos de cada vértice interno están ordenados, y estos se expresan en el grafo de tal forma que los hijos de cada vértice interno se representan en orden de izquierda a derecha. Si el árbol con raíz ordenado tiene un vértice interno del cual emanan dos hijos, el primero se nombra hijo izquierdo y el segundo es llamadohijo derecho

parte 4

PERMUTACIONES Y COMBINACIONES GENERALIZADAS:

Supóngase que una sucesión S de n objetos tien n₁ objetos idénticos del tipo 1, n₂ objetos idénticos del tipo 2, . . . , n_t objetos idénticos del tipo t. Entonces el número de ordenaciones de S es:

Demostración:
Se asignan las posiciones de cada uno de los n objetos para crear un orden de S. Es posible asignar las posiciones de los n1 objetos del tipo 1 en C(n, n₁) formas. Una vbez realizada estas asignación, pueden asignarse las posiciones de los n₂ objetos del tipo 2 en C(n - n₁, n₂) maneras, etc. Por lo tanto

coeficientes binomial 

Los coeficientes binomiales, números combinatorios o combinaciones son números estudiados en combinatoria que corresponden al número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado. Sin embargo, dependiendo del enfoque que tenga la exposición, se pueden usar otras definiciones equivalentes.

Ejemplo:

Se tiene un  con 6 objetos diferentes {A,B,C,D,E,F}, de los cuales se desea escoger 2 (sin importar el orden de elección). Existen 15 formas de efectuar tal elección:

A,B	A,C	A,D	A,E	A,F
	B,C	B,D	B,E	B,F
		C,D	C,E	C,F
			D,E	D,F
				E,F

El número de formas de escoger k elementos a partir de un conjunto de n, puede denotarse de varias formas C(n,k), n,Ck. Así, en el ejemplo anterior se tiene entonces que C(6,2)=15, puesto que hay 15 formas de escoger 2 objetos a partir de un conjunto con 6 elementos.

Los números C(n,k) se conocen como «coeficientes binomiales», pero es frecuente referirse a ellos como «combinaciones de n en k», o simplemente «n en k». Por tanto, la primera definición es:

El coeficiente binomial  es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

Es importante notar que la definición asume implícitamente que n y k son naturales, y que además k no excede a n. Podemos definir C(n,k)=0 si k>n, puesto que no es posible escoger más elementos que los que tiene el conjunto dado (por tanto hay cero formas de hacer la elección). Estas precisiones cobrarán relevancia más adelante cuando se discutan generalizaciones del concepto (por ejemplo, cuando n o k sean negativos o cuando no sean números enteros).

Aplicación al análisis de algoritmos

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En lo que sigue nos centraremos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.
Para cada problema determinaremos un medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N. El concepto exacto que mide N depende de la naturaleza del problema. Así, para un vector se suele utizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importante considerar el número de arcos, dependiendo del tipo de problema a resolver); en un fichero se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste.

Tipos de ejecucion
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como

  S1; for (int i= 0; i < N; i++) S2;

requiere

  T(N)= t1 + t2*N

siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la serie "S2".
Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que mas que un valor T(N) debamos hablar de un rango de valores

  Tmin(N)  <=  T(N)  <=  Tmax(N)

los extremos son habitualmente conocidos como "caso peor" y "caso mejor". Entre ambos se hallara algun "caso promedio" o más frecuente.
Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes "Ti" que dependen de factores externos al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta. Dado que es fácil cambiar de compilador y que la potencia de los ordenadores crece a un ritmo vertiginoso (en la actualidad, se duplica anualmente), intentaremos analizar los algoritmos con algun nivel de independencia de estos factores; es decir, buscaremos estimaciones generales ampliamente válidas.

Grafos

De esta manera podemos dejar patente que aquel emana de la palabra griega grafo, graphein, que puede traducirse como “grabar o escribir”.

Este hecho es el que determina, por ejemplo, que hoy día utilicemos dicho concepto como parte indisoluble de otros términos a los que les da ese citado significado que está relacionado con la escritura. Este sería el ejemplo de bolígrafo que es un instrumento que utilizamos para escribir, grafólogo que es aquella persona que se dedica a determinar las cualidades psicológicas de alguien a través de la escritura que realiza, o el polígrafo que es quien se encarga de estudiar diversas formas de escribir que se llevan a cabo de forma secreta.

En la lingüística, un grafo es un objeto unitario de naturaleza abstracta que abarca a las grafias que componen una letra. La palabra tiene origen griego y significa “imagen” o “dibujo”.

Los grafos pueden ser clasificarse de diversas maneras según sus características. Los grafos simples, en este sentido, son aquellos que surgen cuando una única arista logra unir dos vértices. Los grafos complejos, en cambio, presentan más de una arista en unión con los vértices.

Por otra parte, un grafo es conexo si dispone de dos vértices conectados a través de un camino. ¿Qué quiere decir esto? Que, para el par de vértices (p, r), tiene que existir algún camino que permita llegar desde p hasta r.

En cambio, un grafo es fuertemente conexo si el par de vértices tiene conexión a través de, como mínimo, dos caminos diferentes.

Un grafo simple, además, puede ser completo si las aristas están en condiciones de unir todos los pares de vértices, mientras que un grafo es bipartito si sus vértices surgen por la unión de un par de conjuntos de vértices y si se cumple una serie de condiciones.

parte 3

Relación                                             

Dados dos conjuntos A y B una relación es un subconjunto del producto cartesiano A x B.

Un elemento a, que pertenece al conjunto A, está relacionado con un elemento b, que pertenece al conjunto B, si el par (a, b) pertenece a un subconjunto G (llamado grafo) del producto cartesiano A x B.

Ejemplo: Sean A = {a, b, c} y B = {1, 2} dos conjuntos. El producto cartesiano A x B = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}. Una relación sería R = {(a,1),(c,2)}.

A las relaciones también se les llama correspondencias.

Producto cartesiano

Considere dos conjuntos arbitrarios A y B. El conjunto de todas las parejas ordenadas (a, b) en donde a ∈ A  y b ∈B se llama producto o producto cartesiano de A y B.

La definición de producto cartesiano puede extenderse fácilmente al caso de más de dos conjuntos.

Se llama producto cartesiano de dos conjuntos A y B y se representa  A x B, al conjunto de pares ordenados (a, b), tales que el primer elemento pertenece al primer conjunto y el segundo elemento al segundo conjunto. Es decir:

A x B = {(a, b) / a ∈ A, b ∈ B} El producto cartesiano, en general, no es conmutativo. Es decir: A x B ≠ B x A.

Puede ocurrir que los conjuntos A y B sean coincidentes.

EJEMPLO:

Si A = {a, b, c} y B = {1, 2, 3, 4}, el producto cartesiano es:

A x B = {(a, 1), (a, 2), (a, 3), (a, 4), (b, 1), (b, 2), (b, 3), (b, 4), (c, 1), (c, 2), (c, 3), (c, 4)} 

Se puede representar gráficamente por medio  de puntos en un plano, como se muestra a continuación. Aquí, cada punto  P representa una pareja ordenada (a,  b) de números reales y viceversa; la línea vertical a través de P encuentra al eje x en a, y la línea horizontal a través de P encuentra el eje y en b. 

A esta representación se le conoce como diagrama cartesiano. 

Hay otra manera de visualizar una relación y es a través de una representación gráfica, donde se destaquen los puntos en el plano que pertenecen a A y los puntos que pertenecen a B. Se trazan flechas que indican la relación que existe entre cada elemento del conjunto  A y su correspondiente en el conjunto B. A esta representación gráfica se le conoce como un diagrama de flechas.

Técnicas de Conteo.

Las técnicas de conteo son aquellas que son usadas para enumerar eventos difíciles de cuantificar.

Estas técnicas de conteo tienen como objetivo las combinaciones, estas se forman a través de 2 condiciones: con repetición y sin repetición, se pueden visualizar en forma de árboles,grupos y matriz (arreglo).

Empezaremos por explicar en que consiste el teorema fundamental de la multiplicación y de la adición..

Teorema Fundamental de la multiplicación: Si una combinación se quiere establecer de "n formas" y cada una de ellas se puede llevar a cabo de "m maneras distintas" en una segunda operación. Entonces se dice que juntas las operaciones pueden realizarse:nxm.

Ejemplo:

Se desea conocer el número de placas que se pueden formar si estas tienen 2 dígitos y 3 letras mayúsculas. Establecer de cuantas maneras se pueden formar sin repetición y con repetición.

Datos         Dígitos (D) = 10

Letras mayúsculas (L)=27

Desarrollo
a)con repetición  DDLLL =   10X10X27X27X27 = 1,968,300  maneras.  b)sin repetición* DDLLL=10x9x27x26x25=1,579,500 maneras.

Teorema Fundamental de la Adición: Si un evento se puede llevar a cabo de "n o m lugares distintos", además de no ser posible que se lleve a cabo el mismo evento o dos lugares distinto al mismo tiempo. Entonces el evento se puede realizar: n+m formas diferentes.
Ejemplo
Supóngase que se desea etiquetar las gavetas de los alumnos de la primaria, y que la etiqueta puede estar marcada con un solo digito, una sola letra o la combinación de una sola letra con un solo digito (sin importar si primero se pone la letra y después el digito o al contrario. *Bajo estas condiciones , el numero de etiquetas distintas que se pueden formar son:
Datos
D=10
L=27
Desarrollo
Etiquetas= D+L+D*L+L*D al sustituir queda:
Etiquetas=10+27+10*27+27*10
Etiquetas=577

permutaciones y combinaciones

Permutaciones

Hay dos tipos de permutaciones:

1. Se permite repetir: como la cerradura de arriba, podría ser "333".
2. Sin repetición: por ejemplo los tres primeros en una carrera. No puedes quedar primero y segundo a la vez.

1. Permutaciones con repetición

Son las más fáciles de calcular. Si tienes n cosas para elegir y eliges r de ellas, las permutaciones posibles son:

n × n × ... (r veces) = n^r

(Porque hay n posibilidades para la primera elección, DESPUÉS hay n posibilidades para la segunda elección, y así.)

Por ejemplo en la cerradura de arriba, hay 10 números para elegir (0,1,...,9) y eliges 3 de ellos:

10 × 10 × ... (3 veces) = 10³ = 1000 permutaciones

Así que la fórmula es simplemente:

nr

donde n es el número de cosas que puedes elegir, y eliges r de ellas (Se puede repetir, el orden importa)

2. Permutaciones sin repetición

En este caso, se reduce el número de opciones en cada paso.

Por ejemplo, ¿cómo podrías ordenar 16 bolas de billar? Después de elegir por ejemplo la "14" no puedes elegirla otra vez.

Así que tu primera elección tiene 16 posibilidades, y tu siguiente elección tiene 15 posibilidades, después 14, 13, etc. Y el total de permutaciones sería:

16 × 15 × 14 × 13 ... = 20,922,789,888,000

Pero a lo mejor no quieres elegirlas todas, sólo 3 de ellas, así que sería solamente:

16 × 15 × 14 = 3360

Es decir, hay 3,360 maneras diferentes de elegir 3 bolas de billar de entre 16.

¿Pero cómo lo escribimos matemáticamente? Respuesta: usamos la "función factorial"

	La función factorial (símbolo: !) significa que se multiplican números descendentes. Ejemplos: 4! = 4 × 3 × 2 × 1 = 24 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 1! = 1
Nota: en general se está de acuerdo en que 0! = 1. Puede que parezca curioso que no multiplicar ningún número dé 1, pero ayuda a simplificar muchas ecuaciones.

Así que si quieres elegir todas las bolas de billar las permutaciones serían:

16! = 20,922,789,888,000

Pero si sólo quieres elegir 3, tienes que dejar de multiplicar después de 14. ¿Cómo lo escribimos? Hay un buen truco... dividimos entre 13!...

16 × 15 × 14 × 13 × 12 ...		= 16 × 15 × 14 = 3360
13 × 12 ...

¿Lo ves? 16! / 13! = 16 × 15 × 14

La fórmula se escribe:

donde n es el número de cosas que puedes elegir, y eliges r de ellas (No se puede repetir, el orden importa)

Ejemplos:

Nuestro "ejemplo de elegir en orden 3 bolas de 16" sería:

16!	=	16!	=	20,922,789,888,000	= 3360
(16-3)!		13!		6,227,020,800

¿De cuántas maneras se pueden dar primer y segundo premio entre 10 personas?

10!	=	10!	=	3,628,800	= 90
(10-2)!		8!		40,320

(que es lo mismo que: 10 × 9 = 90)

Combinaciones

También hay dos tipos de combinaciones (recuerda que ahora el orden no importa):

1. Se puede repetir: como monedas en tu bolsillo (5,5,5,10,10)
2. Sin repetición: como números de lotería (2,14,15,27,30,33)

1. Combinaciones sin repetición

Así funciona la lotería. Los números se eligen de uno en uno, y si tienes los números de la suerte (da igual el orden) ¡entonces has ganado!

La manera más fácil de explicarlo es:

• imaginemos que el orden sí importa (permutaciones),
• después lo cambiamos para que el orden no importe.

Volviendo a las bolas de billar, digamos que queremos saber qué 3 bolas se eligieron, no el orden.

Ya sabemos que 3 de 16 dan 3360 permutaciones.

Pero muchas de ellas son iguales para nosotros, porque no nos importa el orden.

Por ejemplo, digamos que se tomaron las bolas 1, 2 y 3. Las posibilidades son:

El orden importa	El orden no importa
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1	1 2 3

Así que las permutaciones son 6 veces más posibilidades.

De hecho hay una manera fácil de saber de cuántas maneras "1 2 3" se pueden ordenar, y ya la sabemos. La respuesta es:

3! = 3 × 2 × 1 = 6

(Otro ejemplo: 4 cosas se pueden ordenar de 4! = 4 × 3 × 2 × 1 = 24 maneras distintas, ¡prueba tú mismo!)

Así que sólo tenemos que ajustar nuestra fórmula de permutaciones para reducir por las maneras de ordenar los objetos elegidos (porque no nos interesa ordenarlos):

Esta fórmula es tan importante que normalmente se la escribe con grandes paréntesis, así:

donde n es el número de cosas que puedes elegir, y eliges r de ellas (No se puede repetir, el orden no importa)

Y se la llama "coeficiente binomial".

Notación

Además de los "grandes paréntesis", la gente también usa estas notaciones:

Ejemplo

Entonces, nuestro ejemplo de bolas de billar (ahora sin orden) es:

16!	=	16!	=	20,922,789,888,000	= 560
3!(16-3)!		3!×13!		6×6,227,020,800

O lo puedes hacer así:

16×15×14	=	3360	= 560
3×2×1		6

Así que recuerda, haz las permutaciones, después reduce entre "r!"

... o mejor todavía...

¡Recuerda la fórmula!

Es interesante darse cuenta de que la fórmula es bonita y simétrica:

Con otras palabras, elegir 3 bolas de 16 da las mismas combinaciones que elegir 13 bolas de 16.

16!	=	16!	=	16!	= 560
3!(16-3)!		13!(16-13)!		3!×13!

. Combinaciones con repetición

OK, ahora vamos con este...

Digamos que tenemos cinco sabores de helado: banana, chocolate, limón, fresa y vainilla. Puedes tomar 3 paladas. ¿Cuántas variaciones hay? Vamos a usar letras para los sabores: {b, c, l, f, v}. Algunos ejemplos son {c, c, c} (3 de chocolate) {b, l, v} (uno de banana, uno de limón y uno de vainilla) {b, v, v} (uno de banana, dos de vainilla)

(Y para dejarlo claro: hay n=5 cosas para elegir, y eliges r=3 de ellas.
El orden no importa, ¡y sí puedes repetir!)

Bien, no puedo decirte directamente cómo se calcula, pero te voy a enseñar una técnica especial para que lo averigües tú mismo.

	Imagina que el helado está en contenedores, podrías decir "sáltate el primero, después 3 paladas, después sáltate los 3 contenedores siguientes" ¡y acabarás con 3 paladas de chocolate!
	Entonces es como si ordenaras a un robot que te trajera helado, pero no cambia nada, tendrás lo que quieres.

Ahora puedes escribirlo como  (la flecha es saltar, el círculo es tomar)

Entonces los tres ejemplos de arriba se pueden escribir así:

{c, c, c} (3 de chocolate):
{b, l, v} (uno de banana, uno de limón y uno de vainilla):
{b, v, v} (uno de banana, dos de vainilla):

OK, entonces ya no nos tenemos que preocupar por diferentes sabores, ahora tenemos un problema más simple para resolver: "de cuántas maneras puedes ordenar flechas y círculos"

Fíjate en que siempre hay 3 círculos (3 paladas de helado) y 4 flechas (tenemos que movernos 4 veces para ir del contenedor 1º al 5º).

Así que (en general) hay r + (n-1) posiciones, y queremos que r de ellas tengan círculos.

Esto es como decir "tenemos r + (n-1) bolas de billar y queremos elegir r de ellas". Es decir, es como el problema de elegir bolas de billar, pero con números un poco distintos. Lo podrías escribir así:

donde n es el número de cosas que puedes elegir, y eliges r de ellas (Se puede repetir, el orden no importa)

Es interesante pensar que podríamos habernos fijado en flechas en vez de círculos, y entonces habríamos dicho "tenemos r + (n-1) posiciones y queremos que (n-1) tengan flechas", y la respuesta sería la misma...

¿Qué pasa con nuestro ejemplo, cuál es la respuesta?

(5+3-1)!	=	7!	=	5040	= 35
3!(5-1)!		3!×4!		6×24