Tema1opos

Tema 3. T´ecnicas de recuento. Combinatoria. Beatriz Ballesteros https://preparadoroposicionesmatematicas.com · Rev. 1.7 ´Indice 1. Introducci´on 2 2. Combinatoria cl´asica. 2 2.1. T´ecnicas de recuento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2. Tipos de agrupaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Combinatoria. 4 3.1. Factorial de un n´umero. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2. Variaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2.1. Variaciones ordinarias. . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2.2. Variaciones con repetici´on. . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3. Permutaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3.1. Permutaciones ordinarias. . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3.2. Permutaciones con repetici´on. . . . . . . . . . . . . . . . . . . . . . . 7 3.4. Combinaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.4.1. Combinaciones ordinarias. . . . . . . . . . . . . . . . . . . . . . . . . 7 3.4.2. N´umeros combinatorios. . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4.3. Combinaciones con repetici´on. . . . . . . . . . . . . . . . . . . . . . . 9 4. Combinatoria y aplicaciones entre conjuntos. 10 5. Conclusi´on. 10 6. Bibliograf´ıa. 10 1 80251817X 80251817X 80251817X.

1 Introducci´on La combinatoria es una parte de la Matem´atica Discreta que se ocupa del estudio y de las propiedades de los distintos grupos que se pueden formar con elementos de un conjunto dado seg´un el n´umero de elementos de cada grupo, la clase de elementos que lo forman, o el orden de colocaci´on de estos. En Occidente, la combinatoria surge en el siglo XVII, con los trabajos de Pascal y Fer- mat sobre la teor´ıa de los juegos de azar. En estos trabajos se establece la conexi´on entre combinatoria y probabilidad. El t´ermino ”combinatoria” fue introducido por Leibniz. Sus trabajos, junto con los de Bernoulli, dieron lugar al establecimiento de la combinatoria como una rama nueva e inde- pendiente de las matem´aticas. En el siglo XVIII, Euler desarroll´o en sus trabajos grandes avances en el campo de la combinatoria, al relacionarla con la teor´ıa de grafos. Hoy en d´ıa, la combinatoria tiene grandes aplicaciones en la teor´ıa de la probabilidad, en inform´atica en la teor´ıa de la codificaci´on y en el an´alisis de algoritmos, as´ı como en la topolog´ıa. En este tema, analizaremos las t´ecnicas iniciales que dieron lugar a la combinatoria ac- tual. Nos centraremos en el estudio de la combinatoria cl´asica: los tipos de agrupamientos, sus caracter´ısticas, y el c´alculo del n´umero de agrupamientos de cada tipo. 2 Combinatoria cl´asica. La combinatoria cl´asica trata sobre la formaci´on y recuento de agrupaciones a partir de los elementos de un conjunto. 2.1 T´ecnicas de recuento. Las t´ecnicas de recuento estudian las ordenaciones de elementos de un conjunto siguiendo unas reglas determinadas. A continuaci´on analizaremos los principios fundamentales de recuento y las t´ecnicas m´as utilizadas para ello. Estos, tratar´an de dar respuesta principalmente a dos tipos de problemas: 1. De existencia: analizan la posibilidad de la existencia de las agrupaciones pedidas. 2. De enumeraci´on: nos permiten determinar el n´umero de clasificaciones posibles. Los conjuntos con los que trabajaremos se supondr´an finitos. 2 80251817X 80251817X 80251817X.

