{"id":1296,"date":"2026-05-18T10:15:18","date_gmt":"2026-05-18T08:15:18","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=1296"},"modified":"2026-05-15T19:30:59","modified_gmt":"2026-05-15T17:30:59","slug":"1296","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=1296","title":{"rendered":"MAD: Principio de inclusi\u00f3n-exclusi\u00f3n"},"content":{"rendered":"<p>El principio de inclusi\u00f3n-exclusi\u00f3n permite calcular el cardinal de la uni\u00f3n de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones. Si consideramos que tenemos dos conjuntos finitos \\(A\\) y \\(B\\), resultar\u00e1: \\[|A \\cup B| = |A| + |B| &#8211; |A \\cap B|.\\]<\/p>\n<p>Imaginemos que tenemos tres conjuntos finitos:<br \/>\n\\[|A \\cup B \\cup C| = |A| + |B| + |C| &#8211; |A \\cap B| &#8211; |A \\cap C| &#8211; |B \\cap C| + |A \\cap B \\cap C|.\\]<\/p>\n<blockquote><p><strong>Ejercicio:<\/strong> En una clase de 1\u00ba de Ingenier\u00eda Inform\u00e1tica con 60 alumnos, se realiza una encuesta sobre los lenguajes de programaci\u00f3n que conocen. Los resultados son los siguientes:<\/p>\n<ul>\n<li>25 conocen Python.<\/li>\n<li>26 conocen Java.<\/li>\n<li>18 conocen C++.<\/li>\n<li>9 conocen Python y Java.<\/li>\n<li>11 conocen Java y C++.<\/li>\n<li>7 conocen Python y C++.<\/li>\n<li>3 conocen los tres lenguajes.<\/li>\n<\/ul>\n<p>\u00bfCu\u00e1ntos alumnos conocen <strong>al menos uno<\/strong> de estos tres lenguajes? \u00bfCu\u00e1ntos alumnos no conocen ninguno de los tres?<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv23() {\n  var htmlShow23 = document.getElementById(\"html-show23\");\n  if (htmlShow23.style.display === \"none\") {\n    htmlShow23.style.display = \"block\";\n  } else {\n    htmlShow23.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23\" style=\"display: none;\">\nPara resolver este problema, utilizaremos el Principio de Inclusi\u00f3n-Exclusi\u00f3n(PIE). Definimos los siguientes conjuntos:<\/p>\n<p>* $P$: Alumnos que conocen Python.<br \/>\n* $J$: Alumnos que conocen Java.<br \/>\n* $C$: Alumnos que conocen C++.<\/p>\n<p>### 1. C\u00e1lculo de alumnos que conocen al menos uno<\/p>\n<p>Queremos hallar el cardinal de la uni\u00f3n de los tres conjuntos, es decir, $|P \\cup J \\cup C|$. La f\u00f3rmula del PIE para tres conjuntos es:<\/p>\n<p>$$|P \\cup J \\cup C| = (|P| + |J| + |C|) &#8211; (|P \\cap J| + |J \\cap C| + |P \\cap C|) + |P \\cap J \\cap C|$$<\/p>\n<p>Sustituimos los valores proporcionados:<\/p>\n<p>* Sumamos las capacidades individuales: $25 + 26 + 18 = 69$<br \/>\n* Restamos las intersecciones dobles (porque las hemos contado dos veces): $-(9 + 11 + 7) = -27$<br \/>\n* Sumamos la intersecci\u00f3n triple (porque al restar las dobles, la hab\u00edamos eliminado por completo): $+3$<\/p>\n<p>$$|P \\cup J \\cup C| = 69 &#8211; 27 + 3 = 45$$<\/p>\n<p>Resultado: 45 alumnos conocen al menos uno de los lenguajes.<\/p>\n<p>### 2. Alumnos que no conocen ninguno<\/p>\n<p>Si el total de la clase es de 60 alumnos ($|U| = 60$), para hallar los que no conocen ninguno, simplemente restamos al total aquellos que conocen al menos uno:<\/p>\n<p>$$|U| &#8211; |P \\cup J \\cup C| = 60 &#8211; 45 = 15$$<\/p>\n<p>Resultado: 15 alumnos no conocen ninguno de los tres lenguajes.\n<\/p><\/div>\n<hr \/>\n<blockquote>\n<p><strong>Principio de Inclusi\u00f3n-Exclusi\u00f3n(PIE)<\/strong>: Si <i>A<\/i><sub>1<\/sub>, &#8230;, <i>A<sub>n<\/sub><\/i> son conjuntos finitos entonces:<\/p>\n<p>\\[\\begin{align}\\biggl|\\bigcup_{i=1}^n A_i\\biggr| &#038; {} =\\sum_{i=1}^n\\left|A_i\\right|-\\sum_{i,j\\,:\\,1 \\le i < j \\le n}\\left|A_i\\cap A_j\\right| \\\\&#038; {}\\qquad +\\sum_{i,j,k\\,:\\,1 \\le i < j < k \\le n}\\left|A_i\\cap A_j\\cap A_k\\right|-\\ \\cdots\\ + \\left(-1\\right)^{n+1} \\left|A_1\\cap\\cdots\\cap A_n\\right|\\end{align}\\]\n<\/p>\n<\/blockquote>\n<p>Una consecuencia muy pr\u00e1ctica es la siguiente.<\/p>\n<p>Si consideramos un conjunto universal $S$  y una serie de subconjuntos $A_i$ (aquellos que cumplen la propiedad $i$), la cantidad de elementos <strong>que no cumplen ninguna<\/strong> de las propiedades se expresa como el cardinal de la intersecci\u00f3n de sus complementos $\\bar{A}_i$.<\/p>\n<p>$$\\left| \\bigcap_{i=1}^{n} \\bar{A}_i \\right| = \\left| S &#8211; \\bigcup_{i=1}^{n} A_i \\right| = |S| &#8211; \\sum_{i=1}^{n} |A_i| + \\sum_{1 \\le i < j \\le n} |A_i \\cap A_j| - \\cdots + (-1)^n |A_1 \\cap \\cdots \\cap A_n|$$\n\n<strong>Nota:<\/strong> Esta estructura es la base de algoritmos de conteo en grafos y es vital para entender la complejidad de problemas combinatorios donde el espacio de b\u00fasqueda es muy grande.<\/p>\n<blockquote><p><strong>Ejercicio:<\/strong> Un administrador de sistemas est\u00e1 analizando un lote de 100 peticiones HTTP sospechosas en un servidor. Para limpiar el tr\u00e1fico, necesita identificar cu\u00e1ntas peticiones son \u00abseguras\u00bb, es decir, aquellas que no presentan ninguno de los siguientes tres fallos de seguridad:<\/p>\n<p>* Propiedad $A_1$: La petici\u00f3n proviene de una IP en lista negra.<br \/>\n* Propiedad $A_2$: La petici\u00f3n contiene caracteres SQL maliciosos.<br \/>\n* Propiedad $A_3$: La petici\u00f3n supera el tama\u00f1o de buffer permitido.<\/p>\n<p>Tras un an\u00e1lisis automatizado, se obtienen los siguientes datos:<\/p>\n<p>* $|A_1| = 12$, $|A_2| = 18$, $|A_3| = 15$<br \/>\n* Peticiones con dos fallos: $|A_1 \\cap A_2| = 7$, $|A_2 \\cap A_3| = 8$, $|A_1 \\cap A_3| = 5$<br \/>\n* Peticiones con los tres fallos simult\u00e1neos: $|A_1 \\cap A_2 \\cap A_3| = 2$<\/p>\n<p>Utilizando la forma complementaria del Principio de Inclusi\u00f3n-Exclusi\u00f3n, calcula cu\u00e1ntas peticiones son seguras (no tienen ning\u00fan fallo).\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv23b() {\n  var htmlShow23b = document.getElementById(\"html-show23b\");\n  if (htmlShow23b.style.display === \"none\") {\n    htmlShow23b.style.display = \"block\";\n  } else {\n    htmlShow23b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23b\" style=\"display: none;\">\nPara resolverlo, aplicamos directamente la f\u00f3rmula de la intersecci\u00f3n de complementarios sobre el conjunto universal $|S| = 100$:<\/p>\n<p>$$\\left| \\bigcap_{i=1}^{3} \\bar{A}_i \\right| = |S| &#8211; \\sum |A_i| + \\sum |A_i \\cap A_j| &#8211; |A_1 \\cap A_2 \\cap A_3|$$<\/p>\n<p>1. Sustituimos los valores:<\/p>\n<p>* Total ($|S|$): $100$<br \/>\n* Suma de fallos individuales: $12 + 18 + 15 = 45$<br \/>\n* Suma de intersecciones dobles: $7 + 8 + 5 = 20$<br \/>\n* Intersecci\u00f3n triple: $2$<\/p>\n<p>2. Operamos siguiendo los signos alternados:<\/p>\n<p>$$\\text{Peticiones seguras} = 100 &#8211; (45) + (20) &#8211; (2)=73$$<\/p>\n<p>Respuesta: Hay 73 peticiones seguras que pueden procesarse sin riesgo.\n<\/p><\/div>\n<hr \/>\n<p><strong>Nota:<\/strong> Este enfoque es mucho m\u00e1s eficiente cuando programamos filtros. En lugar de intentar identificar cada caso \u00ablimpio\u00bb por separado, es m\u00e1s sencillo restar del total las ocurrencias de errores conocidos, ajustando las intersecciones para no sobre-contar o infra-contar los casos cr\u00edticos.<\/p>\n<blockquote><p><strong>Ejercicio:<\/strong> \u00bfCu\u00e1ntos n\u00fameros de 9 cifras tiene, al menos una vez cada uno, los d\u00edgitos 1, 3 y 7? Por ejemplo, 123456789, 13777777, 000000137.<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv() {\n  var htmlShow = document.getElementById(\"html-show\");\n  if (htmlShow.style.display === \"none\") {\n    htmlShow.style.display = \"block\";\n  } else {\n    htmlShow.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show\" style=\"display: none;\">\n<iframe loading=\"lazy\" title=\"Matem\u00e1tica Discreta - Principio de Inclusi\u00f3n-Exclusi\u00f3n II - Jes\u00fas Soto\" width=\"640\" height=\"360\" src=\"https:\/\/www.youtube.com\/embed\/4IjyA4wqago?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div>\n<hr \/>\n<h3>Desarreglos<\/h3>\n<p>Uno de las aplicaciones de este principio la encontramos en la cuenta de desarreglos.<\/p>\n<p>Consideremos el conjunto de las permutaciones \\(S_n\\), donde un elemento ser\u00e1 de la forma:<br \/>\n\\[\\displaystyle \\left(\\begin{array}{cccccccc}1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\cdots &amp; n\\\\ \\sigma_1 &amp; \\sigma_2 &amp; \\sigma_3 &amp; \\sigma_4 &amp; \\sigma_5 \\cdots &amp; \\sigma_n \\end{array}\\right) .\\]<br \/>\nSiendo \\(\\sigma_i\\in I=\\{1,2,3,4,&#8230;,n\\}\\) y de modo que \\(\\sigma_i\\neq \\sigma_j\\forall i\\neq j\\).<br \/>\nHemos visto que \\(S_n\\) con la operaci\u00f3n composici\u00f3n de permutaciones, \\(\\circ\\), le confiere una estructura de grupo; \\((S_n,\\circ)\\) es un grupo.<\/p>\n<p>Definimos un desarreglo como una permutaci\u00f3n \\(\\sigma\\in S_n\\) talque \\(\\sigma_i\\neq i\\forall i\\in I\\). El Principio de inclusi\u00f3n-exclusi\u00f3n nos ayuda a contar el n\u00famero de desarreglos que podemos encontrar en el conjunto \\(S_n\\).<\/p>\n<p>El n\u00famero de desarreglos de \\(n\\) elementos tambi\u00e9n se conoce como subfatorial, a veces escrito como \\(!n\\), que resulta:<br \/>\n\\[{\\displaystyle !n=n!\\sum _{k=0}^{n}{\\frac {(-1)^{k}}{k!}}}.\\]<\/p>\n<p>Teniendo en cuenta que el sumatorio anterior se puede expresar como el n\u00famero \\(e\\), puede verse que<\/p>\n<p>\\[{\\displaystyle !n=\\left\\lfloor {\\frac {n!}{e}}\\right\\rceil \\qquad {\\mbox{para }}n\\geq 1}\\]<br \/>\ndonde \\(\\lfloor \\,\\rceil \\) denota la funci\u00f3n parte entera m\u00e1s cercana.<\/p>\n<blockquote><p><strong>Ejercicio:<\/strong> Construye una funci\u00f3n en maxima que nos devuelva $D_n$\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv23bc() {\n  var htmlShow23bc = document.getElementById(\"html-show23bc\");\n  if (htmlShow23bc.style.display === \"none\") {\n    htmlShow23bc.style.display = \"block\";\n  } else {\n    htmlShow23bc.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23bc()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23bc\" style=\"display: none;\">\n<!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i1)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">desarreglo<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">round<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">factorial<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">%e<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[{ }{desarreglo}(n){:=}{round}\\left( \\frac{n{!}}{\\% e}\\right) \\]<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i2)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">desarreglo<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">9<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[{ }\\left[ 0{,}0{,}1{,}2{,}9{,}44{,}265{,}1854{,}14833{,}133496\\right] \\]<\/p>\n<\/div>\n<hr \/>\n<blockquote><p><strong>Ejercicio:<\/strong> Construye una funci\u00f3n en maxima que nos devuelva \\(D_n\\) utilizando<br \/>\n\\[{\\displaystyle !n=n!\\sum _{k=0}^{n}{\\frac {(-1)^{k}}{k!}}}.\\]\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv23bcd() {\n  var htmlShow23bcd = document.getElementById(\"html-show23bcd\");\n  if (htmlShow23bcd.style.display === \"none\") {\n    htmlShow23bcd.style.display = \"block\";\n  } else {\n    htmlShow23bcd.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23bcd()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23bcd\" style=\"display: none;\">\n<!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i4)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">D<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">factorial<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_function\">sum<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">^<\/span><span class=\"code_variable\">k<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_function\">factorial<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">k<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">k<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">desarreglo<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">9<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{\t}\\operatorname{D}(n)\\operatorname{:=}n\\operatorname{!} \\sum_{k=0}^{n}{\\left. \\frac{{{\\left( -1\\right) }^{k}}}{k\\operatorname{!}}\\right.}\\]<\/p>\n<p>\\[\\operatorname{\t}\\left[ 0\\operatorname{,}0\\operatorname{,}1\\operatorname{,}2\\operatorname{,}9\\operatorname{,}44\\operatorname{,}265\\operatorname{,}1854\\operatorname{,}14833\\operatorname{,}133496\\right] \\]<\/p>\n<\/div>\n<hr \/>\n<blockquote><p><strong>Proposici\u00f3n:<\/strong> Los desarreglos siguen la relaci\u00f3n de recurrencia \\[D_n = (n-1)(D_{n-1} + D_{n-2}).\\]\n<\/p><\/blockquote>\n<blockquote><p><strong>Ejercicio:<\/strong> Construye una funci\u00f3n recursiva en maxima que nos devuelva \\(D_n\\)\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv23bcde() {\n  var htmlShow23bcde = document.getElementById(\"html-show23bcde\");\n  if (htmlShow23bcde.style.display === \"none\") {\n    htmlShow23bcde.style.display = \"block\";\n  } else {\n    htmlShow23bcde.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23bcde()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23bcde\" style=\"display: none;\">\n<!-- Code cell --> <\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"> <span class=\"prompt\">(%i6) <\/span> <\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"> <span class=\"input\"> <span class=\"code_comment\">\/* Definimos los casos base y la regla *\/<\/span> <span class=\"code_endofline\"> <br \/> <\/span> <span class=\"code_function\">D_rec<\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_variable\">n<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_operator\">:<\/span> <span class=\"code_operator\">=<\/span> <span class=\"code_function\">if <\/span> <span class=\"code_variable\">n<\/span> <span class=\"code_operator\">=<\/span> <span class=\"code_number\">0<\/span> <span class=\"code_function\"> then <\/span> <span class=\"code_number\">1<\/span> <span class=\"code_function\"> else <\/span> <span class=\"code_function\"> if <\/span> <span class=\"code_variable\">n<\/span> <span class=\"code_operator\">=<\/span> <span class=\"code_number\">1<\/span> <span class=\"code_function\"> then <\/span> <span class=\"code_number\">0<\/span> <span class=\"code_function\"> else <\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_variable\">n<\/span> <span class=\"code_operator\">\u2212<\/span> <span class=\"code_number\">1<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_operator\">\u00b7<\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_function\">D_rec<\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_variable\">n<\/span> <span class=\"code_operator\">\u2212<\/span> <span class=\"code_number\">1<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_operator\">+<\/span> <span class=\"code_function\">D_rec<\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_variable\">n<\/span> <span class=\"code_operator\">\u2212<\/span> <span class=\"code_number\">2<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_endofline\">;<\/span> <span class=\"code_endofline\"> <br \/> <\/span> <span class=\"code_endofline\"> <br \/> <\/span> <span class=\"code_function\">makelist<\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_function\">D_rec<\/span> <span class=\"code_operator\">(<\/span> <span class=\"code_variable\">i<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_endofline\">,<\/span> <span class=\"code_variable\">i<\/span> <span class=\"code_endofline\">,<\/span> <span class=\"code_number\">0<\/span> <span class=\"code_endofline\">,<\/span> <span class=\"code_number\">9<\/span> <span class=\"code_operator\">)<\/span> <span class=\"code_endofline\">;<\/span> <\/span> <\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\operatorname{D\\_ rec}(n)\\operatorname{:=}\\operatorname{if}\\operatorname{ }n=0\\operatorname{ }\\operatorname{then}\\operatorname{ }1\\operatorname{ }\\operatorname{else}\\operatorname{ }\\operatorname{if}\\operatorname{ }n=1\\operatorname{ }\\operatorname{then}\\operatorname{ }0\\operatorname{ }\\operatorname{else}\\operatorname{ }\\left( n-1\\right) \\, \\left( \\operatorname{D\\_ rec}\\left( n-1\\right) +\\operatorname{D\\_ rec}\\left( n-2\\right) \\right) \\]\n<\/p>\n<p>\\[\\operatorname{ }\\left[ 1\\operatorname{,}0\\operatorname{,}1\\operatorname{,}2\\operatorname{,}9\\operatorname{,}44\\operatorname{,}265\\operatorname{,}1854\\operatorname{,}14833\\operatorname{,}133496\\right] \\]\n<\/p>\n<\/div>\n<hr \/>\n<p>Imaginemos que ahora pretendemos dejar fijos \\(k\\) elementos y los restantes se desarreglen; es decir, queremos contar el n\u00famero de permutaciones de \\(n\\) elementos que dejan fijos \\(k\\) de ellos. Este era el problema de los encuentros que ya vimos. Sin embargo, ahora lo podemos afrontar mediante desarreglos:<br \/>\n\\[T(n,k)=\\binom{n}{k}\\,!(n-k)\\]<\/p>\n<p>Por \u00faltimo, un resultado que podemos obtener aplicando este tema:<\/p>\n<blockquote><p><strong>Teorema<\/strong> El n\u00famero de de aplicaciones sobreyectivas diferentes que se pueden establecer de un conjunto \\(A\\) de cardinal \\(n\\) en otro conjunto \\(B\\) de cardinal \\(r\\) con \\(r\\leq n\\) es \\[ \\sum_{i=0}^r(-1)^i\\binom{r}{i}(r-i)^n. \\]\n<\/p><\/blockquote>\n<hr \/>\n<table id=\"yzpi\" border=\"0\" width=\"100%\" cellspacing=\"0\" cellpadding=\"3\" bgcolor=\"#999999\">\n<tbody>\n<tr>\n<td width=\"100%\">\n<p><strong>Ejercicio:<\/strong> \u00bfCu\u00e1l es el valor de \\(B_5-B_4\\)? <\/p>\n<\/td>\n<\/tr>\n<tr>\n<td width=\"100%\">\n<div id=\"menu-a\">\n<ul>\n<li>28<\/li>\n<li>37<\/li>\n<li>41<\/li>\n<\/ul>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><script>\nfunction showHtmlDiv2() {\n  var htmlShow2 = document.getElementById(\"html-show2\");\n  if (htmlShow2.style.display === \"none\") {\n    htmlShow2.style.display = \"block\";\n  } else {\n    htmlShow2.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2\" style=\"display: none;\">\n<p><strong>B.)<\/strong><\/p>\n<p>\\[B_5-B_4=\\sum_{k=0}^5 \\left\\{{5\\atop k}\\right\\}-\\sum_{k=0}^4 \\left\\{{4\\atop k}\\right\\}\\]<\/p>\n<p>\\[\\begin{split}B_5&#038;=\\sum_{k=0}^5 \\left\\{{5\\atop k}\\right\\}\\\\<br \/>\n&#038;=\\left\\{{5\\atop 0}\\right\\}+\\left\\{{5\\atop 1}\\right\\}+\\left\\{{5\\atop 2}\\right\\}+\\left\\{{5\\atop 3}\\right\\}+\\left\\{{5\\atop 4}\\right\\}+\\left\\{{5\\atop 5}\\right\\}\\\\<br \/>\n&#038;=\\left\\{{5\\atop 0}\\right\\}+\\left[\\left\\{{4\\atop 0}\\right\\}+1\\cdot\\left\\{{4\\atop 1}\\right\\}\\right]+\\left[\\left\\{{4\\atop 1}\\right\\}+2\\cdot\\left\\{{4\\atop 2}\\right\\}\\right]+\\left[\\left\\{{4\\atop 2}\\right\\}+3\\cdot\\left\\{{4\\atop 3}\\right\\}\\right]+\\left[\\left\\{{4\\atop 3}\\right\\}+4\\cdot\\left\\{{4\\atop 4}\\right\\}\\right]+\\left\\{{5\\atop 5}\\right\\}\\\\<br \/>\n&#038;\\qquad\\left(\\left\\{{4\\atop 0}\\right\\}=\\left\\{{5\\atop 0}\\right\\},\\ \\left\\{{4\\atop 4}\\right\\}=\\left\\{{5\\atop 5}\\right\\}\\right)\\\\<br \/>\n&#038;=\\left\\{{4\\atop 0}\\right\\}+\\left[\\left\\{{4\\atop 0}\\right\\}+1\\cdot\\left\\{{4\\atop 1}\\right\\}\\right]+\\left[\\left\\{{4\\atop 1}\\right\\}+2\\cdot\\left\\{{4\\atop 2}\\right\\}\\right]+\\left[\\left\\{{4\\atop 2}\\right\\}+3\\cdot\\left\\{{4\\atop 3}\\right\\}\\right]+\\left[\\left\\{{4\\atop 3}\\right\\}+4\\cdot\\left\\{{4\\atop 4}\\right\\}\\right]+\\left\\{{4\\atop 4}\\right\\}\\\\<br \/>\n&#038;=\\left[\\left\\{{4\\atop 0}\\right\\}+\\left\\{{4\\atop 1}\\right\\}+\\left\\{{4\\atop 2}\\right\\}+\\left\\{{4\\atop 3}\\right\\}+\\left\\{{4\\atop 4}\\right\\}\\right]+\\left[\\left\\{{4\\atop 0}\\right\\}+1\\cdot\\left\\{{4\\atop 1}\\right\\}+2\\cdot\\left\\{{4\\atop 2}\\right\\}+3\\cdot\\left\\{{4\\atop 3}\\right\\}+4\\cdot\\left\\{{4\\atop 4}\\right\\}\\right]\\\\<br \/>\n&#038;=\\sum_{k=0}^4 (k+1)\\cdot\\left\\{{4\\atop k}\\right\\}\\\\<br \/>\n&#038;=B_4+\\sum_{k=0}^4 k\\cdot\\left\\{{4\\atop k}\\right\\}<br \/>\n\\end{split}\\]<\/p>\n<p>\\[B_5-B_4=\\displaystyle\\sum_{k=0}^4 k\\left\\{{4\\atop k}\\right\\}=37\\]<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>El principio de inclusi\u00f3n-exclusi\u00f3n permite calcular el cardinal de la uni\u00f3n de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones. Si consideramos que tenemos dos&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-1296","post","type-post","status-publish","format-standard","hentry","category-matematica-discreta"],"_links":{"self":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1296","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1296"}],"version-history":[{"count":14,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1296\/revisions"}],"predecessor-version":[{"id":1298,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1296\/revisions\/1298"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}