Apuntes de Combinatoria: Técnicas de Conteo y Aplicaciones en Matemáticas

Introducción a la Combinatoria

Justificación de la Elección del Tema

El presente tema se caracteriza por ser coherente e innovador ya que parte del primer nivel de concreción curricular que son las bases legales que regulan nuestro sistema educativo, como la Ley Orgánica 3/2020 (LOMLOE), de 29 de diciembre, por la que se modifica la Ley Orgánica 2/2006, de 3 de mayo de educación (LOE), la Ley de Educación en Andalucía 17/2007 de 17 de diciembre (LEA), y fundamental e imprescindible la Orden del 30 de mayo de 2023. Las matemáticas, presentes en casi cualquier actividad humana, tienen un marcado carácter instrumental que las vincula con la mayoría de las áreas de conocimiento: las ciencias de la naturaleza, la ingeniería, la tecnología e incluso el arte o la música. En particular, la combinatoria es uno de estos instrumentos matemáticos, ya que nos proporcionará herramientas para responder a preguntas como: ¿ De cuántas formas podemos realizar la tarea que nos proponemos?

Reseña Histórica de la Combinatoria

Los problemas de enumeración y combinatoria han interesado al ser humano desde la antigüedad. En el libro ``Ching' ' (2300 a.C) ya aparecen algunos problemas relacionados con estos temas. El término ``combinatoria'' tal y como lo usamos actualmente, fue introducido por el matemático alemán Leibniz (S.XVII) en su obra ``Ars combinatoria' '. Coetaneamente, el matemático francés Pascal, publica sus ideas sobre coeficientes binomiales, combinaciones y polinomios. Pascal, tal y como hace referencia en el libro de Carl B. Boyer: Historia de la matemática, es considerado como el fundador de la combinatoria moderna y sus resultados fueron usados por Bernouilli (S.XVII) para demostrar la forma general del teorema binomial.

Técnicas de Recuento y Conceptos Previos de Combinatoria

Técnicas de Recuento

Las técnicas de recuento tratan de las ordenaciones de elementos de un conjunto siguiendo unas reglas establecidas. Vamos a analizar los principios básicos de recuento y las técnicas más utilizadas, que tratan de responder principalmente a dos problemas: de existencia y de enumeración. Los conjuntos que manejaremos se supondrán finitos. I. Enumeración Si el conjunto es pequeño y sin regla de formación fija, el único procedimiento viable para contar sus elementos es hacer una enumeración de todos ellos. Pero a menudo, los conjuntos tienen demasiados elementos para poder enumerarlos de forma exhaustiva. Entonces, si obedecen a unas reglas de formación fijas, permiten construir artificios mentales para conocer cuántos son, sin tener que hacer una lista de todos ellos. II. Correspondencia biyectiva con {1,2, ... , n} Consiste en establecer una correspondencia biyectiva, o uno a uno, entre los elementos del conjunto del que queremos saber su cardinal y los de un subconjunto de la forma {1,2, ... , n}. III. Principio de adición Si tenemos A1, A2, ... , An conjuntos finitos disjuntos (diferentes, no tienen ningún elemento en común) dos a dos, es decir, A¡ n Aj = Ø, Vi + j, i, j E {1, ... , n}, entonces: |A1 U A2 U ... U An| = |A1| + |A2| + ... + |Anl IV. Principio de multiplicación Si tenemos, A1, A2, ... , An conjuntos finitos no vacíos, entonces: Página 2 de 10|A1 X A2 X ... X An| = |A1| . |A2| . ... . |Anl V. Principio de la división Si un conjunto de n elementos se parte en clases y cada clase tiene r elementos, entonces el número de clases es ". VI. Principio de Dirichlet (de las cajas o del palomar) Si tenemos m objetos que se distribuyen en n cajas, m > n, entonces una de las cajas recibe al menos dos objetos. VII. Este principio generalizado sería: Si tenemos m objetos para distribuir en n cajas con m > n . q, entonces al menos una de las cajas tiene más de q objetos. Principio de inclusión-exclusión (o de la criba) Si sabemos contar los elementos que hay en las intersecciones de una serie de conjuntos, entonces podremos determinar el tamaño de la unión de todos ellos. Sean A y B dos conjuntos finitos no vacíos. Entonces: AUB| = |A| + |B| - |An B] En general, se verifica: n n i |AinAj NAK| - ... + (-1)"+1 . |A1 0 A2 0 .. n Anl i=1 i=1 i

Factorial de un Número

Definición Sea n E N, se llama factorial de n, y se escribe n!, a: 0! = 1 1! = 1 n! = n · (n -1) · (n-2) . ... . 3 . 2 . 1, Vn ≥ 2 Es decir, n! Es el producto de los n primeros números naturales no nulos. Proposición (Propiedades) 1) n! · (n + 1) = (n+1)! 2) k! · (k + 1) · (k +2) . ... . n = n!, Vk

Números Combinatorios

Definición Dados dos números naturales m, n con m ≥ n, se llama número combinatorio de m sobre n, y se designa (m), al cociente: n n! . (m - n)! m! donde a m se le llama base y a n orden. Proposición (Propiedades) a) (m) = (m) = 1; (") = ( __ 1) = m b) (m) = (mn) c) Fórmula de Stiegel: (m) = (m-1) + (m-1) d) ("+1) = (m) + (m-1 - + (m-2) + .... + ("+1) + ("), Vm ≥ n ≥ 1 n n e) (m+n) p (m+n) = (m) . (n) + (") . p-1/ ")++(pm) . (7) +(m) (2) f) ΣΚ o (*) =2η g) _k=0(-1)k.(R)=0 Observación Los números combinatorios tienen una forma conocida de representación llamada "triángulo de Pascal" o "triángulo de Tartaglia". 1 1 1 121 3 1331 Muchas de las propiedades anteriormente enunciadas se pueden deducir a partir de este triángulo.