Principales t´ecnicas de recuento 1. Enumeraci´on: si el conjunto es peque˜no y sin regla de formaci´on fija, el ´unico procedi- miento viable para contar sus elementos es hacer una enumeraci´on de todos ellos. 2. Correspondencia biyectiva con el conjunto: consiste en establecer una correspondencia biyectiva entre los selementos del conjunto del que queremos saber su cardinal, y los del subconjunto de la forma. 3. Principio de adici´on: si tenemos A1, A2, ..., An conjuntos finitos y disjuntos (Ai∩Aj = ∅ ∀i, j = 1, ..., n), entonces, siendo |A| = cardinal de A: |A1 ∪ A2 ∪ ... ∪ An| = |A1| + |A2| + ... + |An| 4. Principio de multiplicaci´on: si tenemos A1, A2, ..., An conjuntos finitos no vac´ıos, en- tonces: |A1 × A2 × ... × An| = |A1| · |A2| · ... · |An| 5. Principio de la divisi´on: si un conjunto de n elementos se parte en clases, y cada clase tiene r elementos, entonces el n´umero de clases es n r . 6. Principio de Dirichlet, de las cajas o del palomar: si tenemos m objetos que se distri- buyen en n cajas, con m > n, entonces una de las cajas recibe al menos dos objetos. 7. Principio generalizado de Dirichlet: si tenemos m objetos que se distribuyen en n cajas, con m > n · q, entonces una de las cajas recibe m´as de q objetos. 8. Principio de inclusi´on-exclusi´on: sean A1, A2, ..., An conjuntos finitos no vac´ıos, enton- ces: | n� i=1 Ai| = n � i=1 |Ai|− n � i<j |Ai ∩Aj|+ n � i<j<k |Ai ∩Aj ∩Ak|−...+(−1)n+1|A1 ∩A2 ∩...∩An| 9. Principio del complementario: si un conjunto de n elementos est´a dividido en dos partes, y una de ellas contiene m elementos, entonces la otra contiene n − m elementos. 10. Diagramas de ´arbol: permiten organizar procedimientos de formaci´on de agrupaciones basados en varias etapas. Con ellos se identifican las posibilidades que ofrece cada etapa, y una vez identificadas, se puede aplicar el principio de multiplicaci´on ya visto para realizar el recuento. 11. Diagramas de Venn: sirven para organizar y clasificar elementos de un conjunto en funci´on de determinadas propiedades, facilitando as´ı los recuentos. 12. Tablas para representar productos cartesianos: se utilizan para formar los posibles pares ordenados con elementos de dos conjuntos y/o determinar su n´umero. Se representa mediante tablas de doble entrada donde cada casilla representa uno de los posibles pares ordenados. Tambi´en permiten identificar f´acilmente aquellos pares que cumplen ciertos requisitos. 3 80251817X 80251817X 80251817X.

2.2 Tipos de agrupaciones. Las posibilidades de agrupaciones son pr´acticamente infinitas. Sin embargo, existen una serie de agrupaciones b´asicas que, adem´as de resolver una buena parte de los problemas m´as comunes, facilitan el an´alisis de situaciones m´as complejas. Podemos resumirlas en el siguiente esquema: 3 Combinatoria. En este apartado vamos a analizar las distintas agrupaciones citadas en el punto anterior, aunque empezaremos definiendo el concepto de factorial de un n´umero, necesario para el desarrollo de los siguientes ep´ıgrafes. 3.1 Factorial de un n´umero. Sea n ∈ N, se llama factorial de n, y lo denotamos como n! a: 0! = 1 1! = 1 n! = n · (n − 1) · (n − 2) · ... · 2 · 1 ∀n ≥ 2 De la definici´on anterior se deducen las siguientes propiedades: a) n! · (n + 1) = (n + 1)! b) k! · (k + 1) · (k + 2) · ... · n = n! ∀k < n Para n grande, n! resulta tedioso de calcular, por lo que podemos aproximarlo por la f´ormula de Stirling: n! ≈ nn√ 2πn en . 4 80251817X 80251817X 80251817X.

3.2 Variaciones. 3.2.1 Variaciones ordinarias. Definici´on: Llamamos variaciones ordinarias o sin repetici´on de m elementos tomados de n en n (n ≤ m) a las agrupaciones que se pueden formar: Sin repetir elementos dentro de la agrupaci´on. Teniendo en cuenta que dos agrupaciones se consideran distintas cuando est´an formadas por distinos elementos, o por los mismos elementos pero en distinto orden. Proposici´on: El n´umero de variaciones ordinarias de m elementos tomados de n en n (n ≤ m) es: Vm,n = V n m = m! (m − n)! = m · (m − 1) · ... · (m − n + 1) Demostraci´on: Si organizamos el proceso de formaci´on de una variaci´on de orden n en n etapas, hay m posibilidades para la primera etapa, m − 1 posibilidades para la segunda, m − 2 para la tercera, y as´ı sucesivamente para las n etapas, siendo la ´ultima m − n + 1. Aplicando el principio de multiplicaci´on quedar´ıa demostrado. Ejemplo: ¿De cu´antas maneras se pueden completar los puestos de delegado y subdele- gado de una clase de 30 alumnos? Importa el orden, la agrupaci´on tiene menos elementos que el total del conjunto y no se pueden repetir elementos, por tanto, se trata de una variaci´on ordinaria: V30,2 = 30! 28! = 870 formas distintas 3.2.2 Variaciones con repetici´on. Definici´on: Llamamos variaciones con repetici´on de m elementos tomados de n en n a las agrupaciones que se pueden formar: Pudi´endose repetir elementos dentro de la agrupaci´on. Teniendo en cuenta que dos agrupaciones se consideran distintas cuando est´an formadas por distinos elementos, o por los mismos elementos pero en distinto orden. Proposici´on: El n´umero de variaciones con repetici´on de m elementos tomados de n en n es: V Rm,n = V Rn m = mn Demostraci´on: Se realiza de manera id´entica a la anterior, solo que ahora en cada una de las n etapas nos encontramos con m posibilidades, por tanto: m · m · ... · m = mn Ejemplo: ¿Cu´antas palabras de 5 letras con o sin sentido pueden formarse con las letras A, M, R? Importa el orden, la agrupaci´on no tiene el mismo n´umero de elementos que el total del conjunto, y se pueden repetir elementos, por tanto, se trata de una variaci´on con repetici´on: V R3,5 = 35 = 243 palabras 5 80251817X 80251817X 80251817X.

3.3 Permutaciones. 3.3.1 Permutaciones ordinarias. Definici´on: Llamamos permutaciones ordinarias o sin repetici´on de n elementos a las variaciones ordinarias de n elementos tomados de n en n. Por tanto, el n´umero de permutaciones ordinarias o sin repetici´on de n elementos es: Pn = Vn,n = n! (n − n)! = n! 0! = n! Ejemplo: ¿Cu´antos n´umeros diferentes de tres cifras se pueden formar con los d´ıgitos 1, 5, 7 sin que el mismo d´ıgito aparezca m´as de una vez? Importa el orden, la agrupaci´on tiene el mismo n´umero de elementos que el total del con- junto, y no se pueden repetir elementos, por tanto, se trata de una permutaci´on ordinaria: P3 = 3! = 6 n´umeros diferentes Dos permutaciones de un conjunto A ser´an diferentes si es distinto el orden de sus ele- mentos. Dados n elementos distintos a1, a2, ..., an, adoptaremos una de sus permutaciones, por ejemplo a1a2...an como la principal. En otra permutaci´on cualquiera formada con los mismos elementos, se dir´a que: Dos de ellos presentan una inversi´on, cuando prescindiendo de los restantes, estos se suceden en orden contrario al de la permutaci´on principal. Ejemplo: En la permutaci´on a3a1a4a2, a3 forma una inversi´on con a1 y a2, as´ı como a4 con a2. Un elemento presenta una permanencia, cuando presenta el mismo orden que en la permutaci´on principal. Ejemplo: En la permutaci´on a1a3a4a2, a1 presenta una permanencia. Se ha efectuado una trasposici´on, cuando se cambien entre s´ı dos elementos cualesquiera respecto de la permutaci´on principal. Ejemplo: En la permutaci´on a1a3a2a4, a2 y a3 presentan una trasposici´on. Decimos que una permutaci´on es de clase par o impar seg´un sea par o impar el n´umero total de inversiones que presenta. A dicho n´umero, le llamamos ´ındice de permutaci´on. Para hallar el ´ındice de permutaci´on hay que comparar cada elemento con todos los que le siguen. Ejemplo: La permutaci´on a3a1a4a2 tiene ´ındice de permutaci´on 3, ya que presenta 3 inver- siones. Dado un conjunto, existen el mismo n´umero de permutaciones de clase par que de clase impar. 6 80251817X 80251817X 80251817X.