Combinatoria

Variaciones Ordinarias

Definición Sea A = {a1, a2, ... , am} un conjunto de m elementos. Dado n E N tal que 1 ≤n ≤m, llamaremos variación (o variación ordinaria) de orden n (o de m elementos tomados de n en n) a todo subconjunto totalmente ordenado según un orden estricto compuesto de n elementos de A. Página 4 de 10Proposición El número de variaciones ordinarias de m elementos tomados de n en n (n ≤ m) se denota Vm,n º Vm, y vale: Vm,n= (m - n)! m! = m . (m - 1) . ... . (m - n + 1) Demostración Para determinar el número de variaciones de orden n que se pueden formar en un conjunto de m elementos tendremos en cuenta el principio de la multiplicación enunciado anteriormente. Para la primera posición de la ordenación pueden escogerse m elementos diferentes, para la segunda posición sólo (m - 1) y así hasta el último en el que quedan por escogerse m - (n-1) = m -n + 1. Ejemplo: En la carrera final de un campeonato corren 8 atletas. ¿ De cuántas formas se pueden configurar el pódium? V8,3 => 8! F (8-3)! = 8 .7 . 6 = 336 formas. Teorema Se verifica que: Vm,n = (m - n + 1) . Vm,n-1 Demostración (m -n +1) · Vm,n-1 = (m-n+1). (m -n + 1)! m! = (m=A+I) . (m=n+1) . (m-n)! m! = Vm,n

Variaciones con Repetición

Definición Sea A = {a1, a2, ... , am} un conjunto de m elementos. Dado n E N, llamaremos variación con repetición de orden n a todo elemento de A™ = A x ... (n) × A. (Los elementos no tienen por qué ser diferentes, ni es necesario que n ≤ m). Proposición El número de variaciones con repetición de m elementos tomados de n en n se denota VRm,n O VRm, y vale: VRm,n = mn Ejemplo: ¿Cuál es el número de boletos de quiniela a rellenar para asegurar un acierto pleno? VR3,14 = 314 = 4.782.969 boletos. Teorema Se verifica que: VRm,n = m . VRm,n-1 Página 5 de 10Demostración m . VRm.n-1 = m . mn-1 = mn = VRm,n

Permutaciones Ordinarias

Definición Sea A = {a1, a2, ... , am} un conjunto de m elementos. Llamaremos permutación (o permutación ordinaria) de A, a todo conjunto totalmente ordenado según un orden estricto compuesto de los mismos elementos de A. Proposición El número de permutaciones ordinarias de m elementos se denota por Pm, y vale: Pm = m! Demostración Como se puede apreciar, las permutaciones ordinarias son un tipo particular de variaciones ordinarias, en las que intervienen todos los elementos del conjunto. Por tanto, se cumple: Pm = Vm,m =7 (m -m)! m! For= m! m! Ejemplo: ¿De cuántas formas diferentes pueden disponerse los 7 colores del arco iris? P7 = 7! = 5040 formas.

Permutaciones Circulares

Existe otro tipo de permutaciones en las que es indiferente la posición de sus elementos; solo importa la disposición relativa de unos elementos con otros. Estas permutaciones se denominan permutaciones circulares. Definición Una permutación circular de m objetos distintos es una colocación ordenada de dichos objetos en posiciones igualmente espaciados sobre una circunferencia. Se consideran dos permutaciones circulares iguales si una puede ser obtenida de la otra mediante una rotación apropiada de la circunferencia alrededor de su centro. Proposición El número de permutaciones circulares de m elementos distintos se denota PCm y vale: PCm = (m -1)! Página 6 de 10Ejemplo: ¿De cuántas formas se pueden sentar 5 personas en una mesa redonda? PC5 = (5 - 1)! = 4! = 24 formas.

Permutaciones con Repetición

Definición Sea A = {a1, ... (m1), a1; a2, ... (m2) , a2; ...; ap, ... (mp), apt un conjunto de m elementos entre los que existen m1 objetos iguales y de un mismo tipo (a1), m2 iguales pero de otro tipo (a2), y así sucesivamente hasta un grupo de mp objetos también idénticos entre sí (ap), es decir, se cumple que: m1 + m2 + ... + mp = m Se llama permutación con repetición de m elementos a cada una de las ordenaciones posibles con los m elementos dados, teniendo en cuenta que dos permutaciones son distintas si difieren en el orden de los elementos. Proposición El número de permutaciones con repetición de m elementos con m1 elementos iguales entre sí, ... , mp elementos iguales entre sí, se denota por PRm , y vale: PR m m1 .... ,mp m1! . m2! . m3! . ... . mp! m! con m1 + m2 + m3 + ... + mp = m Ejemplo: En el palo de señales de un barco se pueden izar 3 banderas rojas, 2 azules y 4 verdes. ¿ Cuántas señales distintas pueden indicarse con las nueve banderas? PR3,2,4 = 9! 3 !. 2 !. 4! = 1260 señales.

Combinaciones Ordinarias

Definición Sea A = {a1, a2, ... , am} un conjunto de m elementos. Dado n E N tal que 1 ≤n ≤ m, llamaremos combinación (o combinación ordinaria) de orden n (o de m elementos tomados de n en n) a todo subconjunto de A que contiene n elementos. Así, dos combinaciones de orden n con elementos de A serán distintas si y sólo si difieren en algún elemento (no considerando el orden). Proposición El número de combinaciones de m elementos tomados de n en n (n € N, 1 ≤ n ≤m). Se denota por Cm 0 Cm,n, y vale: Cm,n =; m! n! (m - n)! Página 7 de 10