3.3.2 Permutaciones con repetici´on. Definici´on: Llamamos permutaciones con repetici´on de n elementos a las distintas for- mas de ordenar dichos elementos, entre los que puede haber elementos iguales, es decir, repetidos. Proposici´on: El n´umero de permutaciones con repetici´on de n elementos, entre los que hay un grupo de n1 elementos iguales, otro grupo de n2 elementos iguales, ..., y un grupo de nk elementos iguales es: PRn1,n2,...,nk n = n! n1! · n2! · ... · nk! Demostraci´on: Hay n! formas de ordenar los elementos si estos son distintos. Como un elemento se repite n1 veces, hay n1! ordenaciones iguales que deber´ıan de contar como una sola. Lo mismo ocurre con el resto de elementos repetidos, y de ah´ı que se divida n! entre los ni! con 1 ≤ i ≤ k. Ejemplo: ¿Con las letras de la palabra MERMELADA cu´antas palabras distintas, con o sin sentido, de 9 letras se pueden formar? Importa el orden, la agrupaci´on tiene el mismo n´umero de elementos que el total del con- junto, y hay elementos repetidos (M dos veces, E dos veces, A dos veces), por tanto, se trata de una permutaci´on con repetici´on: PR2,2,2 9 = 9! 2! · 2! · 2! = 45360 palabras distintas 3.4 Combinaciones. 3.4.1 Combinaciones ordinarias. Definici´on: Llamamos combinaciones ordinarias o sin repetici´on de m elementos toma- dos de n en n (n ≤ m) a las agrupaciones que se pueden formar: Sin repetir elementos dentro de la agrupaci´on. Teniendo en cuenta que dos agrupaciones se consideran distintas solo cuando est´an formadas por distintos elementos. Es decir, el orden de los elementos no importa. Proposici´on: El n´umero de combinaciones ordinarias de m elementos tomados de n en n (n ≤ m) es: Cm,n = Cn m = Vm,n Pn = m! (m − n)! · n! Demostraci´on: Cada combinaci´on de orden n genera n! variaciones ordinarias al cam- biar el orden de colocaci´on de sus n elementos. Si esto lo hacemos para cada combinaci´on de orden n, obtenemos todas las variaciones ordinarias de m elementos tomados de n en n: Cm,n · n! = Vm,n =⇒ Cm,n = Vm,n Pn = m! (m − n)! · n! Ejemplo: ¿Cu´antas parejas distintas puedo formar en un grupo de 10 jugadores? No importa el orden, la agrupaci´on tiene menos elementos que el total del conjunto y no se pueden repetir elementos, por tanto, se trata de una combinaci´on ordinaria: C10,2 = 10! 2! · 8! = 45 parejas distintas 7 80251817X 80251817X 80251817X.

3.4.2 N´umeros combinatorios. Al n´umero de combinaciones de m elementos tomados de n en n, Cm,n, se le llama n´ume- ro combinatorio y se representa por Åm n ã . Donde m es la base y n es el orden del n´umero combinatorio. Veamos algunas propiedades de los n´umeros combinatorios: 1. Åm 0 ã = Åm m ã = 1 2. Åm 1 ã = Å m m − 1 ã = m 3. Åm n ã = Å m m − n ã 4. F´ormula de Stifel: Åm n ã = Åm − 1 n − 1 ã + Åm − 1 n ã 5. Siendo m ≥ n ≥ 1 se verifica: Åm n ã = Åm − 1 n − 1 ã + Åm − 2 n − 1 ã + Åm − 3 n − 1 ã + ... + Å n n − 1 ã + Ån − 1 n − 1 ã A partir de estas propiedades puede completarse de forma sencilla la tabla de los n´umeros combinatorios, que suele representarse con la configuraci´on del tri´angulo de Tartaglia: Å0 0 ã Å1 0 ã Å1 1 ã Å2 0 ã Å2 1 ã Å2 2 ã Å3 0 ã Å3 1 ã Å3 2 ã Å3 3 ã Å4 0 ã Å4 1 ã Å4 2 ã Å4 3 ã Å4 4 ã ... Calculando los n´umeros combinatorios: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ... Partiendo del tri´angulo de Tartaglia obtenemos los coeficientes del binomio de Newton: (a + b)n = n � i=0 Ån i ã an−ibi 8 80251817X 80251817X 80251817X.

Adem´as, a partir de los n´umeros combinatorios podemos obtener el n´umero total de subconjuntos de un conjunto de n elementos: Cn,0 + Cn,1 + ... + Cn,n = 2n Dicha f´ormula se puede demostrar f´acilmente utilizando el binomio de Newton para (1+1)n. 3.4.3 Combinaciones con repetici´on. Definici´on: Llamamos combinaciones con repetici´on de m elementos tomados de n en n a las agrupaciones de n elementos que se pueden formar: Pudi´endose repetir elementos dentro de la agrupaci´on. Teniendo en cuenta que dos agrupaciones se consideran distintas solo cuando est´an formadas por distinos elementos. Es decir, el orden de los elementos no importa. Proposici´on: El n´umero de combinaciones con repetici´on de m elementos tomados de n en n es: CRm,n = CRn m = Ån + m − 1 n ã = (n + m − 1)! (m − 1)! · n! Demostraci´on: Consideremos las combinaciones con repetici´on de m elementos (a1, a2, ..., am) de orden n. Entonces una combinaci´on gen´erica puede expresarse mediante una sucesi´on de s´ımbolos de dos clases (por ejemplo, α y β) de la forma siguiente: Para representar el elemento a1 se escribe una α seguida de tantas β como veces entre dicho elemento en la combinaci´on considerada. Para representar el elemento a2 se escribe una α seguida de tantas β como veces entre dicho elemento; y as´ı sucesivamente. Si un elemento no se repite, sera representado por una α seguida de ninguna β. Por ejemplo, si tenemos cuatro elementos a1, a2, a3, a4, la combinaci´on a1a1a3, se escribe como αββααβα. De este modo, cada combinaci´on considerada viene representada por una expresi´on que empieza por α seguida m − 1 veces por α y n veces por β. Rec´ıprocamente, toda expresi´on de este tipo representa una de las combinaciones. Por tanto, el n´umero de combinaciones posibles viene dado por el n´umero de permuta- ciones con repetici´on de dos elementos donde un elemento (α) se repite m − 1 veces y el otro elemento (β) se repite n veces. Esto es: CRm,n = PRn,m−1 n+m−1 = (n + m − 1)! n!(m − 1)! = Ån + m − 1 n ã Ejemplo: En una bodega hay 4 tipos diferentes de botellas de vino. ¿De cu´antas maneras pueden escogerse 3 botellas? No importa el orden y se pueden repetir elementos, por tanto, se trata de una combinaci´on con repetici´on: CR4,3 = Å3 + 4 − 1 3 ã = Å6 3 ã = 6! 3!3! = 20 maneras distintas 9 80251817X 80251817X 80251817X.

4 Combinatoria y aplicaciones entre conjuntos. En este apartado vamos a enunciar una serie de proposiciones en las que se relacionan las f´ormulas combinatorias de los apartados anteriores con el n´umero de aplicaciones que existen entre diferentes conjuntos. Obviaremos su demostraci´on dada la longitud del tema. Proposici´on 1: Sean los conjuntos A = y B =, card(A) = n y card(B) = m. El n´umero de aplicaciones entre A y B coincide con el n´umero de V Rm,n. Proposici´on 2: Sean los conjuntos A = y B = con n < m, card(A) = n y card(B) = m. El n´umero de aplicaciones inyectivas entre A y B coincide con el n´umero de Vm,n . Proposici´on 3: Sean los conjuntos A y B dos conjuntos con el mismo cardinal, card(A) = n = card(B). El n´umero de aplicaciones biyectivas entre A y B coincide con el n´umero de Pn. 5 Conclusi´on. Como s´ıntesis de este tema, podemos concluir que la combinatoria es una rama de la Ma- tem´atica Discreta con numerosas aplicaciones en la teor´ıa de la probabilidad, la topolog´ıa o la inform´atica. La combinatoria se encarga del an´alisis y de las propiedades de los diferentes agrupamientos que se pueden formar a partir de los elementos de un conjunto. Para realizar los recuentos de los elementos de un conjunto se utilizan una serie de principios y t´ecnicas denominados t´ecnicas de recuento. Por ´ultimo, de entre todos los tipos de agrupamientos que se pueden formar a partir de los elementos de un conjunto cabe destacar tres de ellos: las variaciones, las permutaciones y las combinaciones. Pudiendo ser todas ellas con repetici´on o sin repetici´on, seg´un pueda haber o no en el agrupamiento elementos repetidos. Estos tres tipos de agrupamientos permiten resolver una gran cantidad de problemas combinatorios. Para cerrar este tema, vamos a relacionarlo con el curr´ıculo de Educaci´on Secundaria de Matem´aticas. Muchos de los contenidos de este tema se pueden encontrar en las asignaturas de Matem´aticas de 3º y 4º ESO, as´ı como en las Matem´aticas en Bachillerato. Se introducen los conceptos b´asicos y se trabaja la combinatoria por s´ı misma a la vez que convierte en una herramienta para el c´alculo de probabilidades. 6 Bibliograf´ıa. BOYER. (1974). Historia de la matem´atica. Editorial: Alianza. FERN´ANDEZ VI˜NA. (1994). An´alisis matem´atico. Editorial: Tecnos. BIGSS. (1998). Matem´atica discreta. Editorial: Vicens-Vives. GRIMALDI. (2003). Matem´atica discreta y combinatoria. Editorial: Pearson. FERN´ANDEZ GALLARDO Y F´ERNANDEZ P´EREZ. Notas de matem´atica discreta. Universidad Aut´onoma de Madrid. (www.uam.es) 10 80251817X 80251817X 80251817X.